Problém cestujícího prodejce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. června 2022; kontroly vyžadují 7 úprav .

Problém cestujícího obchodníka (nebo TSP z anglického travel salesman problem ) je jedním z nejznámějších kombinatorických optimalizačních problémů , který spočívá v nalezení nejvýnosnější trasy procházející zadanými městy alespoň jednou a poté návratu do původního města. V podmínkách problému je uvedeno kritérium rentability trasy (nejkratší, nejlevnější, kumulativní kritérium atd.) a odpovídající matice vzdáleností, nákladů a podobně. Zpravidla je uvedeno, že trasa by měla procházet každým městem pouze jednou - v tomto případě se vybírá mezi hamiltonovskými cykly. Existuje několik speciálních případů obecné formulace problému, zejména geometrický problém obchodního cestujícího (nazývaný také rovinný nebo euklidovský, kdy matice vzdáleností odráží vzdálenosti mezi body v rovině), problém metrického obchodního cestujícího (když trojúhelníková nerovnost je splněna na matici nákladů ), symetrické a asymetrické problémy cestujícího obchodníka . Existuje také zobecnění problému, tzv. generalizovaný problém cestujícího obchodníka .

Příkaz optimalizačního problému patří do třídy NP-těžkých problémů, stejně jako většina jeho konkrétních případů. Verze „rozhodovacího problému“ (tj. taková, která se ptá, zda neexistuje cesta delší než daná hodnota k ) patří do třídy NP-úplných problémů . Problém obchodního cestujícího je jedním z transpočítačových problémů : i při relativně malém počtu měst (> 66) jej nelze vyřešit metodou výčtu možností žádnými teoreticky myslitelnými počítači v době kratší než několik miliard let.

Historie

S problémem obchodního cestujícího souvisí problém nalezení Hamiltonova cyklu . Příkladem takového problému je problém tahu rytíře známý minimálně od 18. století [1] . Leonhard Euler jí věnoval velké dílo „Řešení kuriózní otázky, která, jak se zdá, nepodléhá žádnému výzkumu“, z roku 1759 [2] . Dalším příkladem problému při hledání hamiltonovského cyklu je icosian : matematická hádanka, ve které musíte projít dvanáctistěn (graf s 20 uzly), který navštíví každý vrchol právě jednou. Tento problém navrhl William Hamilton v 19. století, definoval také třídu takových cest.

V roce 1832 vyšla kniha s názvem „Cestující prodavač – jak se má chovat a co má dělat, aby doručil zboží a byl úspěšný ve svých záležitostech – rady starého kurýra“ ( německy: Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein - von einem alten Commis-Voyageur ), který problém popisuje, ale k jeho řešení nepoužívá matematický aparát. Nabízí ale příklady tras pro některé regiony Německa a Švýcarska.

První zmínky o matematickém optimalizačním problému patří Carlu Mengerovi , který jej formuloval na matematickém kolokviu v roce 1930 takto:

Problémem poslů (protože tato otázka vyvstává u každého pošťáka, řeší ji především mnoho cestovatelů) nazýváme problém nalezení nejkratší cesty mezi konečnou množinou míst, jejichž vzdálenost je známa.

Brzy se objevil známý název problému obchodního cestujícího , který navrhl Hassler Whitney z Princetonské univerzity .

Spolu se snadností definice a relativní snadností hledání dobrých řešení je problém cestujícího prodejce odlišný v tom, že najít skutečně optimální cestu je poměrně obtížný úkol. Vzhledem k těmto vlastnostem, počínaje druhou polovinou 20. století, nemá studium problému obchodního cestujícího ani tak praktický význam, jako spíše teoretický, jako spíše model pro vývoj nových optimalizačních algoritmů.

Mnoho dnešních běžných metod diskrétní optimalizace , jako je cutoff , branch and bound , a různé varianty heuristických algoritmů, byly vyvinuty na příkladu problému cestujícího obchodníka.

V 50. a 60. letech 20. století přitahoval problém obchodního cestujícího pozornost vědců ve Spojených státech a v Evropě. Významný příspěvek ke studiu problému má George Danzig , Delbert Ray Fulkerson ( ing. Delbert Ray Fulkerson ) a Selmer Johnson ( ing. Selmer M. Johnson ), kteří v roce 1954 v institutu RAND Corporation formulovali problém ve formě diskrétního optimalizačního problému a aplikovaný na něj řešení cut-off metody . Touto metodou sestavili cestu obchodního cestujícího pro jeden konkrétní problém se 49 městy a doložili její optimálnost. V 60. a 70. letech se tímto problémem zabývalo mnoho vědců jak teoreticky, tak z hlediska jeho aplikací v informatice, ekonomii, chemii a biologii.

Richard Karp v roce 1972 prokázal NP-úplnost problému hledání hamiltonovských cest, což díky polynomiální redukovatelnosti implikovalo NP-tvrdost problému obchodního cestujícího. Na základě těchto vlastností dal teoretické zdůvodnění náročnosti hledání řešení problému v praxi.

Velkých úspěchů bylo dosaženo na konci 70. a 80. let, kdy Martin Grötschel ( německy Martin Grötschel ), Manfred Padberg ( německy Manfred Padberg ) a Giovanni Rinaldi ( italsky Giovanni Rinaldi ) a další pomocí nových metod dělení rovina, větve a hranice vypočítali řešení pro konkrétní případ problému s 2393 městy.

V devadesátých letech vytvořili rekordy programu Concorde David Applegate , Robert Bixby , Vašek Chvátal a William Cook . Gerhard Reinelt ( německy Gerhard Reinelt ) vytvořil TSPLIB - soubor standardizovaných příkladů problému obchodního cestujícího různého stupně složitosti pro porovnání výsledků práce různých skupin výzkumníků. V březnu 2005 byl programem Concord vyřešen problém s 33 810 uzly : byla vypočtena cesta o délce 66 048 945 a byla prokázána absence kratších cest. V dubnu 2006 bylo nalezeno řešení pro instanci s 85 900 uzly. Pomocí dekompozičních metod je možné vypočítat řešení pro případy problému s miliony uzlů, jejichž délka je o méně než 1 % větší než optimální.

Formální definice

Zobrazení grafu

Aby bylo možné použít matematický aparát k řešení problému, měl by být prezentován ve formě matematického modelu . Problém obchodního cestujícího lze znázornit jako model na grafu , tedy pomocí vrcholů a hran mezi nimi. Vrcholy grafu tedy odpovídají městům a hrany mezi vrcholy a odpovídají komunikačním cestám mezi těmito městy. Každá hrana může být spojena s kritériem ziskovosti trasy , které lze chápat jako například vzdálenost mezi městy, čas nebo náklady na cestu. $\left(i,j\right)$ $i$ $j$ $\left(i,j\right)$ $c_{ij}\geqslant 0$

Hamiltonovský cyklus je cesta, která obsahuje přesně jednou každý vrchol grafu.

Pro zjednodušení problému a zaručení existence cesty se obvykle předpokládá, že modelový graf problému je plně propojen , tedy že mezi libovolnou dvojicí vrcholů existuje hrana. V případech, kdy mezi jednotlivými městy není komunikace, lze toho dosáhnout zavedením hran s maximální délkou. Kvůli velké délce taková hrana nikdy nespadne do optimální trasy, pokud existuje.

Řešením problému obchodního cestujícího je tedy nalezení Hamiltonova cyklu minimální hmotnosti v kompletním váženém grafu.

V závislosti na tom, které kritérium ziskovosti trasy se porovnává s velikostí okrajů, existují různé verze problému, z nichž nejdůležitější jsou symetrické a metrické problémy.

Asymetrické a symetrické problémy

Obecně se problém asymetrického obchodního cestujícího liší v tom, že je modelován pomocí orientovaného grafu. Je tedy třeba zvážit, kterým směrem jsou hrany.

V případě symetrické úlohy mají všechny dvojice hran mezi stejnými vrcholy stejnou délku, to znamená, že délky hrany jsou stejné . V symetrickém případě je počet možných cest poloviční než v případě asymetrickém. Symetrický problém je modelován neorientovaným grafem (viz obrázek). $\left(i,j\right)$ $c_{ij}=c_{ji}$

Ve skutečnosti může být problém cestujícího prodejce v případě skutečných měst jak symetrický, tak asymetrický, v závislosti na délce nebo délce tras a na směru pohybu.

Metrický problém

Problém symetrického obchodního cestujícího se nazývá metrický , pokud je rovnost trojúhelníku splněna s ohledem na délky hran . Relativně řečeno, v takových problémech jsou objížďky delší než přímky, to znamená, že hrana od vrcholu k vrcholu není nikdy delší než cesta přes mezilehlý vrchol : $i$ $j$ $k$

c_{ij}\leqslant c_{ik}+c_{kj}

Tato vlastnost délky hrany definuje měřitelný prostor na sadě hran a míru vzdálenosti, která vyhovuje intuitivnímu chápání vzdálenosti.

Funkce vzdálenosti běžné v praxi jsou také metriky a splňují trojúhelníkovou nerovnost:

Euklidovská vzdálenost v euklidovském problému obchodního cestujícího,
Manhattanská metrika (také čtvrtletní) problému pravoúhlého cestujícího prodejce, ve kterém je vzdálenost mezi vrcholy na mřížce rovna součtu vzdáleností podél osy y a úsečky,
Maximální metrika , která definuje vzdálenost mezi vrcholy mřížkového grafu jako maximální hodnotu vzdálenosti podél ordináty a úsečky.

Poslední dvě metriky se používají například při vrtání děr do desek plošných spojů, kdy stroj musí udělat více děr za nejmenší čas a může pohybovat vrtákem v obou směrech, aby se pohyboval od jednoho otvoru k druhému. Manhattanská metrika odpovídá případu, kdy k pohybu v obou směrech dochází postupně, a maximum odpovídá případu, kdy k pohybu v obou směrech dochází synchronně, a celkový čas je roven maximální době pohybu podél osy pořadnice nebo úsečky.

Nemetrický problém obchodního cestujícího může nastat například v případě minimalizace doby pobytu za přítomnosti výběru vozidel v různých směrech. V takovém případě může být objížďka letecky kratší než přímý spoj autem.

Pokud je v praxi za podmínek problému povoleno vícekrát navštívit města, pak lze symetrický problém zredukovat na metrický. K tomu je problém uvažován na takzvaném grafu vzdálenosti. Tento graf má stejnou sadu vrcholů jako původní a je plně propojen. Délka hran mezi vrcholy a na grafu vzdálenosti odpovídá délce nejkratší vzdálenosti mezi vrcholy a v původním grafu. Pro takto definované délky trojúhelníková nerovnost platí a každá trasa na grafu vzdálenosti vždy odpovídá trase s možným opakováním vrcholů v původním grafu. $c_{ij}$ $i$ $j$ $i$ $j$ $c_{ij}$

Formulace jako diskrétní optimalizační problém

Jedním z přístupů k řešení problému je formulovat jej jako diskrétní optimalizační problém, přičemž řešení jsou reprezentována jako proměnné a souvislosti jako vztahy nerovnosti mezi nimi. Možností je tedy několik. Například symetrický problém může být reprezentován jako množina hran . Každé hraně je přiřazena binární proměnná rovná 1, pokud hrana patří do trasy, a 0 v opačném případě. Libovolná trasa může být reprezentována jako hodnoty sady proměnných členství, ale ne každá taková sada trasu definuje. Podmínkou, že hodnoty množiny proměnných určují trasu, jsou níže popsané lineární nerovnosti. $PROTI$ $\{i,j\}$ $x_{ij}\in \{0,1\}$

Každý vrchol musí komunikovat přes pár hran se zbytkem vrcholů, tedy přes vstupní a výstupní hrany:

\forall i\in V,\;\součet _{j\in V\setminus \{i\}}x_{ij}=2\qquad (1)

Celkově je každý výraz roven buď 1 (patří do trasy) nebo 0 (nepatří). To znamená, že výsledný součet se rovná počtu hran v trase, které mají vrchol na jednom z konců. Je roven 2, protože každý vrchol má vstupní a výstupní hranu. Na sousedním obrázku je vrchol zobrazen se vstupními a výstupními hranami a okraje trasy jsou znázorněny jako tlusté čáry. Vedle žeber jsou délky aplikované na výše uvedenou částku. $x_{ij}$ $i$ $i$ $x_{ij}$

Výše popsané podmínky násobnosti splňují nejen trasy, ale také hodnoty proměnných odpovídajících jednotlivým cyklům, kde každý vrchol patří pouze jednomu cyklu (viz obrázek). Aby se takovým případům předešlo , musí být splněny tzv. smyčkové nerovnosti (neboli podmínky eliminace podcesty), které definovali Danzig, Fulkerson a Johnson v roce 1954 pod názvem loop conditions . Tyto nerovnosti definovaly další podmínku, že každá sada vrcholů je buď prázdná, nebo obsahuje všechny vrcholy v kombinaci se zbytkem vrcholů přes alespoň dvě hrany: $S\podmnožina V$

\sum _{i\in S,\;j\notin S}x_{ij}\geqslant 2\qquad (2)

pro všechny množiny vrcholů , kde . Tento součet se rovná součtu délek hran cest mezi vrcholem a vrcholem . Abychom odstranili zbytečné nerovnosti, můžeme se omezit na množiny vrcholů s minimálně dvěma a maximálně vrcholy. Na obrázku vedle jsou tlustými čarami vyznačeny hrany s délkami , zbývající hrany mají délku . Zavedení dalších podmínek (2) pro množinu vrcholů , sestávající ze tří levých vrcholů, zajistí, že bude kombinována přes alespoň dvě hrany cesty se třemi vrcholy napravo, aby se eliminovaly oba cykly. Počet nerovností eliminujících cyklus podle Danziga, Fulkersona a Johnsona je . $S$ $1\leqslant |S|\leqslant |V|-1$ $i\v S$ $j\notin S$ $S$ $|V|-2$ $\{i,j\}$ $x_{ij}=1$ $x_{ij}=0$ $S$ $S$ $2^{n}-2(n-1)$

V roce 1960 Miller, Tucker a Zemlin vymysleli alternativní podmínky pro eliminaci podtras zavedením nových proměnných specifikujících pořadí navštívených měst, které vyžadovaly pouze další nerovnosti. Navíc kvůli dualitě ve formulacích Millera, Tuckera a Zemlina zůstává problém obchodního cestujícího NP-těžký. $n$ $n^{2}-n+1$ $x_{ij}$

Každý vektor s prvky rovnými 0 a 1, který splňuje všechny nerovnosti, tedy definuje správnou trasu, která je řešením přeformulovaného problému obchodního cestujícího: vypočítat

\min \;\left\{\součet _{i\in V}\součet _{j\in V\setminus \{i\}}c_{ij}x_{ij}\;|\;x{\mbox { platné (1) (2),}}\;x_{ij}\in \{0,1\}\right\}.\qquad (3)

Protože proměnné mají pouze hodnoty 0 a 1, součet se rovná celkové délce hran patřících k trase. $x_{ij}$ $c_{ij}$ $\{i,j\}$

Počet nerovností typu (2) roste exponenciálně s rostoucím počtem měst, protože téměř každá podmnožina uzlů definuje jednu nerovnost. Tento problém lze vyřešit aplikací metody ořezové roviny , díky které se nerovnosti sčítají pouze tehdy, když jsou tyto nerovnosti skutečně potřeba. Z geometrického hlediska lze lineární nerovnosti reprezentovat jako nadroviny v prostoru proměnných. Množina vektorů splňujících tyto nerovnosti tvoří polytop (vícerozměrný mnohostěn), neboli vícerozměrný mnohoúhelník, v takovém prostoru je přesný tvar určen délkami a většinou je neznámý. Lze však ukázat, že podmínky (1) a (2) určují plochy (fasetu) polytopu, tedy boční plochy polytopu s nejvyšším rozměrem. Proto patří mezi nejsilnější lineární nerovnosti, které mohou trasu popsat. Existuje také mnoho různých aspektů definovaných nerovnostmi známými pouze v několika případech. Přestože (1) a (2) spolu s omezeními kompletně modelují problém pouze pro binární vektory, lze tyto nerovnosti použít v metodě větvení a vazeb k vyřazení řešení lineárními optimalizačními metodami s neceločíselnými souřadnicemi (viz část přesné metody níže). $2^{|V|}$ $c_{ij}$

Algoritmická složitost

Vzhledem k tomu, že obchodní cestující v každém městě stojí před volbou dalšího města z těch, které ještě nenavštívil, existují trasy pro asymetrický problém a trasy pro problém symetrického obchodního cestujícího. Velikost vyhledávacího prostoru tedy závisí faktoriálně na počtu měst. $(n-1)!$ $(n-1)!/2$

Různé verze problému obchodního cestujícího (metrické, symetrické a asymetrické) jsou NP-ekvivalentní. Podle běžné, ale neprokázané domněnky o nerovnosti tříd složitosti P a NP neexistuje žádný deterministický Turingův stroj , který by byl schopen řešit problémové instance v polynomiálním čase v závislosti na počtu měst.

Je také známo, že za podmínky neexistuje žádný algoritmus, který by pro nějaký polynom vypočítal taková řešení problému obchodního cestujícího, která by se lišila od optimálního maxima faktorem . $P\neq NP$ $p$ $2^{p(n)}$

V praxi není vždy nutné hledat striktně optimální trasu. Existují algoritmy pro nalezení přibližných řešení metrické úlohy v polynomiálním čase a nalezení cesty, která je maximálně dvakrát delší než ta optimální. Dosud není znám žádný polynomiální časový algoritmus, který by zaručoval přesnost lepší než 1,5 optimální. Za předpokladu existuje (neznámá) konstanta , takže žádný polynomiální algoritmus nemůže zaručit přesnost . Jak ukázal Arora, pro euklidovský problém obchodního cestujícího existuje polynomiální časové schéma PTAS pro nalezení přibližného řešení. $P\neq NP$ $c>0$ $1+c$

Kromě toho mohou mít data funkce, které mohou pomoci vyřešit problém. Například města se nenacházejí náhodou, ale podle terénu, nebo dokonce podél optimální obchodní cesty, která se již dávno našla. Další informace a heuristika nám umožňují najít přijatelná řešení v rozumném čase.

Uzavřené a otevřené varianty problému

V uzavřené verzi problému cestujícího prodejce je nutné navštívit všechny vrcholy grafu a poté se vrátit k původnímu vrcholu. Otevřená varianta se od uzavřené liší tím, že nevyžaduje návrat do výchozího vrcholu.

Otevřená verze problému je redukována na uzavřenou tím, že se váhy oblouků obsažených v počátečním vrcholu nahradí číslem 0. Optimální uzavřená trasa obchodního cestujícího v takovém grafu odpovídá optimální otevřené trase v původním grafu.

Chcete-li zmenšit uzavřenou variantu na neuzavřenou, je nutné určit číslo striktně převyšující váhu jakékoli cesty obchodního cestujícího v daném grafu (například můžete vzít součet maximálních váhových oblouků vycházejících z každého vrcholu , zvýšené o 1). Poté je potřeba do grafu přidat nový vrchol (předpokládáme, že vrcholy původního grafu jsou očíslovány od 0 do , zatímco počáteční vrchol má číslo 0). Náklady na oblouky opouštějící vrchol a vstup do něj jsou definovány takto: $K$ $K$ $v_{n}$ $n-1$ $v_{n}$

$c_{n,i}=3K$
$c_{0,n}=3K$
$c_{i,n}=c_{i,0}+2 tis$ v od do $i$ $jeden$ $n-1$

Optimální neuzavřená trasa obchodního cestujícího v takovém grafu odpovídá optimální uzavřené trase obchodního cestujícího v původním grafu a má vyšší náklady. $2K$

Metody řešení

Prvoci

vyčerpávající hledání
náhodný výčet
chamtivé algoritmy
- metoda nejbližšího souseda
- metoda začlenění nejbližšího města
- metoda nejnižších nákladů
metoda minimálního kostrového stromu
metoda simulovaného žíhání

Všechny efektivní (snížení plného výčtu) metody pro řešení problému obchodního cestujícího jsou heuristické metody . Většina heuristických metod nenachází nejúčinnější cestu, ale přibližné řešení . Často jsou požadovány takzvané algoritmy pro libovolný čas .[ upřesnit ] , tedy postupné vylepšování nějakého současného přibližného řešení.

Příkladem nejjednodušší metody řešení metrické verze úlohy je použití minimálních kostry, které dává řešení s aproximačním faktorem a má časovou složitost . Myšlenka je taková, že každý připojený graf obsahuje pro svůj podgraf nižší prahovou hodnotu nákladů, minimální kostru, a že každý cyklus, který navštíví každý vrchol grafu alespoň jednou, lze pomocí metriky převést na nákladově optimální trasu: $2$ $O(n^{2}\log n)$

Najděte minimální kostru grafu . $T$ $G$
Vytvořte graf zdvojnásobením všech hran v . Takže všechny vrcholy v mají sudý počet hran. $T'$ $T$ $T'$
Najděte Eulerův cyklus . $T'$ $C'$
Zmenšit , přeskakovat zdvojené hrany, získat cyklus . $C'$ $C$
Vynést . $C$

Hodnota aproximačního faktoru je dokázána následovně: Nechť - minimální kostra, - stejný strom, ale se zdvojenými hranami, - Eulerův cyklus na grafu , - výsledek algoritmu, - minimální trasa. Všimněte si, že stejně jako . Pak je aproximační faktor . $T$ $T'$ $C'$ $T'$ $C$ $C^{*}$ $c(T)\leqslant c(C^{*}-e)\leqslant c(C^{*})$ $c(C)\leqslant c(C')=2\cdot c(T)$ ${\frac {C}{C^{*}}}\leqslant {\frac {2\cdot c(T)}{c(C^{*})))\leqslant {\frac {2\ cdot c(C^{*})}{c(C^{*})}}=2$

Výše uvedený způsob však lze optimalizovat zvýšením počtu hran ve vrcholech s lichým počtem sousedů o 1, což odpovídá odpovídajícím "lichým" vrcholům. Je důležité poznamenat, že počet "lichých" vrcholů je vždy sudý na základě lemmatu handshake . V takovém případě má optimalizovaný algoritmus aproximační faktor a časovou složitost . Před důkazem si ukažme, že , kde je shoda a je optimální cesta: Nechť je množina "lichých" vrcholů minimální kostry a je cyklus získaný z přeskakování vrcholů . Je zřejmé, že má sudou délku a také dvě neprotínající se maximální shody a , pro které a . Z toho vyplývá , že a tedy . Na základě toho zjistíme aproximační faktor algoritmu: . $3/2$ $O(n^{3})$ $c(M)\leqslant c(C^{*})/2$ $M$ $C^{*}$ $U$ $T$ $C''$ $C^{*}$ $V\setminus U$ $C''$ $M_{1}$ $M_{2}$ $c(M)\leqslant c(M_{1})$ $c(M)\leqslant c(M_{2})$ $2\cdot c(M)\leqslant c(M_{1})+c(M_{2})=c(C'')\leqslant c(C^{*})$ $c(M)\leqslant c(C^{*})/2$ ${\frac {c(C)}{c(C^{*})}}\leqslant {\frac {c(T)+c(M)}{c(C^{*})}} \leqslant {\frac {c(C^{*})+c(C^{*})/2}{c(C^{*})}}\leqslant {\frac {1.5\cdot c(C^ {*})}{c(C^{*})}}=1,5$

Existují také nastavení, ve kterých se problém cestujícího prodejce stává NP-complete . Obvykle taková prohlášení vypadají takto: existuje na daném grafu G taková prohlídka , že její cena nepřesáhne x . Často se na něm testují nové přístupy k heuristické redukci vyčerpávajícího vyhledávání .

V praxi se používají různé modifikace efektivnějších metod: metoda větvené a vázané a metoda genetických algoritmů a také algoritmus mravenčích kolonií .

Metoda větvení a vazby

Je možné najít přesné řešení problému obchodního cestujícího, tedy „ručně“ spočítat délky všech možných tras a vybrat trasu s nejmenší délkou. I pro malý počet měst je však prakticky nemožné problém takto vyřešit. Pro jednoduchou variantu, symetrický problém s městy, jsou možné trasy, to znamená, že pro 15 měst je 43 miliard tras a pro 18 měst už 177 bilionů. Jak rychle roste trvání výpočtů, lze ukázat na následujícím příkladu. Pokud by existovalo zařízení, které by dokázalo najít řešení pro 30 měst za hodinu, dvě další města by trvala tisíckrát déle; tedy více než 40 dní. $n$ $(n-1)!/2$

Diskrétní optimalizační metody, zejména větvené a vázané metody, umožňují nalézt optimální nebo přibližná řešení pro dostatečně velké problémy.

V geometrické interpretaci tyto metody řeší problém jako konvexní polytop, tedy vícerozměrný mnohoúhelník v jednotkové krychli , kde se rovná počtu hran v grafu. Každý vrchol této jednotkové krychle odpovídá trase, tedy vektoru s prvky 0/1, který splňuje výše popsané lineární nerovnosti. Nadroviny popsané těmito nerovnostmi oříznou ty hrany jednotkové krychle, které neodpovídají žádné trase. $m$ $[0,1]^{m}$ $m$

Na sousedním obrázku je znázorněno použití metody pro problém se třemi uzly. V souladu se třemi možnými hranami mezi vrcholy se porovnávají binární proměnné a . V tomto případě existuje pouze jedna možná trasa, a to ta, která prochází třemi vrcholy. Tato trasa splňuje nerovnost , která říká, že trasa musí procházet alespoň dvěma vrcholy. Kromě této cesty, která odpovídá vektoru (1,1,1), splňují nerovnosti i všechny body v červeně označené části této nerovnosti. Roviny procházející červenými čarami odříznou všechny rohy odpovídající neexistujícím cestám s nejvýše jednou hranou, a to nulovým vektorem (0, 0, 0), jednotkovými vektory (1, 0, 0), (0, 1, 0) a (0, 0, 1). Silná nerovnost odřízne z jednotkové kostky vše, kromě jediného platného bodu (1, 1, 1). V tomto konkrétním případě lze stejného účinku dosáhnout třemi nerovnostmi typu (1). $x_{1},\,x_{2}$ $x_{3}$ $x_{1}+x_{2}+x_{3}\geqslant 2$ $x_{1}+x_{2}+x_{3}\geqslant 3$

Chcete-li určit přípustnou hranu s nejmenší délkou, měli byste vyřešit sady lineárních optimalizačních problémů, které odříznou nepotřebné části jednotkové krychle řezáním rovin, a pokusit se rozdělit jednotkovou krychli na menší polytopy pomocí metody větvení a vazby.

Tato metoda však obvykle nestačí k rychlému nalezení tras. Hlavní výhodou exaktních metod je, že při dostatku času vypočítají nejkratší trasu. Díky spodní hranici pro optimální řešení lze odhadnout, jak moc se nalezená trasa liší od optimální. Například když má dolní hranici 100 a po nalezení trasy délky 102 může být optimální trasa mezi 100 a 102. Takzvaný interval optimality neboli maximální relativní vzdálenost mezi délkou optimální trasy a nejkratší známá trasa, bude (102 - 100) /100 = 2 %, to znamená, že délka nalezené trasy 102 se liší maximálně o 2 % od optimální. Když je délka vypočítané trasy rovna délce předchozí, má se za to, že nalezené řešení je optimální. Pro nalezení tras přijatelné délky lze přesné metody kombinovat s heuristickými.

Metoda větví a vazeb pro řešení problému obchodního cestujícího byla navržena v roce 1963 skupinou autorů (J. Little, K. Murty, D. Sweeney, K. Carol) [3] .

Metoda elastické sítě

Historie

V roce 1987 jej použili Durbin a Willshaw, kteří poukázali na analogii s mechanismy pro navazování uspořádaných neuronových spojení [4] .

Každá z tras obchodního cestujícího byla považována za mapování kruhu na rovinu (některý bod tohoto kruhu je mapován ke každému městu v letadle). Sousední body na kružnici by měly být mapovány na body, pokud je to možné, nejbližší a v rovině.

Algoritmus

Začíná to instalací malého kruhu na letadlo. Nerovnoměrně se rozšiřuje a stává se prstencem, který prochází téměř všemi městy a vytváří tak požadovanou trasu. Každý pohybující se bod prstence je ovlivněn dvěma složkami: posunutím bodu směrem k nejbližšímu městu a posunutím směrem k sousedům bodu na prstenci tak, aby se zkrátila jeho délka. Město se nakonec při rozšiřování napojí na určitou část okruhu. Jak se taková elastická síť rozšiřuje, každé město je spojeno s určitou částí prstence.

Na začátku mají všechna města přibližně stejný vliv na každý průjezdní bod. Následně se větší vzdálenosti stávají méně vlivnými a každé město se stává specifičtějším pro body prstence, které jsou mu nejblíže. Toto postupné zvyšování specifičnosti, které připomíná metodu učení sítě Kohonen, je řízeno hodnotou nějakého efektivního poloměru.

Durbin a Willshaw ukázali, že pro problém 30 měst, který uvažovali Hopfield a Tank, metoda elastické sítě generuje nejkratší trasu v asi 1000 iteracích. U 100 měst byla trasa nalezená touto metodou pouze o 1 % vyšší než optimální.

Ant algoritmus

Genetický algoritmus

Algoritmus dynamického programování

Hlavní myšlenkou je vypočítat a uložit cestu z původního města do každého z dalších měst, pak tuto hodnotu sečíst s cestou z každého z ostatních měst do zbývajících měst atd. Výhodou této metody oproti brutálnímu silovou metodou je výrazné snížení výpočtů celkového objemu v důsledku znatelného zvýšení množství paměti [5] . $D$ $F$ ${\displaystyle P_{D}=(6n-1)-n2^{n-1}+4n(n-1)2^{n-2},P_{F}=n!\přibližně n^{n} e^{-n}{\sqrt {2\pi n)),P_{D}\ll P_{F))$ $Q_{D}\sim 2^{n}{\sqrt {\frac {2n}{\pi }}},Q_{F}=2,Q_{D}\gg Q_{F}$

Viz také

Poznámky

↑ Gross JL, Yellen J. Teorie grafů a její aplikace, 2006 , str. 275.
↑ Euler, Leonhard, Solution d'une question curieuse que ne paroit soumise à aucune analysis Archivováno 19. srpna 2021 na Wayback Machine , Mémoires de l'académie des sciences de Berlin, 15 (1759) 1766, s. 310-337.
↑ Kostevich L. S. Matematické programování: Inform. technologie optimálních řešení: Proc. příspěvek / L. S. Kostevich. - Minsk: Nové poznatky, 2003. il., s. 150, ISBN 985-6516-83-8
↑ Richard Durbin, David Willshaw. Analogový přístup k problému obchodního cestujícího pomocí metody elastické sítě // Nature . — 1987-04-22. — Sv. 326 , iss. 6114 . — S. 689–691 . - doi : 10.1038/326689a0 . Archivováno z originálu 23. dubna 2016.
↑ Korbut A. A., Finkelstein Yu. Yu. Diskrétní programování. - M., Nauka, 1969. - C. 258-264

Literatura

Levitin A. V. Kapitola 3. Metoda hrubé síly: Problém cestujícího obchodníka // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 159-160. — 576 s. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmy: konstrukce a analýza = Úvod do algoritmů. - 2. vyd. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .
V A. Moudrý. Problém cestujícího prodejce . - M .: "Znalosti" , 1969. - S. 62.
Ezhov A., Shumsky S. Neurocomputing a jeho aplikace v ekonomii a podnikání . - M .: MEPhI , 1998. - S. 216.
Gross JL, Yellen J. Teorie grafů a její aplikace. druhé vydání. Boca Raton – Londýn – New York: Chapman & Hall/CRC, 2006.

NP-úplné problémy
Maximalizační problém stohování (balení)	Balení v kontejnerech dvourozměrné balení lineární balení balení podle hmotnosti balení podle hodnoty Problém s batohem
teorie grafů teorie množin	Problém s krytím vertexu Klikněte na problém Problém nezávislé množiny (množiny) Nastavit problém s krytím Steinerův problém Problém cestujícího prodejce Obecný problém cestujícího prodejce
Algoritmické problémy	Problém splnitelnosti pro booleovské vzorce (v konjunktivní normální formě)
Logické hry a hádanky	Generalizované značky (hra v N 2 -1) problém s nejkratším řešením Problémy, jejichž řešení jsou aplikována v Tetrisu Generalizovaný problém sudoku Problém vyplňování latinského čtverce Kakurův úkol
Třídy obtížnosti Operační výzkum Optimalizace Kombinatorická optimalizace Aplikovaná matematika Teorie algoritmů Dynamické programování 21 NP-úplný Karp problém