Lukasz 336 Odesláno: 11. Leden, 2021 Share Odesláno: 11. Leden, 2021 (upraveno) 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 12. Leden, 2021 by ffredyk Vodjebanej bordel z názvu topicu - ještě jednou a ban 1 Link to comment Share on other sites More sharing options...
Scydo 397 Odesláno: 11. Leden, 2021 Share Odesláno: 11. Leden, 2021 Takže, vlastně https://www.youtube.com/watch?v=eYZxdfbvXfQ ? Link to comment Share on other sites More sharing options...
Lukasz 336 Odesláno: 11. Leden, 2021 Author Share Odesláno: 11. Leden, 2021 Ano, je to jeden a ten stejny problem Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now