All Colors Shortest Path Problem on Trees
Ağaç Yapılarında Tüm Renkleri İçeren En Kısa Yol Problemi
- Tez No: 395444
- Danışmanlar: DOÇ. DR. HÜSEYİN AKCAN, DOÇ. DR. CEM EVRENDİLEK
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2015
- Dil: İngilizce
- Üniversite: İzmir Ekonomi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Akıllı Mühendislik Sistemleri Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- 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
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİzmir Ekonomi ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ KUTLUHAN EROL
- 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
2015
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
PROF. DR. ERGİN TARI
- 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
2024
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
PROF. DR. ERDİNÇ ALTUĞ
- التحدّي في القرآن الكريم (کتاب في ظلال القُرآن أنموذجاً)
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
2021
DinKarabük ÜniversitesiTemel İslam Bilimleri Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HOSSAM MOUSSA MOHAMED SHOUSHA HOSSAM MOUSSA MOHAMED SHOUSHA
- 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
2012
Tekstil ve Tekstil MühendisliğiUşak ÜniversitesiTekstil Mühendisliği Ana Bilim Dalı
PROF. DR. AHU DEMİRÖZ GÜN