Izbrani postopki za problem trgovskega potnika

Vladimir Batagelj, 1992; zadnja sprememba: 27. oktober 1997

genixy - naklju~ne to~ke

Program genixy ustvari datoteko s koordinatami izbranega {tevila naklju~nih to~k v ravnini. Zahteva tri parametre: ime datoteke (brez podalj{ka), {tevilo to~k in obseg vrednosti koordinat. Tako na primer zahteva genixy poskus 25 1000 ustvari datoteko poskus.xy, ki vsebuje zaporedje 25 naklju~nih to~k podanih s koordinatama x in y, 0 <= x, y <= 1000.

euclid - evklidske razdalje med to~kami

Program euclid zahteva dva parametra: ime vhodne datoteke vrste xy s celo{tevilskimi koordinatami to~k in ime izhodne datoteke vrste dis, na katero zapi{e matriko evklidskih razdalj med danimi to~kami. Razdalje so zaokro`ene na cela {tevila. Obe imeni datotek sta brez podalj{kov. Na primer: euclid poskus poskus ustvari na datoteki poskus.dis matriko razdalj med to~kami z datatoteke poskus.xy.

To datoteko lahko sestavimo tudi ro~no z urejevalnikom - vnesemo svoje podatke. Zgrajena je takole: v prvi vrstici datoteke je napisano {tevilo to~k grafa; nato sledi v vsaki vrstici po ena vrstica matrike razdalj (tipa Integer). Posamezna {tevila so lo~ena vsaj z enim presledkom.

Pozor: ker so v pascalu navadna cela {tevila razmeroma majhna, lahko pride med ra~unanjem do prekora~itev obsega.

enumerat - postopek popolnega prebora

Program enumerat dolo~i to~no re{itev problema trgovskega potnika s pregledom vseh n! mo`nih ciklov, kjer je n {tevilo to~k grafa. Ker n! nara{~a zelo hitro, je to izvedljivo le za majhne grafe. V program je vgrajena omejitev n <= 20.

Program pri~akuje imena treh datotek (brez podalj{kov): izpis, razdalje in re{itve. Na primer:

enumerat poskus poskus poskus Klic oblike enumerat ? izpi{e kratek napotek, kako program pokli~emo. ^e pa zahtevamo samo: enumerat bomo imena datotek dolo~ili v pogovoru.

2_opteng - postopek lokalne optimizacije 2-OPT

Program 2_opteng posku{a dolo~iti ~im bolj{o re{itev problema trgovskega potnika z lokalno optimizacijo glede na sose{~ino 2-OPT. V program je vgrajena omejitev n <= 100. Po`enemo ga z zahtevo: 2_opteng Potrebne datoteke dolo~imo v pogovoru. ^e za dane razdalje obstajajo tudi koordinate, si lahko potek iskanja re{itve ogledamo tudi na sliki.

3_opteng - postopek lokalne optimizacije 3-OPT

Program 3_opteng posku{a dolo~iti ~im bolj{o re{itev problema trgovskega potnika z lokalno optimizacijo glede na sose{~ino 3-OPT. V program je vgrajena omejitev n <= 100. Po`enemo ga z zahtevo: 3_opteng Potrebne datoteke dolo~imo v pogovoru. ^e za dane razdalje obstajajo tudi koordinate, si lahko potek iskanja re{itve ogledamo tudi na sliki.

bab - postopek razveji in omeji

Program bab dolo~i to~no re{itev problema trgovskega potnika po postopku razveji in omeji. V program je vgrajena omejitev n <= 50. Po`enemo ga z zahtevo: bab Potrebne datoteke dolo~imo v pogovoru.

display - prikaz re{itev

Program display omogo~a za podatke, ki vsebujejo tudi koordinate, slikovni prikaz re{itev dobljenih s programi za iskanje re{itev problema trgovskega potnika.

Program pri~akuje kot parameter ime datotek (brez podalj{ka) s podatki. Na primer na zahtevo:

display poskus bo program pri~akoval re{itve na datoteki poskus.sol in koordinate na datoteki poskus.xy.