2-aproksimacijski algoritem za metrični TSP

Spodnja dva (v Pythonu napisana) programa rešujeta problem trgovskega potnika. Znano je, da problem trgovskega potnika NP-težek problem. To pomeni, da nihče ne pozna hitrega algoritma, ki bi poiskal (točno) rešitev. Če v grafu velja trikotniška neenakost, potem imamo metrični TSP. Poznamo več aproksimacijskih algoritmov, ki rešujejo metrični TSP. Spodaj je implementacija 2-aproksimacijskega algoritma. Rešitev, ki jo ta algoritem najde, ne bo optimalna, a bo slabša kvečjemu za faktor 2 od optimalne. Obstajajo tudi boljši algoritmi, npr. Christofidesov algoritem, ki je 1,5-aproksimacijski.

Download

• completeSearch.py (iskanje z grobo silo)
• twoApprox.py (2-aproksimacijski algoritem)
• podatki.txt (datoteka s testnimi podatki)

Navodila

Program pričakuje na disku datoteko z imenom podatki.txt. V prvi vrstici tega programa sta dve celi števili n (število vozlišč v grafu) in m (program rešuje TSP samo na prvih m vozliščih grafa).

Tej vrstici sledi n vrstic z imeni vozlišč.

V naslednjih n-1 vrsticah je spodnji trikotnik matrike razdalj med kraji. (Ker je matrika simetrična in ker so na diagonali ničle, nam spodnji trikotnik pove vse o razdaljah.) V prvi vrstici je eno samo število: razdalja med vozliščema #1 in #2. V naslednji vrstici sta dve števili: prvo je razdalja med vozliščema #1 in #3, drugo pa razdalja med vozliščema #2 in #3.

Bug reports & feature requests

Če opazite kakšnega hrošča ali imate idejo za izboljšavo programov, mi pišite na nino.basic@gmail.com.