Different Methods and Their Comparison in Solving Traveling Salesman Problem

Bakalaureusetöö eesmärk on tutvustada erinevate probleemilahenduse algoritmide tööpõhimõtteid, uurida nende omadusi ning leida nende eelised ja puudused. Töö tulemusi saavad kasutada Tartu Ülikoolis õpetatava kursuse Tehisintellekt I kuulajad toetava ja lisamaterjalina probleemilahendusmeetodite omandamiseks. Algoritme uuritakse ühe kindla algoritmilise probleemi baasil. Iga algoritmi juures tutvume esmalt selle ülesehituse ja algoritmiliste omadustega. Lisaks võrdleme kõikide algoritmide tööd ja tulemusi omavahel. Uurimistöö sisu eeldab lugejalt arusaama programmeerimises tuntumatest andmestruktuuridest ja terminitest. Mõningate tehnoloogiate tausta seletatakse täpsemalt, juhul kui need ei ole Tartu Ülikooli matemaatika-informaatikateaduskonna informaatika bakalaureuseõppe õppekavas. Käsitletud algoritme on implementeeritud õpiprogrammis, mis hõlbustab algoritmide tulemuste ja töö visualiseerimist. Bakalaureusetöö raames tutvume tehisnärvivõrkudega ja nende seast lähemalt Hopfieldi närvivõrguga. Uurime tuntumaid pimeotsingualgoritme: süvitsi- ja laiutiotsingut. Käsitletavate heuristiliste otsingualgoritmide hulka kuuluvad lähima naabri algoritm, parim-enne algoritm, geneetiline algoritm ja libalõõmutamise algoritm. Esimeses peatükis tutvustame konkreetset probleemi, mis on valitud algoritmide käsitlemiseks. Sellele järgnevalt uurime iga algoritmi eraldi. Kui oleme tutvunud algoritmidega, analüüsime ja võrdleme neid omavahel. Töö lõpus tutvustame valminud programmi ja teeme ka mõningad tähelepanekud ning ettepanekud tulevaseks arenduseks. Lisades on kirjeldatud matemaatilised funktsioonid, mille abil on võimalik tasandil punktide koordinaatidest luua kaugusmaatriks ja kaugusmaatriksist punktid kahemõõtmelisele tasandile (see on seotud algoritmide käsitlemisel aluseks võetud konkreetse probleemiga). Programm on tööle lisatud CD-l.Traveling salesman problem is a NP-hard problem which is commonly used as an abstraction of many real life problems. It is widely used as benchmark to many optimization methods. In given thesis we analyze various methods, describe their algorithms and benchmark their performance when solving traveling salesman problem. Furthermore we compare results. Firstly an introduction is made to artificial neural networks. Then Hopfield neural network is introduced and applied to solving traveling salesman problem. Secondly blind search algorithms are introduced. In given thesis we focus on depth first search and breadth first search. In both cases we introduce some optimizations to algorithms which enable them to work faster. Thirdly heuristic search algorithms are introduced and some more common algorithms are analyzed. In given thesis nearest neighbour algorithm, best first algoritm, genetic algorithm and simulated anneal are described. Once the algorithms and theory behind them are described, they are implemented in a java application, which is used to benchmark their performance. Application is made firsthand for students to observe how algorithms work, as well as measure their time consumption and measure the results of each algoritm. Having done the benchmarks in this thesis, it is concluded that blind search algoritms are not suitable methods for solving traveling salesman problem. Furthermore it is concluded that Hopfield neural networks are also impractical when it comes to solving traveling salesman problem. Nearest neighbour search, genetic algorithm and simulated annealing are found to be most promising methods when solving problem described above. Most suitable method is found to be simulated annealing proving to find good solutions in relatively short time. In the end of thesis some proposals are made, which could be further investigated by students. These proposals could benefit work done so far by improving described methods. Mathematical functions to generate distance matrix from coordinates and vice versa are described in extras