Jump to content

ostatní Traveling Salesman Problem


Lukasz

Recommended Posts

Zdravím,

v dnešní rubrice si povíme něco o TSP.

Traveling Salesman Problem (TSP) je jedním z nejklasičtějších problémů kombinatorické optimalizace.

O co v tomto problému jde? Mějme seznam měst a vzdálenosti mezi nimi, naším cílem je navštívit každé z měst právě jednou a to nejkratší cestou.

Jednoduché zadání, přesto se jedná o NP-hard problém - to zjednodušeně znamená, že je alespoň tak těžký, jako všechny NP úlohy (všechny NP úlohy se dají polynomiálně redukovat na tento problém). Tedy najít řešení pro tuto úlohu není jednoduché. Problém je dokonce silně NP-hard!!

S tímto problémem se můžete přímo setkat v různých odvětvích, například v logistice - minimalizace cesty kurýra, plánování pro rozvážení s omezeným počtem vozidel (a kapacity) apod. A v mnoha dalších odvětvích i v lehce modifikované verzi.

Vzhledem k tomu, že se jedná o hodně studovaný problém a tím pádem na něj existují optimalizované solvery, není od věci toho využít a polynomiálně na něj zredukovat i ostatní NP úlohy.


Historie:

Nebudeme se zde zabývat tím, kdo a kdy tento problém formuloval, ale tím, pro jak velké úlohy se postupem času dokázaly najít optimální řešení.

1954 - 49 měst
1977 - 120 měst
1987 - 532 "měst"
1987 - 666 "měst"
1987 - 2 392 "měst"
1994 - 7 397 "měst"
1998 - 13 509 měst
2001 - 15 112 měst
2004 - 24 978 měst

Fun fact: Procter&Gamble měli soutěž o vyřešení TSP s 33 městy v roce 1962. Hlavní výhra $10k. A to se vyplatí!


Formulace problému:

Formulací tohoto problému je hned několik, my si zde představíme 2 formulace.

Mějme kompletní neorientovaný graf G a váhy c: E(G) -> R+
Naším cílem je najít Hamiltonovu kružnici T, která minimalizuje váhy (suma c(e) pro všechny hrany e z E(t) je minimální).

Takto se formuluje symetrická verze tohoto problému. Pokud by se jednalo o asymetrickou verzi, pak bychom měli kompletní orientovaný graf v předchozí formulaci. V takovém případě by cena cesty z města A do města B byla jiná, než cena cesty z města B do města A.

Metrický TSP je formulován podobně, ale klademe si větší podmínky na váhy a to takové, že vyžadujeme aby splňovaly trojúhelníkovou nerovnost - tzn. pro všechny váhy c platí c({i, j}) + c({j, k}) ≥ c({k, i})

 

Řešení problému

Řešení problému není tak jednoduché. Pro (a)symetrické TSP nemáme ani aproximační algoritmy. Pro metrické TSP máme r-aproximační algoritmy, jako například Christofides' algorithm (2/3-aproximační). k-opt atd.

Problém se dá take jednoduše formulovat jako ILP a řešit solvery pro ILP.

 

 

Dost v tomto textu vychází z toho, že P != NP. Pokud dokážete opak, pak většina tohoto příspěvku neplatí a jsou z vás milionáři.

 

// Pozn. možná budu rozšiřovat

 

Edited by ffredyk
Vodjebanej bordel z názvu topicu - ještě jednou a ban
  • Smutný 1
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...