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ı: 73
Ö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
- Farklı topoloji optimizasyon algoritmalarının performans değerlendirmesi üzerine bir çalışma
A study on the performance evaluation of different topology optimization algorithms
FUAT SİNAN ATEŞ
Yüksek Lisans
Türkçe
2020
Makine MühendisliğiGazi ÜniversitesiEndüstriyel Tasarım Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSMAİL ŞAHİN
DR. HARUN GÖKÇE
- Geliştirilmiş SPEA2 ile envanter probleminin çözümü
Inventory optimization with a novel SPEA2 algorithm
ALİ BAYRAKDAR
Yüksek Lisans
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Aydın ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. ILHAM HUSEYINOV
- 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
- Bulanık çok modlu kaynak kısıtlı proje çizelgeleme problemlerinin çözümü için matematiksel bir model
A mathematical model for the solution of the fuzzy multi mode resource-constrained project scheduling problems
ÖMER ATLI
Doktora
Türkçe
2012
Endüstri ve Endüstri MühendisliğiHava Harp Okulu KomutanlığıEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. CENGİZ KAHRAMAN
- Üç boyutlu palet yükleme probleminin metasezgisel çözüm yaklaşımı ile bir otomotiv fabrikasında uygulaması
The application of the three-dimensional pallet loading problem in an automotive factory with a metaheuristic solution approach
MERVE SİMGE USUK
Yüksek Lisans
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. İHSAN HAKAN SELVİ