Učinkovitost drevesnega preiskovanja Monte Carlo na problemu trgovskega potnikaGrbec, Mia (Avtor) Čibej, Uroš (Mentor) Drevesno preiskovanje Monte CarloProblem trgovskega potnikahevristikaProblem 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.20252025-09-03 12:05:00Diplomsko delo/naloga171851VisID: 37980COBISS_ID: 248507651sl