Проблема за търговския пътник (angl.Travellingsalesmanproblem, на ТС) (продавач - амбулантен търговец) - един от най-известните комбинаторни оптимизационни проблеми, е да се намери най-печелившата маршрута се преминава през споменатия град поне веднъж и след това се върнете към оригиналния града. В контекста на проблема показва рентабилността на критериите за маршрут (най-краткия, най-евтините, набор от критерии, и други подобни), както и съответстващото разстояние матрица, разходите и други подобни. Като правило, се посочва, че по маршрута трябва да премине през всеки град само веднъж - в този случай, изборът е направен сред Hamiltonian цикли.
Има няколко специални случаи на широката формулировка на проблема, по-специално геометрична търговски пътник проблем (наричан също планарна или евклидовата когато матрица разстояние отразява разстоянието между точките на самолета), метрични търговски пътник проблем (когато матрицата стойности неравенството триъгълник), симетричен и асиметричен търговски пътник проблем. Налице е също така обобщение на проблема, така наречената генерализирано пътуващ търговец проблема.
формулиране оптимизация на проблема принадлежи към класа на NP-трудни проблеми, но като повечето от неговите специални случаи. Версия «решение проблем» (това е този, при който въпросът е дали е налице маршрут е не по-дълъг от една предварително определена стойност к) принадлежи към класа на NP-пълни проблеми. Проблема за търговския пътник е един transvychislitelnyh: вече на сравнително малък брой градове (66 или повече), то не може да бъде решен чрез груба сила всички теоретично възможни варианти на компютри в по-малко от няколко милиарда години.
Задължително условие и единствената причина за проблема с пътуващ търговец е да се намери най-печелившата начин. За да направите това, да намерите и да опише всички възможни начини, с който и да е от вариантите на начини за намиране на решения. Ако не сме измислили по целия път до избрания вариант на решение, не можем да твърдим, че намереното решение е най-изгодно. Какво е решения за проверка? - търси грешка в преценката или изравняването на резултата с известно право. Вторият вариант е временно спадна, тъй като няма практически смисъл при решаването на проблема, ако има вече решение (от своя страна, използването на по-рано взели правилното решение за тази част от съществуващия проблем - начин за намаляване на решението). Като част от тази работа няма за цел да сравни различните методи и начини за решения, така че ние се предположи, че рецензент също смята, избрания начин на оптимални решения и да го проверява за коректност. Какво трябва да се направи, за да се провери? - повтори направено в решението работата, в пълно търсене на грешки, на всеки етап от решението. Ако се установи грешка, изпитващият ще трябва да продължи процеса на решение да се намери по-печеливши маршрути. По този начин, ние виждаме, че решенията за проверка Проблема за търговския пътник е равен или по-голям от самото решение.
Представяне като графика.
Symmetric проблем за четирите града.
За да разрешите използването на математически инструменти, за да се реши проблемът, трябва да се представи под формата на математически модел. пътуване проблем продавач може да бъде представен като модел на графиката, което е, с помощта на върховете и краищата между тях. По този начин, върховете на съответните градове и ребрата (I, й) между възли I и J - комуникация между двата града. Всеки ръб (I, J)> = 0 може да се сравни критерии рентабилност маршрут, които могат да бъдат разбрани като, например, разстоянието между места, времето за пътуване или разходи. Route (маршрут също Hamiltonian) се нарича маршрут на такава графика, която включва веднъж на всеки връх на графиката. Предизвикателството е да се намери най-краткия маршрут.
За да се опрости задачата и гарантира наличието на маршрута обикновено се счита, че моделът на графика на проблема е напълно свързани, т.е., че има ръб между всяка двойка на върховете. В случаите, когато между отделните градове, няма съобщение, това може да се постигне чрез въвеждане на ребрата с максимална дължина. Поради голямата дължина на ръба никога не стига до оптималния маршрут, ако има такъв.
В зависимост от това дали стойността на критерий е свързан рентабилност маршрут ръбове, разграничаване на различните изпълнения на проблема, най-важните от които са симетрични и проблем показател.
Пример за решаване на проблема пътуване продавач в питон на дадена графика (фиг. 3.2).
Обява 2 показва скрипт за изпълнение на задачата.
Този скрипт е "най-изгодно" път от най-богатия 1 в началото 4.
Свързани статии