Geri Dön

All Colors Shortest Path Problem on Trees

Ağaç Yapılarında Tüm Renkleri İçeren En Kısa Yol Problemi

  1. Tez No: 395444
  2. Yazar: MEHMET BERKEHAN AKÇAY
  3. Danışmanlar: DOÇ. DR. HÜSEYİN AKCAN, DOÇ. DR. CEM EVRENDİLEK
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2015
  8. Dil: İngilizce
  9. Üniversite: İzmir Ekonomi Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Akıllı Mühendislik Sistemleri Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 67

Özet

Ağaç Yapılarında Tüm Renkleri İçeren En Kısa Yolu Bulma (TREKY-a) problemi, V kümesi içinde bulunan r düğümünde kökleşmiş bir T = (V;E) ağacı verilip, ağaçtaki her bir düğüme C = {1,2,...,k} kümesinden bir renk atandığında, r düğümünden başlayarak, her bir farklı renkten en az bir düğüm içeren en kısa yolu bulma problemidir. Biz TREKY-a probleminin NP-Zor olduğunu gösteriyoruz. Ayrıca, TREKY-a için sabit faktörlü bir yakınsama algoritmasının olmadığını kanıtlıyoruz. TREKY-a problemi için tamsayı lineer programlama formülü veriyoruz. Bu formülün lineer programlama gevşetmesini temel alarak çeşitli sezgisel çözüm yöntemleri öneriliyor. Bu tez ayrıca TREKY-a için Genetik ve Tabu Arama algoritmalarını temel alan alternatif sezgisel çözüm yöntemleri de geliştirmektedir. Önerilen bütün sezgisel yöntemlerin performansı çeşitli parametrik tipte ağaçlarla deneysel olarak değerlendirilmektedir.

Özet (Çeviri)

Given an edge weighted tree T(V;E), rooted at a designated base vertex r \in V, and a color from a set of colors C = {1,2,...,k} assigned to every vertex v \in V , All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly nonsimple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-Hard, and also prove that it doesn't have a constant factor approximation algorithm. We give an Integer Linear Programming formulation of ACSP-t. Based on a Linear Programming relaxation of this formulation, several heuristics are proposed. The thesis also explores Genetic Algorithms, and Tabu Search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are finally evaluated experimentally for a wide range of trees parametrically generated.

Benzer Tezler

  1. Using artificial intelligence and machine learning to solve NP-complete graph theory problems

    NP-tam çizge teori problemlerinin çözümü için yapay zeka ve makine öğrenmesi kullanımı

    MUSTAFA KEMAL BİNLİ

    Yüksek Lisans

    İngilizce

    İngilizce

    2020

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİzmir Ekonomi Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ KUTLUHAN EROL

  2. Comparison of shortest path and least risk path according to the 2D and 3D visualizations for multilayered indoor spaces

    En kısa yol ve en az riskli yol algoritmalarının 2B ve 3B görselleştirilmiş çok katlı binalarda karşılaştırılması

    HAZAL CEYLAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2015

    Jeodezi ve Fotogrametriİstanbul Teknik Üniversitesi

    Geomatik Mühendisliği Ana Bilim Dalı

    PROF. DR. ERGİN TARI

  3. Integrating path planning and image processing with UAVs for disease detection and yield estimation in indoor agriculture

    Kapalı alan tarımda hastalık tespiti ve verim tahmini için rota planlama ve görüntü işlemenin İHA'larla entegre edilmesi

    ONAT ERDOĞMUŞ

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    Mekatronik Mühendisliğiİstanbul Teknik Üniversitesi

    Mekatronik Mühendisliği Ana Bilim Dalı

    PROF. DR. ERDİNÇ ALTUĞ

  4. التحدّي في القرآن الكريم (کتاب في ظلال القُرآن أنموذجاً)

    Kuran meydan okuma yaklaşım okumaları (Fi Zilalil Kuran örneği) / Qur'anic method of challenge (Fi Dhillal al Qurans' book an as example)

    ABDULLAH MUHI MAHGOOB

    Yüksek Lisans

    Arapça

    Arapça

    2021

    DinKarabük Üniversitesi

    Temel İslam Bilimleri Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ HOSSAM MOUSSA MOHAMED SHOUSHA HOSSAM MOUSSA MOHAMED SHOUSHA

  5. Mikroliflerden üretilen düz örme kumaşların aşınma ve renk haslık özelliklerinin incelenmesi

    Investigation of abrasion and color fastness properties of flat knitted fabrics from microfiber

    BURÇİN DEMİRCAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2012

    Tekstil ve Tekstil MühendisliğiUşak Üniversitesi

    Tekstil Mühendisliği Ana Bilim Dalı

    PROF. DR. AHU DEMİRÖZ GÜN