Problem trgovskega potnika

Iz MaFiRaWiki

Vsebina

Definicija

Problem trgovskega potnika (angleško traveling salesman problem (TSP)) je dobro znan problem. Dano je omrežje (graf, kjer poznamo vredenosti povezav). Trgovski potnik mora obresti vsa vozlišča tako, da bo pri tem prehodil čim krajšo pot (da bo vsota vrednost uporabljenih povezav čim manjša) in se vrniti v izhodišče.

Reševanje problema

Problem rešujemo tako da:

  • prepoznavamo in hranimo možne rešitve,
  • ocenjujejo obetavnost rešitev in
  • zavržemo rešitve, ki ne morejo pripeljati do boljše rešitve kot je obstoječa možna rešitev.

V splošnem je strategija reševanja uporabna ko:

  • imamo N stanj in vsa moramo obiskati,
  • poznamo "vrednost, ceno, čas" prehoda iz enega stanja v drugega,
  • želimo, čim ugodnjeje obiskati vsa stanja in priti na začetek.
  • Točka začetka ni pomembna!

Primeri tovrstnih problemov:

  • vrtanje lukenj na elektronskih vezjih,
  • robotsko sestavljanje elektronskih vezij,
  • optimalna pot poštarja, ko prazni/polni nabiralnike ali trgovskega potnika,
  • voznik dostavnega kamiona, ko razvaža blago v trgovine,...

Koraki reševanja

  • Naredimo spisek vseh možnih poti in njihovih cen (sestavimo matriko omrežja v kateri so vse možne povezave in njihove vrednosti).
  • Pridobimo oceno vrednosti posameznih poti (izvedemo postopek redukcije matrike omrežja, ki pove, koliko nas bo minimalno stala določena pot).
  • Po najbolj obetavni poti pridemo do prve možne rešitve (krožne poti), ki ima določeno končno vrednost.
  • Oklestimo(izločimo) vse poti, ki imajo kvečjemu enako ali pa slabšo možno končno vrednost.
  • Nadaljujemo na poteh, kjer je možno dobiti boljšo končno vrednost.
  • V teortičnem računalništvu je prevladalo, da pojma lahki in težki problem ustrezata razreda P in NP.

V razredu P so problemi za katere obstajajo polinomski algoritmi. V razredu NP so posebej odlikovana skupina NP-polnih problemov. Za NP-polne probleme velja, če bi obstajal polinomski algoritem za reševanje enega od njih, potem bi obstajal polinomski algoritem za vse probleme iz razreda NP. V primeru PTP imamo končno množico in algoritem je eksponentnega reda.

  • Prostorska zahtevnost pa tudi ne kaže najbolje, saj moramo vedno hraniti vsaj skupen seštevek cen.

Dve metodi za reševanje PTP

  • Rešitev problema trgovskega potnika nas hitreje pripelje do najugodnejše poti, kot če bi pot iskali s sestopanjem (Sestopanje).

Pri sestopanju najboljšo rešitev(pot) poiščemo tako, da preverimo vse možne rešitve in izberemo najboljšo. Prednost rešitve problema trgovskega potnika je v tem, da je hitrejši, ker ne išče med možnostimi, kjer boljša rešitev ni možna!

Način reševanja je smiselno uporabljati takrat, ko imemo veliko število stanj. Ocena vrednosti posameznih poti je namreč preveč potratna za manjše število stanj.

Spet vzamemo za izhodišče vozlišče 1. Za zaporedje odločitev lahko vzamemo: kam na tekočem koraku. Če je graf poln, imamo za prvi cilj n-1 možnosti, za drugi n-2 itn., torej v celoti (n-1)! možnih poti.

Naj bo 1 => k => v1 => v2 => ... => vn-2 => 1 najkrajša krožna pot. Očitno mora biti k => v1 => v2 => ... => vn-2 => 1 najkrajša pot iz k => 1, ki gre skozi vsako od vozlišč V\{1, k} natanko enkrat, saj drugače tudi celotna pot ni najkrajša. Velja pravilo optimalnosti. označimo:

g(i, s) := dolžina najkrajše poti, ki začne v i, gre skozi vsa vozlišča S natanko enkrat in konča v 1.

Najkrajša krožna pot je torej dolga g(1, V\{1}).

Denimo, da smo v tekočem vozlišču i in še nismo obiskali vozlišč v. Naj j označi vozlišče, za katerega se odločimo v vozlišču i. Ker gremo iz j do i po preostalih vozliščih po najkrajši poti, nam izbiro j narekuje tale Bellmanova enačba

g(i, s) = min (c[i, j] + g(j, s\{j}) (j je element množice S), če S ni prazna.

Za konstrukcijo rešitve seveda potrebujemo vrednosti j, ki minimizirajo desno stran. Vpeljimo

J(i, S) := vrednost j, ki določa g(i, S).


Primer rešen s sestopanjem

Za omrežje dano s spodnjo matriko določi vse krožne poti in izpiši njihove dolžine. Skiciraj drevo stanj in poišči optimalno pot.

20 30 10 11
15 16 4 2
3 5 2 4
19 6 18 3
16 4 7 16

Kako rešujemo: Izberemo poljubno točko, iz katere bomo začeli našo pot. Pa si v našem primeru izberimo točko 3. Napišemo vse možne poti in njihove vrednosti med njimi seštejemo. Le te pa dobimo v zgornji matriki.

Naše poti:

3 - 1 - 2 - 4 - 5 - 3 vrednost poti je 37
3 - 1 - 2 - 5 - 4 - 3 vrednost poti je 59
3 - 1 - 5 - 2 - 4 - 3 vrednost poti je 50
3 - 1 - 5 - 4 - 2 - 3 vrednost poti je 62
3 - 1 - 4 - 2 - 5 - 3 vrednost poti je 28
3 - 1 - 4 - 5 - 2 - 3 vrednost poti je 36

3 - 2 - 1 - 5 - 4 - 3 vrednost poti je 40
3 - 2 - 1 - 5 - 4 - 3 vrednost poti je 65
3 - 2 - 4 - 1 - 5 - 3 vrednost poti je 48
3 - 2 - 4 - 1 - 5 - 3 vrednost poti je 58
3 - 2 - 5 - 1 - 4 - 3 vrednost poti je 51
3 - 2 - 5 - 4 - 1 - 3 vrednost poti je 72

3 - 4 - 1 - 2 - 5 - 3 vrednost poti je 50
3 - 4 - 1 - 5 - 2 - 3 vrednost poti je 53
3 - 4 - 2 - 1 - 5 - 3 vrednost poti je 41
3 - 4 - 2 - 5 - 1 - 3 vrednost poti je 56
3 - 4 - 5 - 1 - 2 - 3 vrednost poti je 57
3 - 4 - 5 - 2 - 1 - 3 vrednost poti je 54

3 - 5 - 1 - 2 - 4 - 3 vrednost poti je 62
3 - 5 - 1 - 4 - 2 - 3 vrednost poti je 52
3 - 5 - 2 - 1 - 4 - 3 vrednost poti je 51
3 - 5 - 2 - 4 - 1 - 3 vrednost poti je 51
3 - 5 - 4 - 1 - 2 - 3 vrednost poti je 75
3 - 5 - 4 - 2 - 1 - 3 vrednost poti je 71

Optimalna pot v našem primeru je: 3 - 1 - 4 - 2 - 5 - 2, kjer je vrednost poti 28.

Drevo stanj:

image:Drevostanj.jpg

Glej tudi

Osebna orodja