A study on performance evaluation of optimization algorithms in the shortest path problem
En kısa yol probleminde optimizasyon algoritmalarının performans değerlendirmesi üzerine bir çalışma
- Tez No: 619063
- Danışmanlar: PROF. DR. FATİH VEHBİ ÇELEBİ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Graf, en kısa yol, optimizasyon, Dijkstra, Floyd-Warshall, Bellman-Ford, Johnson's, Graph, the shortest path, optimization, Dijkstra, Floyd-Warshall, Bellman-Ford, Johnson's
- Yıl: 2020
- Dil: İngilizce
- Üniversite: Ankara Yıldırım Beyazıt Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
İki nokta arasındaki en kısa yolun en kısa sürede ya da en az maliyetle bulunması pek çok alanda oldukça önemlidir. En kısa yol problemi graf üzerindeki bir başlangıç düğümünden hedef düğümüne en kısa yoldan gitmeyi amaçladığından günümüzde trafik uygulamalarında, internet trafiğinin yönlendirilmesi ve oyun programlamada sıklıkla kullanılmaktadır. Zaman geçtikçe, bilim ve teknolojinin gelişmesiyle birlikte, birçok bilim insanı en kısa yol problemini çözmek için araştırmalar yapmış, birçok algoritma geliştirilmiştir. Farklı türdeki problemlere hitap eden bu algoritmalarla, düğümler arasındaki en kısa yollar bulunabilmektedir. Literatürde en kısa yol problemine ilişkin oldukça fazla sayıda ve farklı çalışmalar yer aldığı gözlenmiştir. Bu çalışmanın amacı en kısa yol problemlerinde kullanılan algoritmalardan dördünün analiz edilmesi ve karşılaştırılmasıdır. Projede Dijkstra Algoritması, Bellman–Ford Algoritması, Johnson's Algoritması ve Floyd-Warshall Algoritmasının ekranda çizilen bir graf için, başlangıç ve bitiş noktası belirlenerek hangi sürede ve hangi maliyet ile en kısa yolu bulabildiği tespit edilmiştir. En kısa yolun belirlenmesinde hangi algoritmanın daha iyi ve etkili olduğu tartışılmıştır. 4 farklı algoritmanın tamamiyle bağlı, pozitif ağırlıklı kenarlardan oluşan ve yönsüz graflar için, aynı simulasyon ile kıyaslanması daha önce karşılaşılmamış bir çalışma olması nedeni ile önem taşımaktadır. Çalışma sonuçlarına göre, kullanılacak algoritmanın graf veya problem türüne göre seçilmesi gerektiği anlaşılmıştır. Ancak; bağlı, pozitif ağırlıklı kenarlardan oluşan ve yönsüz graflar için kesinlikle Dijkstra algoritması kullanılması gerektiği gözlenmiştir.
Özet (Çeviri)
Finding the shortest or least costly path between two points in the shortest time is crucial in many areas. The shortest path problem aims to move from a starting node on a graph to the destination node via the shortest path. Nowadays it is widely used in traffic applications, routing of internet traffic and programming of games. As time went by and with the development of science and technology, many scientists made researches to solve the shortest path problem, and many algorithms were developed. These algorithms address different kinds of problems and the shortest paths between nodes can be found with them. It can be observed that in the literature there are many and different studies on the shortest path problem. The aim of this study is to analyze and compare four of the algorithms used in shortest path problem. Dijkstra, Bellman – Ford, Johnson's and Floyd-Warshall Algorithms are displayed on the graph drawing application. It is discussed that which algorithm is better and more effective in finding the shortest path. The comparison of four different algorithms for positive weighted, non-directional and fully connected graphs on the same graph drawing application is remarkable because there is no study on this subject with the same spesifications. According to the results of the study, it is understood that algorithm that will be used should be selected in line with type of graph and problem. It is proved that Dijkstra algorithm is absolutely must be used for fully connected, positive weighted and non-directional graphs.
Benzer Tezler
- A decision support model for the early design phase of residential buildings based on space conditioning energy prediction and optimization with embodied energy
Konut binalarının erken tasarım aşaması için mekan iklimlendirme enerjisi tahmini ve gömülü enerji ile optimizasyonuna dayalı bir karar destek modeli
DAMLA KÖMÜRCÜ
Doktora
İngilizce
2025
Enerjiİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. FETHİYE ECEM EDİS
- Sosyal medyadaki nefret söylemi içeren yayınların tespitinde yapay zeka temelli makine öğrenmesi algoritmalarının performans değerlendirmesi
Performance evaluation of artificial intelligence based machine learning algorithms in detecting publications containing hate speech on social media
KADİR TURGUT
Yüksek Lisans
Türkçe
2023
Mühendislik Bilimleriİstanbul Gedik ÜniversitesiYapay Zeka Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ AYTAÇ UĞUR YERDEN
- Karınca kolonisi ve parçacık sürü optimizasyonu algoritmaları ile 360 derece performans değerlendirme modeli: Bir yazılım firmasında uygulaması
A 360-degree performance evaluation model using ant colony and particle swarm optimization algorithms: An application in a software company
ZEYNEP YAĞIZ
Yüksek Lisans
Türkçe
2024
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. MERVE CENGİZ TOKLU
- Evaluation of heuristic algorithms for traffic signal optimization along a corridor
Bir koridor boyunca trafik sinyal optimizasyonu için sezgisel algoritmaların değerlendirilmesi
MORTEZA AHMADPUR
Yüksek Lisans
İngilizce
2016
TrafikBoğaziçi Üniversitesiİnşaat Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ILGIN GÖKAŞAR
- Bir dişli pompa grubunun imalatında eşzamanlı mühendislik ve grup teknolojisi
The carrying out of group technology in the concurrent engineering concept on a factory which is manufacturing gear pomp
ALPER ASLAN
Yüksek Lisans
Türkçe
1997
Makine Mühendisliğiİstanbul Teknik ÜniversitesiMakine Mühendisliği Ana Bilim Dalı
PROF. DR. TEOMAN KURTAY