20.500.12556/RUL-171851 Učinkovitost drevesnega preiskovanja Monte Carlo na problemu trgovskega potnika Efficiency of Monte Carlo Tree Search for the Traveling Salesman Problem Problem trgovskega potnika (TSP) je klasičen NP-težek optimizacijski problem, katerega cilj je najti najkrajšo pot, ki obišče vsako vozlišče natančno enkrat. V diplomski nalogi preučujemo uporabo drevesnega preiskovanja Monte Carlo (MCTS), znanega iz področja umetne inteligence, za približno reševanje problema TSP. Poleg implementacije osnovnega algoritma MCTS predstavimo tudi nadgradnje, kot so hevristično vodene simulacije. Testiranje je bilo opravljeno na standardnih primerih iz zbirke TSPLIB. Rezultate metode MCTS primerjamo z algoritmom najbližjega soseda, genetskim algoritmom, optimizacijo s kolonijami mravelj in napredno hevristiko Lin-Kernighan. MCTS se ni izkazal za učinkovitejšega od naprednih hevristik, kot je Lin-Kernighan, in je v primerjavi z njimi tudi počasnejši. Kljub temu dosega boljše rezultate kot preproste metode in nekatere metahevristike ter zlasti pri večjih primerkih kaže potencial za izboljšave in nadgradnje v prihodnosti. The Traveling Salesman Problem (TSP) is a classic NP-hard optimization problem, where the goal is to find the shortest possible route that visits each node exactly once. In this thesis, we explore the use of the Monte Carlo Tree Search (MCTS) method—originally developed in the field of artificial intelligence—for approximating solutions to the TSP. In addition to implementing the basic MCTS algorithm, we also introduce enhancements such as heuristically guided simulations. The method was tested on standard benchmark instances from the TSPLIB library. We compare the performance of MCTS against the Nearest Neighbor algorithm, Genetic Algorithm, Ant Colony Optimization, and the advanced Lin-Kernighan heuristic. MCTS did not outperform advanced heuristics such as Lin-Kernighan and was also slower in comparison. However, it achieved better results than simpler methods like Nearest Neighbor or some metaheuristics and demonstrates potential for improvement, especially on larger instances. Drevesno preiskovanje Monte Carlo Problem trgovskega potnika hevristika Traveling Salesman Problem Monte Carlo Tree Search heuristic true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2025-09-03 12:05:00 2025-09-03 12:05:12 2025-09-22 04:06:04 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 37980 248507651 Grbec_Mia_-_Ucinkovitost_drevesnega_preiskovanja_Monte_Carlo_na_problemu_trgovskega_potnika.pdf Grbec_Mia_-_Ucinkovitost_drevesnega_preiskovanja_Monte_Carlo_na_problemu_trgovskega_potnika.pdf 1 71E23FFEA984F52F4D7620910A095F34 aa3c796e7db0c0224ddf48661f9fdc2f812d5e09df3baa94b178c3bf87353e59 55bb25ed-88ad-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=215377 Fakulteta za računalništvo in informatiko 0 0 0