Проблем трговачког путника

Проблем трговачког путника поставља следеће питање: С обзиром на списак градова и даљина између сваког пара градова, који је најкраћи могући пут да се посети сваки град тачно једном и врати се у почетни град? То је НП-тешки проблем проблем комбинаторне оптимизације, важно у Операционим истраживањима и Теоретском рачунарству.

Проблем је први пут формулисан у 1930. године и један је од најинтезивнијих проблема у оптимизацији. Користи се као репер за многе методе оптимизације. Иако је проблем рачунски тежи, велики број хеуристичких и методе су познате, тако да су неки случајеви са десетинама хиљада градова бити решени.

ТСП има неколико апликација још у својој формулацији, као што су планирање, логистика, а производња микрочипови. Мало измењена, изгледа као под-проблем у многим областима, као што су ДНК секвенцирање. У овим апликацијама, концепт град представља, на пример, купци, лемљење тачкама, или фрагмената ДНК, а концепт дистанца представља путовање пута или трошак или сличност између фрагмената ДНК. У многим апликацијама, додатна ограничења, као што су ограничени ресурси или временски прозори који су знатно тежи. ТСП је специјални случај Проблем трговачког путника.

У Теорији комплексности, одлука верзија ТСП (где је, с обзиром на дужину L, задатак је да одлучи да ли код графа је постојало путовање краће од L) припада класи НП-комплетних проблема. Дакле, врло је вероватно да Најбољи, најгори и просечан случај време извршавања једног алгоритма за ТСП експоненцијалног раста са бројем градова.

Историја

Вилијам Рован Хамилтон

Проблем порекла трговачког путника је нејасан. Приручник трговачког путника од 1832. године, помиње проблем и обухвата туре кроз примере Немачке и Швајцарске, али не садржи математички третман "Дер Хандлунгсреисенде - Вие ер Сеин унд солл био ер зу Тун {сиц шешир, ум Ауфтраге зу ерхалтен унд еинес глуцклицхен Ерфолгс у Сеинен магазинов ГЕВИСС зу сеин - вон еинем Алтен коми-Воиагеур " (трговачки путник - како он мора да буде и шта треба да уради како би били сигурни да обавља своје задатке и имају успеха у његовом бизнис - од високе ко-Воиагеур) трговачки путник Проблем је дефинисан у 1800. год., од Ирског математичара ВР Хамилтон и од стране британског математичар Томас Киркман. Хамилтонова Ицосиан игре је рекреативна слагалица заснована на проналажењу Хамилтоновог пута дискусија почетком рада Хамилтон и Киркман могу се наћи у Грапх Тхеори 1736-1936 општи облик ТСП изгледа. Да има је прво студирао математичари током 1930-их година у Бечу и на Харварду, нарочито од стране Карл Менгер, који дефинише проблем, сматра да је очигледно бруте-форце алгоритма, и посматра не-оптималност најближег суседа хеуристике: {{ Понуда | Ћемо означити по гласника проблемом (јер се у пракси ово питање треба да се реши сваки поштар, у сваком случају и многи путници) задатак да пронађе, за коначно много бодова чији Паирвисе растојања су позната, најкраћи пут који повезује тачке. Наравно, овај проблем је решив од коначно много суђења. Правила којима би се број суђења испод број пермутација од датих тачака, нису позната. Правило да се прво иде од почетне тачке до најближе тачке, затим до тачке затварања.

Проблем трговачког путника је дефинисан у 1800. године, од стране Ирског математичара Вилијам Роуан-а Хамилтон-а и од стране Британског математичара Томас-а Киркман-а. Хамилтонова Ицосиан игре је рекреативна слагалица заснована на проналажењу Хамилтоновог циклуса, дискусија почетком рада Хамилтон-а и Киркман-а могу се наћи у Теорији графова 1736-1936 општи облик ТСП изгледа. Да има је прво студирао математичари током 1930-их година у Бечу и на Харварду, нарочито од стране Карл Менгер-а, који дефинише проблем, сматра да је очигледно бруте-форце алгоритма, и посматра не-оптималност најближег суседа хеуристике. Задатак да пронађе, за коначно много бодова чији Паирвисе растојања су познати, најкраћи пут који повезује тачке. Наравно, овај проблем је решив од коначно много суђења. Правила која би се број суђења испод броја пермутација од датих тачака, нису познати. Правило да се прво иде од почетне тачке до најближе тачке, затим до тачке најближе њој, итд, уопште не даје најкраћи пут. Цитед и енглески превод Оригинални Немачки: "Вир безеицхнен алс Ботенпроблем' (Веил Диесе Захтевај у вон дер Пракис једем Постботен, убригенс ауцх зу од виелен Реисенден лосен ист) умрети Ауфгабе, фур Ендлицх виеле Пункте, Дерен паарвеисе Абстанде беканнт Синд, Ден курзестен Дие точки вербинденден Вег зу финден. Диесес Проблем ист Натурлицх стетс дурцх Ендлицх Виеле Версуцхе лосбар. Правила, велцхе Дие Количество Версуцхе унтер дие Количество Пермутатионен дер гегебенен Пункте херунтердруцкен вурден, синд ницхт беканнт. Дие Регел, човек Солле вом Аусгангспункт предходно зум нацхстгелег.

Током 1950-их и 1960-их, проблем је постао веома популаран у научним круговима у Европи и САД. Значајни допринос дали су Џорџ Дантзиг, Делберт Реј Фулкерсон и Селмер M. Јохнсон у РАНД Цорпоратион у Санта Моникци, који је изразио проблем као цео број линеарни програма и развио сечење, метод за његово решавање. Са овим новим методама су решени инстанцу са 49 градова у оптималности наредним деценијама, проблем је проучавана од стране многих истраживача из области Математике, информатике, хемије, физике, и друге науке. Ричард M. Карп показао је 1972. год. да Хамилтонов циклус проблем НП-комплетан, што подразумева Нп тежак проблем. Ово испоручује математички објашњење очигледним рачунарском тешкоће у проналажењу оптималних решења. Велики напредак је направљен крајем 1970-их и 1980-их, када Гротсцхел, Падберг, Риналди и други успели да тачно реши случајеве у градовима до 2392, коришћењем најновије авионе и филијала-и-везан. У 1990, Апплегате, Бикби, Вашек Цхватал-а и Вилијам-а Ј. Цоок развија програм Конкорд, који се користи у многим решењима. Герхард Реинелт објавила ТСПЛИБ 1991, колекцију бенчмарк случајева различите тежине, која је у употреби од стране многих истраживачких група за поређење резултата. У 2006. год., Кук и други израчунава оптималану турнеју кроз 85,900 градском пример дао микрочипом распоред проблема, тренутно највећи решен ТСПЛИБ инстанце. За многе друге случајеве са милионима градова, решење се може наћи да се гарантује да се у року од 1% од оптималне турнеје.

Опис

Проблем графа

Симетрична ТСП са четири града

ТСП је моделован као [неусмерен граф] ], тако да су графови графикон темена, стазе су на графикону је ивице, а пут ' , а удаљеност је ивица дужине. То је проблем минимизације почиње и завршава се у одређеном после посете једни друге тачно једном. Често, модел је комплетан граф (тј.' сваки пару чворова повезаних ивица). Ако не постоји пут између два графа, додајући произвољно ивица ће завршити граф без утицаја на оптималну турнеју.

Асиметричност и Симетричност

Симетрични ТСП је растојање између два града је иста у сваком супротном смеру, стварајући неусмереним графом. Ова симетрија преполови број од могућих решења. У асиметричне ТСП, путеви не могу да постоје у оба смера или раздаљине могу бити различите, формирајући усмерени граф. Авио карте за градове са различитим поласка и доласка накнаде су примери како ова симетрија може разбити.

Поставка проблема

Ако је дат одређен број градова, цене путовања од било ког града до било ког града, која је најјефтинија рута која обилази сваки град тачно једном, и враћа се у почетни град? Еквивалентан проблем изражен у терминима теорије графова би гласио: Дат је комплетан тежински граф (чији чворови представљају градове, гране представљају путеве, а тежине представљају цену путовања, или дужину пута) - наћи Хамилтонов циклус најмање тежине. Може се показати да захтев да се врати у почетни град не мења рачунску комплексност овог проблема. Решење овог проблема је од великог практичног значаја, не само у питању саобраћаја. Добар пример у коме је битно на ефикасан начин решити Проблем трговачког путника би могла да буде организација теретне луке: Ако се у луци у сваком тренутку налази више хиљада контејнера, наслаганих једни на друге, и свакодневно се стотине контејнера искрцавају са бродова, или товаре на шлепере, који је оптималан редослед кретања кранова за утовар и истовар, и где поставити који контејнер.

ИЛП формулацију

ТСП се може формулисати као целобројно програмирање.

${\begin{aligned}\min &\sum _{i\neq j}c_{ij}x_{ij}&\\0\leq &x_{ij}\leq 1&\forall i,j\\&x_{i,j}{\text{ ceo broj}}&\forall i,j\\&\sum _{i=0,i\neq j}^{n}x_{ij}=1&j=0,\ldots ,n\\&\sum _{j=0,j\neq i}^{n}x_{ij}=1&i=1,\ldots ,n\\u_{i}-u_{j}&+nx_{ij}\leq n-1&1\leq i\neq j\leq n\\u_{i}\geq 0&&1\leq i\leq n.\end{aligned}}$

I наведеном формулацијом, $c_{ij}$ одговара удаљености између градова $i$ анд $j$ анд $x_{ij}$ означава да ли је пут од града и до града ј је укључен у турнеји. Последња препрека намеће да постоји само једна тура. Да бисмо то доказали, мора се доказати да је (1) свако могуће решење је турнеја и (2) да за сваку могућем турнеју, постоје вредности за $u_{i}$ тхат сатисфy тхе цонстраинтс. Да би доказао да је сваки изводљиво решење турнеје, довољно је показати да је сваки субтоур у прихватљивом решењу пролази кроз град 0 јер то имплицира да може да постоји само једна тура која обухвата све градове. Да бисмо то доказали, претпоставимо низ градова $i_{1},\ldots ,i_{k}$ формира субтоур који не укључује Сити 0. Сумирајући одговарајућа ограничења за ове графове,

${\begin{aligned}u_{i_{j}}-u_{i_{j+1}}+n&\leq n-1\qquad j=1,\ldots ,k-1\\u_{i_{k}}-u_{i_{1}}+n&\leq n-1\end{aligned}}$

даје

$kn\leq kn-k,$

што је контрадикција. Дакле, сваки субтоур у прихватљивом решењу пролази кроз граф и тако сваки 0 изводљиво решење. Сада мора да се покаже да за сваку могућу туру постоје вредности за $u_{i}$који задовољавају ограничења. Нека редоследа градова $i_{0},\ldots ,i_{n}$ бити нека $u_{i_{t}}=t$ фор $t=0,\ldots ,n$. онда је $x_{i_{j},i_{k}}=0$,

$u_{i_{j}}-u_{i_{k}}\leq n-1,$

која има осим у случају $u_{i_{j}}=n$ и $u_{i_{k}}=0$. Међутим, овај случај се искључује јер је пут од графа $i_{n}$ то цитy $i_{0}$ ис ин тхе тоур. Иф $x_{i_{j},i_{k}}=1$, онда мора бити задовољан

$u_{i_{j}}-u_{i_{k}}+n\leq n-1.$

То важи, јер $x_{i_{j},i_{k}}=1$ онлy иф $i_{j}$ анд $i_{k}$ узастопни су графови (анд $i_{j}\neq n,i_{k}\neq 0$) и онда $u_{i_{j}}-u_{i_{k}}=-1$.

Цомпутинг решење

Традиционалне линије напада за НП-тешких проблема су следећи: . * Израда алгоритама за тражење тачне решења (они ће радити разумно брзо само за мали проблем величине) * Израда хеуристицког алгоритма , односно, алгоритми који пружају било наизглед или вероватно добра решења, али која не може да се показао као оптималан. * Проналажење посебне случајеве за проблем ("субпроблемс") за које је био бољи или тачан хеуристике су могуће.

Сложеност израчунавања

Проблем је показала да је НП-тежак (прецизније, то је потпуна и због комплексности класе ФПНП), а проблем одлучивања верзија ("с обзиром на трошкове и број к, одлучити да ли постоји тура пут јефтиније од к ") је НП-комплетан. Уско грло проблем трговачког путника је НП-тежак. Проблем остаје НП-тежак чак и за случај када су градови су у равни са Еуклидских удаљеностима, као и у бројним другим случајевима рестриктивне. Уклањање стање посети сваки град "само једном" не уклони НП-тврдоће, јер се лако може видети да је у планарна случају постоји оптималан турнеје која посећује сваки град само једном (иначе, по троугао неједнакост, пречица која прескаче понављањем посету не би повећање дужине турнеје).

Сложеност апроксимације

У општем случају, проналажење најкраће трговачког путника турнеју је НПО-комплетан. Ако је удаљеност мера метрички и симетрични, проблем постаје АПКС-комплетан и Цхристофидес алгоритам је приближан у 1.5.

Ако су растојања ограничена на 1 и 2 (али и даље су метричка) апроксимација однос постаје 7/6. У случају асиметричне, метрички случај, познати су само логаритамске перформансе гаранције, најбољи тренутни алгоритам постиже однос перформансе 0,814 лог н, то је отворено питање да ли постоји стални фактор апроксимација.

Одговарајући максимизација проблем налажења најдужих трговачког путника је апроксимирати турнеју у 63/38. Ако растојање функција је симетрична, најдужа турнеја може апроксимирати у 4/3 од детерминистички алгоритам $(33+\epsilon )/25$ од случајног алгоритма.

Тачни алгоритми

Најдиректније решење би било да пробате све пермутације (поређани комбинације) и видели који је најјефтинији (користећи бруталну силу претрагу). Време извршавања овог приступа лежи у полинома фактора $O(n!)$, броја градова, тако да је ово решење постаје непрактично и за само 20 градова. Једна од првих примена динамичког програмирања је Хелд-Карп алгоритам који решава проблем на време $O(n^{2}2^{n})$ од случајног алгоритма.

[[Датотека:Брутефорце.гиф|фрамед|центер|

Решење на ТСП са 7 градова који користе бруталну силу претрагу. Напомена: Број пермутација: (7-1)!/2 = 360

Динамичко програмирање решење захтева експоненцијални простор. Коришћење укључивања у искључености, проблем се може решити на време у оквиру полинома фактор $2^{n}$ полинома и простора. Побољшање ове временске границе изгледа тешко. На пример, још увек није утврђено да ли је тачан алгоритам за ТСП који ради на време $O(1.9999^{n})$ постоји.

Други приступи укључују:

• Разни филијала-и-везане алгоритми, који се могу користити за обраду ТСП-а садрже 40-60 градова.

Решење о ТСП са 7 градова користећи једноставан Гране и везан алгоритам. Напомена: број пермутација је много мање него грубом силом претрагу

• Прогресивно побољшање алгоритама који користе технике које подсећају линеарног програмирања. Ради добро за до 200 градова.
• Имплементација гране-и-везан и проблема специфичних рез генерације (филијала-и-рез), то је метода избора за решавање великих случајева. Овај приступ има тренутни рекорд, решавање инстанцу са 85.900 градовима.

Тачан решење за 15.112 немачких градова од ТСПЛИБ пронађен је у 2001 користећи најсавременије методе авион који је предложио Џорџ Дантзиг, Раи Фулкерсон и Селмер M. Јохнсон 1954, на основу линеарног програмирања.

Хеуристички алгоритми и апроксимација

Разни хеуристике, алгоритми и апроксимација која ће брзо дати добра решења су осмишљена. Савремене методе могу пронаћи решења за изузетно велике проблеме (милиони градова) у разумном временском периоду који су са великом вероватноћом само 2-3% далеко од оптималног решења. Неколико категорија хеуристике признају.

Конструктивне хеуристике

Најближи сусед алгоритам за ТСП са 7 градова. Решење промене као полазна тачка се мења

Најближи комшија (НН) алгоритам (или тзв. похлепни алгоритам) омогућава продавац одабрати најближу непосећени град као свој следећи потез. Овај алгоритам брзо приноси ефикасно кратак пут. За Н градова насумично распоређених у авиону, алгоритам на просечних приноса пут 25% дужи од најкраћи могући пут. Међутим, постоје многе посебно организован градски системи који чине НН алгоритам даје најгори пут (Гутин, Јео , и Зверовицх, 2002). Ово важи и за асиметричне и симетричне ТСП-а (Гутин и Иео, 2007). Показали су да алгоритам има апроксимације фактор $\Theta (\log |V|)$ случајевима за задовољавање неједнакост троугла. Варијација НН алгоритма, позвао Најближа фрагмент (НФ) оператора, који повезује групу (одломак) од најближих непосећени градова, можете наћи краћи пут са узастопних итерација. НФ оператер може се применити и на почетној решења добијеног НН алгоритма за даље усавршавање у елитистички модел, где се прихватају само боља решења. Изградњу на основу рразапињућег стабла минималног степена имају приближан однос 2. Цхристофидес алгоритам постиже однос од 1,5. Битониц турнеја скуп тачака је минимална-периметар монотон полигон који има тачке као своје чворова, може да се ефикасно израчуна помоћу динамичког програмирања. Још један конструктиван хеуристички, меч два пута и Ститцх (МТС) (Кахнг, Реда 2004), обавља две узастопне матцхингс, где се други подударања извршава након брисања све ивице првог упаривања, да дају низ циклуса. Циклуси су тада зашили да произведе финални турнеју.

Итеративно побољшање

Паирвисе размена

Појава удвојених размена или 2-опт техника подразумева итеративно уклањање две оштрице и замене их са две различите ивице да поново успостави фрагменте настале уклањањем ивице у нову и краће турнеје. Ово је специјални случај к-опт методом. Имајте на уму да ознака Лин-Кернигхан је често погрешно чуо за 2-опт. Лин-Кернигхан је заправо општији к-опт метода.

к-опт хеуристички, или Лин-Кернигхан хеуристике

Узмите дати обилазак и брисање к међусобно неповезане ивице. Поново преостале фрагменте на турнеји, и не оставља ишчашен субтоурс (то јест, не повезују крајње тачке фрагмент је). Овај ефекат у поједностављује ТСП који разматрамо у много једноставнији проблем. Сваки фрагмент крајња тачка може бити повезан са 2к - 2 друге могућности: од фрагмената 2к укупних расположивих крајњих тачака, две крајње тачке у фрагменту који се разматра је недопуштено. Таква отежана 2к-град ТСП се могу решити са бруталним методама да пронађу бар-цост рекомбинацијом оригиналних фрагмената. К-опт техника је специјални случај V-изузимање или променљива опт-технике. Најпопуларнији к-опт методе су 3-опт, и они су уведене од стране Схен Лина из Белл Лабс 1965. Постоји посебан случај 3-опт где ивице нису ишчашен (два од ивице суседни једни другима). У пракси, често је могуће да се оствари значајан напредак у односу на 2-опт без комбинаторне штету општих 3-опт ограничавањем 3-промене у овом посебном подгрупом којој два од уклоњених ивица суседни. Овај такозвани два-и-по-опредељују обично пада око пола пута између 2-опт и 3-опт, како у погледу квалитета туре постигнутих и време потребно за постизање те туре.

V-опт хеуристички

Променљива-опт метод је повезана и генерализација к-опт методом. Док к-опт методе уклоните фиксни број (к) од ивица из оригиналног турнеје, променљива-опт методе не поправи величину ивице постављен за уклањање. Уместо тога, они расту као скуп претраживање процес се наставља. Најпознатији метод у овој породици је Лин-Кернигхан метод (горе поменуто као погрешно употребљава за 2-опт). Шен Лин и Брајан Кернигхан први објавио свој метод у 1972, а то је најпоузданији хеуристике за решавање проблема трговачког путника скоро две деценије. Напреднији променљива опт-методе су развијене у Белл Лабс у касним 1980 Дејвид Џонсон и његов истраживачки тим. Ове методе (понекад се назива Лин-Кернигхан-Џонсон) граде на Лин-Кернигхан методом, додајући идеје табу претраживање и еволутивног рачунарства. Основни Лин-Кернигхан техника даје резултате који су гарантовано да буде најмање 3-опт. ЛИН-Кернигхан-Јохнсон метода израчуна Лин-Кернигхан турнеју, а затим Пертурб турнеју по ономе што је описано као мутацијом која уклања најмање четири ивице и поновно повезивање турнеју на другачији начин, а затим V-одлуче на нову турнеју. Мутација је често довољно да се креће у обилазак од локалног минимума препознаје по Лин-Кернигхан. V-опт методе се широко сматра као најмоћније хеуристике за проблем, и да су могли да се баве посебним случајевима, као што је Хамилтон циклуса проблема и других не-метричких ТСП-а који не успевају на друге хеуристике. Дуги низ година, Лин-Кернигхан-Џонсон је утврдила оптимална решења за све ТСП-а где је оптимално решење познатих и идентификована су најпознатије решења за све остале ТСП на који је начин је суђено.

Рандомизирано побољшање

Оптимизовани Марковљеви ланци алгоритми који користе локалне потрази хеуристика под-алгоритми могу наћи пут веома близу оптималног пута за 700 и 800 градова. ТСП је пробни камен за многе опште хеуристике створеним за комбинаторне оптимизације, као што су генетских алгоритама, симулирано жарење, Табу тражење, колонија мрава оптимизација и динамика формирање.

Оптимизација колоније мрава

Вештачка интелигенција истраживач Марко Дориго је описао 1997. године хеуристички метод генерисања "добрих решења" за ТСП користећи мрављи алгоритам (енгл. Ант цолонy оптимизатион алгоритхмс, АЦО). Као основу је искористио понашање реалних мрава, које је приметио у природи. Наћи кратке стазе између извора хране и своје гнездо, хитно понашање узроковано жељи сваког мрава да прати траг феромона депонована од стране других мрава. АЦС шаље велики број виртуелних мрава агената за истраживање многих могуће трасе на мапи. Сваки мрав пробабилистички бира следећи град да посети основу хеуристике комбинује раздаљину до града и износ виртуелног феромона депонована на ивици до града. Мрави истражују, депоновање феромона на свакој ивици да пређе, док сви они су завршили турнеју. У овом тренутку мрав који заврши најкраћем турнеје депозита виртуелни феромона дуж своје трасе потпуне турнеје (глобална рута ажурирање). Износ депонованих феромона је обрнуто пропорционална дужини турнеје: краће турнеје, виши депозити.

Ант Цолони Оптимизатион Алгоритам за ТСП са 7 градова: црвено и дебеле линије у феромона карте указују на присуство више феромона

Посебни случајеви

Метрички ТСП

У метрике ТСП, такође познат као Делта или ТСП-Δ-ТСП, међумесни растојања задовољити троугао неједнакост. врло природно ограничење ТСП је да захтева да се удаљеност између градова формирају метрику да задовољи троугао неједнакост, који је директна веза од А до Б никад даље од правца преко C: $d_{AB}\leq d_{AC}+d_{CB}$.

Едге обухвата затим изградити метрику на скупу темена. Када су се градови посматрају као тачке у равни, многи природни растојање функција а су метрике, а толико природни случајеви задовољавају ТСП то ограничење. Следе неки примери метричких ТСПс за разне метрике. * У Еуклидов ТСП (види доле) растојање између два града је Еуклидово растојање између одговарајућих тачака. * У праволинијском ТСП растојање између два града је збир разлике у њиховимx и y-координатама.

Ова метрика се често назива Менхетн растојање или град-блок метрике. * У максимум метрички, растојање између две тачке је максимум апсолутних вредности разлика од својих x и y-координата. Последње две метрике се појављују на пример у рутирање машину која бушилице дати скуп рупа у штампана плоча. Манхаттан метрика одговара машину која подешава први који координира, а затим други, па је време да се преселе у нове тачке је збир оба покрета. Максималне метричких одговара машину која истовремено подешава обе координате, тако да је време да се преселе у нове тачке је спорији од ова два покрета.

У својој дефиницији, ТСП не дозвољава градовима да се два пута посете, али многим апликацијама не треба то ограничење. У таквим случајевима, симетрични, неметричким инстанцама може се свести на један метрички. Ово замењује оригинални граф са комплетним графом који рацуна грацко растојање $d_{AB}$ замењује најкраћи пут између $A$ и $B$ и оригиналног графа.

Распон минималне мреже $G$је доња граница размака од оптималне трасе, јер брисање било које ивице у оптималној рути приносе Хамилтонова путања, који је у спаннинг трее $G$.У ТСП са [[]] троугао неравноправности случај је могуће доказати преко горње границе у погледу минималног спаннинг трее и дизајн алгоритам који има доказиви горња граница распона трасе. Прва објављена (и најједноставнија) пример следи:

1. Изградити минималну Спаннинг Трее $T$ фор $G$.
2. Дуплирати све ивице $T$. То је, где год постоји ивица од У да V, додајте Друга предност од V да у. То нам даје Ојлеров граф $H$.
3. Пронађи Ојлеров круг $C$ у $H$. Јасно, распона два пута распон од дрвета.
4. Конвертовати Ојлеров круг у Хамилтонов циклуса на следећи начин: шетња, а сваки пут кад треба да дођу у већ посећена темена, прескочите га и иду на следећи.

Лако је доказати да је последњи корак ради. Штавише, захваљујући неједнакости троугла, свака прескакање у кораку 4 у ствари пречица, односно, дужина циклуса не повећава. Стога нам даје ТСП турнеју не више од два пута дуже од оптималан.

Цхристофидес алгоритам следи сличан нацрт већ комбинује минимални Спаннинг Трее раствором другог проблема, минимална тежина-савршено подударање. Ово даје ТСП турнеју која је највише 1,5 пута оптимална. Цхристофидес алгоритам је био један од првих апроксимација алгоритма а, и био је делимично одговорна за скретање пажње на приближавања алгоритмима као практичан приступ нерешиви проблеми. У ствари, израз "алгоритам" није уобичајено продужен до приближавања алгоритама касније, Цхристофидес алгоритам је у почетку назива Цхристофидес хеуристике.

У слуцају да је удаљеност између градова су све или један или два (а тиме и неједнакост троугла је нужно задовољан), постоји полином-време апроксимација алгоритам који проналази обилазак дужине највише 8/7 пута оптимална тура дужине Берман , Карпински.П. Берман (2006). Марек Карпински, "Алгоритам за 8/7-Аппрокиматион (1,2)-ТСП", Проц. 17. АЦМ-СИАМ сода (2006), стр 641-648.</реф> Међутим, то је дугогодишњи (од 1975) отворен проблем да се побољша Цхристофидес фактор приближавања од 1,5 за опште метрички ТСП на мање константе. Познато је да, уколико П = НП,најбоље да полином-алгоритам може наћи обилазак дужине 123/122 пута Оптимална дужина туре Карпински, Лампис и Сцхмиед. За асиметричне ТСП је основна граница износи 75/74. У случају ограничења показало се да је најбоље време полином алгоритам може да уради је да се изгради турнеју дужине 337/336 пута оптималној дужини Тоур, осим акоП = НП За случај асиметричне граница је 135/134.

Еуклидов ТСП

Еуклидска ТСП, или планарна ТСП, је ТСП са дистанце сада обичан еуклидска дистанца. Еуклидов ТСП је појединачан случај метричких ТСП, јер раздаљине у авиону поштују неједнакост троугла. Као опште ТСП, еуклидска ТСП (а самим тим и опште метрички ТСП) је НП-комплетан. Међутим, у неким аспектима се чини да је лакше него опште метрике кашичице. На пример, минимално разапињуће стабло графа је повезано са инстанцом Евклидовог ТСП-а, то је Еуклидска минимално раyапињуће стабло, па се може израчунати у очекиваном О (н лог н) за н тачака (знатно мањи од броја ивица). Ово омогућава једноставну 2-апроксимације алгоритам за ТСП са неједнакости троугла горе да ради брже. У принципу, за свако ц > 0, где је д број димензија у Еуклидов простор, постоји полином-алгоритам који проналази обилазак дужине највише (1 + 1 / ц) пута оптимална за геометријских случајева ТСП у $O\left(n(\log n)^{(O(c{\sqrt {d}}))^{d-1}}\right)$ времену; то се зове полином-време апроксимација шема (ПТАС) Сањев Арора и Јосиф СБ Мичел је добио награду у 2010 Гедел за њихово истовремено откриће ПТАС за Еуклидов ТСП. У пракси, хеуристике са лошијим гаранције и даље да се користи.

Асиметрична ТСП

У већини случајева, растојање између два чвора у мрежи ТСП је исти у оба смера. Случај када је растојање од А до Б није једнака удаљености од Б до А асиметрични ТСП. Практична примена асиметричног ТСП је пут оптимизацији коришћења уличних рутирање (који је направљен од асиметричних једносмерне улице, клизање-путева, аутопутева и сл).

Решавање конверзијом у симетрични ТСП

Решавање асиметричну ТСП графикон може бити донекле сложен. Следи 3 × 3 матрица која садржи све могуће путање тежине између чворова А, Б и C. Једна од опција је да се окрену асиметричну матрицу величине Н у симметрическој матрице величине 2Н.

Асиметрични пут тежине

	А	Б	C
А		1	2
Б	6		3
C	5	4

Да би удвостручио величину, сваки од чворова у графу је дуплирана, креирајући други дух чвор. Коришћење дупле поене са веома ниским тежине, као што су - ∞, пружа јефтин пут "повезивање" врати на прави чвор и симетрична евалуација омогућава да се настави. Оригинални 3 × 3 матрица приказан горе је видљив у доњем левом и обрнуто од оригинала у врху десно. Оба примерка су матрице су њихови дијагонале замењене дешевие хоп стазама, представљају - ∞.

Симетрични пут тежине

	А	Б	C	А′	Б′	C′
А				−∞	6	5
Б				1	−∞	4
C				2	3	−∞
А′	−∞	1	2
Б′	6	−∞	3
C′	5	4	−∞

Оригинални 3 × 3 матрица ће производити два Хамилтонових циклуса (пут да посети једном сваки чвор), односно АБЦА [оцена 9] и АЦБА [оцена 12]. Процена 6 × 6 симетрична верзија истог проблема сада производи много путева, укључујући АА'-ББ'-CC'-, АБ'-ЦА'-, АА'-БЦ'-[све оцена 9 - ∞] . Важна ствар у вези са сваком новом низу је да ће бити смењивање испрекидана (', Б', C ') и УН-испрекидана чворова (А, Б, C) и да су повезане на "скок" ; вези између једног пара (АА) је ефикасно бесплатно. Верзија алгоритма може да користи било коју тежину за пут на АА ', док је тежина мања од свих других путања пондера присутне у графикону. Као пут тежину да "скочи" мора да буде ефикасно "слободан", вредност нула (0) може да се користи за представљање ове трошкова нула уколико се не користи у друге сврхе већ (као што су одређивање неважеће путање). У два горе наведеним примерима, непостојеће стазе између чворова су приказани као празан квадрат.

Мерила

За бенцхмаркинг ТСП алгоритама, ТСПЛИБ је библиотека узорака инстанци ТСП и сродних проблема се одржава, погледајте ТСПЛИБ спољну референцу. Многи од њих су листе стварних градова и распореда стварних штампаних плоча.

Људска представа о ТСП

ТСП, посебно евклидова варијанти проблема, привукао је пажњу истраживача у когнитивној психологији. Примећује се да су људи у стању да брзо дати добре квалитетна решења. Први број часописа за решавање проблема је посвећен теми људске перформансе на кашичице.

ТСП Дужина пута по рандом поинтсет у квадрат

Претпоставимо Н тачке су насумично распоређени у 1 × 1 квадрат са Н >> 1. Размислите много таквих квадрата. Претпоставимо да желимо да знамо просек најкраћи пут дужине (тј. решење ТСП) за сваки квадрат.

Доња граница

${\frac {1}{2}}{\sqrt {N}}$ је доња граница која се добија претпостављајући Ја бити тачка у низу и ја је његов следећи Комшија као његова друг у путу.

$\left({{\frac {1}{4}}+{\frac {3}{8}}}\right){\sqrt {N}}$ Има бољу доњу границу коју добија претпостављајући I 'а ово друго је I , следи, и ја' 'бивси је ја је након следећег.

${\sqrt {\frac {N}{2}}}$ је још боља од доње границе која се добија дељењем путањи секвенце на два дела, као бефоре_и' и' са бехинд_и сваки део садржи Н / 2 бода, а затим брисања бефоре_и' део формирати разблаженим поинтсет.

• Давид С. Џонсон добити доњу границу од рачунара експеримента:

$0.7080{\sqrt {N}}+0.522$, одакле потиче од 0.522 тачака у близини трга границе које имају мање суседе.

• Кристина L. Валензуела и Антониа Ј. Јонес добио још један доње границе од рачунара експеримента:

$0.7078{\sqrt {N}}+0.551$

Горња граница

Применом методе на симулирани жарења узорака Н = 40000, компјутерска анализа показује горње границе

$\left({\sqrt {\frac {N}{2}}}+0.72\right)\cdot 1.015$, одакле долази 0,72 од граничне ефекта.

Пошто стварни решење је само најкраћи пут, за потребе програмског потрази други горњу границу је дужина једног претходно открио апроксимације.

Трговачки путник аналитичара проблема

Постоји проблем у аналоган геометријској теорији мери која пита следеће: под којим условима може подскуп е Еуклидов простор се налази у отклоњива кривини (то јест, када је ту крива са коначне дужине које посећује сваки поен у Е)? Овај проблем је познат као трговачког путника аналитичара проблем или геометријског проблема трговачког путника.

Погледај још

Проблем рутирања возила

Нотес

• Дер Хандлунгсреисенде - вие ер Сеин унд солл био ер зу Тун [сиц] шешир, ум Ауфтраге зу ерхалтен унд еинес глуцклицхен Ерфолгс у Сеинен магазинов ГЕВИСС зу сеин - вон еинем Алтен коми-Воиагеур" (трговачки путник - како он мора да буде и шта треба да уради како би били сигурни да обавља своје задатке и да успех у свом послу - од стране Високог комесаријата-воиагеур) ^ дискусија раног рада Хамилтон и Киркман могу се наћи у Грапх Тхеори 1736-1936 ^ Цитирано и енглески превод у Сцхријвер (2005).
• Оригинални Немачки: "Вир безеицхнен алс Ботенпроблем (Веил Диесе Захтевај у вон дер Пракис једем Постботен, убригенс ауцх вон виелен Реисенден зу лосен ист) фур дие Ауфгабе, ендлицх виеле Пункте, Дерен паарвеисе Абстанде беканнт синд дие, Ден курзестен Пункте вербинденден Вег зу финден. Диесес Проблем ист Натурлицх стетс дурцх Ендлицх Виеле Версуцхе лосбар. Правила, велцхе Дие Количество Версуцхе унтер дие Количество Пермутатионен дер гегебенен Пункте херунтердруцкен вурден, синд ницхт беканнт.
• Дие Регел, човек Солле вом Аусгангспункт предходно зум нацхстгелегенен Пункт, Данн зу дем диесем нацхстгелегенен Пункт гехен етц, лиеферт им аллгемеинен ницхт ден Вег курзестен.. " ^ детаљан третман повезаности Менгер и Витни, као и раст у проучавању ТСП се може наћи у 2005 папиру Александра Сцхријвер је "о историји комбинаторне оптимизације (до 1960). Приручник о дискретној Оптимизатион (К. Аардал, ГЛ Немхаусер, Веисмантел Р., ур.), Елсевиер, Амстердам, 2005, стр 1-68.ПС, ПДФ ^ Бехзад, Арасх, Модаррес, Мухамед (2002), " ; нови ефикасни Трансформација генерализоване трговачког путника проблема у проблем трговачког путника ", Зборник радова 15. Међународне конференције системски инжењеринг (Лас Вегас) ^ Пападимитриоу, ЦХ; Стеиглитз, К. (1998). Комбинаторне оптимизације: Алгоритми и сложеност. Минеола, НИ: Довер. ^ Орпонен

Литература

• Апплегате, D. L.; Биxбy, Р. M.; Цхвáтал, V.; Цоок, W. Ј. (2006), Тхе Травелинг Салесман Проблем, ИСБН 0-691-12993-2 .
• Беллман, Р. (1960), „Цомбинаториал Процессес анд Дyнамиц Программинг”, Ур.: Беллман, Р.; Халл, M., Цомбинаториал Аналyсис, Процеедингс оф Сyмпосиа ин Апплиед Матхематицс 10, Америцан Матхематицал Социетy, стр. 217—249 .
• Беллман, Р. (1962), „Дyнамиц Программинг Треатмент оф тхе Травеллинг Салесман Проблем”, Ј. Ассоц. Цомпут. Мацх., 9: 61—63, С2ЦИД 15649582, дои:10.1145/321105.321111 .
• Цхристофидес, Н. (1976), Wорст-цасе аналyсис оф а неw хеуристиц фор тхе травеллинг салесман проблем, Тецхницал Репорт 388, Градуате Сцхоол оф Индустриал Администратион, Царнегие-Меллон Университy, Питтсбургх .
• Хассин, Р.; Рубинстеин, С. (2000), „Беттер аппроxиматионс фор маx ТСП”, Информатион Процессинг Леттерс, 75 (4): 181—186, дои:10.1016/С0020-0190(00)00097-1 .
• Хелд, M.; Карп, Р. M. (1962), „А Дyнамиц Программинг Аппроацх то Сеqуенцинг Проблемс”, Јоурнал оф тхе Социетy фор Индустриал анд Апплиед Матхематицс, 10 (1): 196—210, дои:10.1137/0110015 .
• Каплан, Х.; Леwенстеин, L.; Схафрир, Н.; Свириденко, M. (2004), „Аппроxиматион Алгоритхмс фор Асyмметриц ТСП бy Децомпосинг Дирецтед Регулар Мултиграпхс”, Ин Проц. 44тх ИЕЕЕ Сyмп. он Фоундатионс оф Цомпут. Сци, стр. 56—65 .
• Карп, Р.M. (1982), „Дyнамиц Программинг Меетс тхе Принципле оф Инцлусион анд Еxцлусион”, Опер. Рес. Летт., 1 (2): 49—51, дои:10.1016/0167-6377(82)90044-X .
• Кохн, С.; Готтлиеб, А.; Кохн, M. (1977), „А Генератинг Фунцтион Аппроацх то тхе Травелинг Салесман Проблем”, АЦМ Аннуал Цонференце, АЦМ Пресс, стр. 294—300 .
• Косарају, С. Р.; Парк, Ј. К.; Стеин, C. (1994), „Лонг тоурс анд схорт суперстрингс'”, Проц. 35тх Анн. ИЕЕЕ Сyмп. он Фоундатионс оф Цомпут. Сци, ИЕЕЕ Цомпутер Социетy, стр. 166—177 .
• Орпонен, П.; Маннила, Х. (1987), „Он аппроxиматион пресервинг редуцтионс: Цомплете проблемс анд робуст меасурес'”, Тецхницал Репорт C-1987–28, Департмент оф Цомпутер Сциенце, Университy оф Хелсинки .
• Пападимитриоу, C. Х.; Yаннакакис, M. (1993), „Тхе травелинг салесман проблем wитх дистанцес оне анд тwо”, Матх. Опер. Рес., 18: 1—11, дои:10.1287/моор.18.1.1 .
• Сердyуков, А. I. (1984), „Ан алгоритхм wитх ан естимате фор тхе травелинг салесман проблем оф тхе маxимум'”, Управлyаемyе Системy, 25: 80—86 .
• Wоегингер, Г.Ј. (2003), „Еxацт Алгоритхмс фор НП-Хард Проблемс: А Сурвеy”, Цомбинаториал Оптимизатион – Еурека, Yоу Схринк! Лецтуре нотес ин цомпутер сциенце, вол. 2570, Спрингер, стр. 185—207 .

Спољашње везе

• Traveling Salesman Problem Архивирано на сајту Wayback Machine (26. децембар 2008) at Georgia Institute of Technology
• TSPLIB at the University of Heidelberg
• Traveling Salesman Problem by Jon McLoone at the Wolfram Demonstrations Project
• Source code library for the travelling salesman problem Архивирано на сајту Wayback Machine (21. мај 2013)