Vehbi Neziri, Ramadan Dervishi, Blerim Rexha
Publication year: 2013

ABSTRACT

Problemi TSP (Travelling Salesman Person) është i njohur si problem NP i vështirë (non-deterministic polynomial-time) dhe për këtë arsye algoritmet janë të detyruara të japin një zgjidhje optimale brenda një kohe të arsyeshme. Qëllimi i TSP është të përcaktojë ose gjejë ciklin më të shkurtër të ashtuquajtur cikli i Hamiltonit a rrugën më të shkurtër duke kaluar nëpër të gjitha nyjat në një graf me n nyje. Problemi njihet edhe kur një agjent tregtar duhet të vizitojë një sërë të qyteteve në mënyrë të tillë që të përshkojë të gjitha qytetet duke shpenzuar sa më pak para, e kjo do të ishte e mundur duke gjetur rrugën më të shkurtër.
Punimi analizon problemin TSP duke përdorur algoritmet Simulated Annealing dhe Hill Climbing për numër të ndryshueshëm të nyjave a qyteteve në rastin kur në mes qyteteve ekziston vetëm një rrugë. Në fund janë dhënë krahasimet dhe përparësitë e njërit algoritëm ndaj algoritmit tjetër si në aspektin kohor e po ashtu edhe në aspektin e numrit të pikave që duhen vizituar.