Решаване на проблема с пътуващия търговец с различни софтуерни методи
1.1 Общо описание
Проблемът на търговския пътник (наричан по-долу съкратено TSP) е един от известните проблеми в теорията на комбинаториката. Тя е поставена през 1934 г. и най-добрите математици си счупиха зъбите за нея, както за последната теорема на Ферма. В своята област (оптимизиране на дискретни проблеми) SP служи като своеобразен тестов полигон, на който се тестват нови методи.
Изложението на проблема е следното.
Пътуващият търговец (пътуващият търговец) трябва да напусне първия град, да посети градове 2,1,3.. n веднъж в неизвестен ред и да се върне в първия град. Разстоянията между градовете са известни. В какъв ред трябва да се обикалят градовете, така че затвореният път (обиколка) на пътуващия търговец да е най-кратък?
За да приведем проблема в научна форма, въвеждаме някои термини. И така, градовете се преномерират с номера j Т=(1,2,3.. n ). Обиколката на пътуващия търговец може да бъде описана чрез циклична пермутация t =( j 1, j 2 . j n , j 1 ), и всички j 1 .. j n са различни числа; повтаря се в началото и в края на j 1 показва, че пермутацията е циклична. Разстоянията между двойки върхове C ij образуват матрица C. Проблемът е да се намери такава обиколка t, която да минимизира функционалната
Относно математизираната формулировка на КП е уместно да се направят две забележки.
Първо, във формулировката на C ij означава разстояния, така че те трябва да са неотрицателни, т.е. за всички j T:
(последното равенство означава забрана за цикли в обиколката), симетрично, т.е. за всички i, j:
и удовлетворяват неравенството на триъгълника, т.е. за всички:
С ij + С jk C ik
Математическата формулировка се отнася до произволна матрица. Това се прави, защото има много приложни проблеми, които са описани от основния модел, но всички условия (2)-(4) не са изпълнени.Особено често се нарушава условие (3) (например, ако С ij не е разстояние, а тарифа: често билетът там струва една цена, а обратно - друга). Следователно ще разграничим два варианта на TSP: симетричен проблем, когато условие (3) е изпълнено, и асиметричен, в противен случай. Условия (2)-(4) ще се считат за изпълнени по подразбиране.
Втората забележка се отнася до броя на всички възможни обиколки. В асиметричен TSP всички обиколки t =( j 1 , j 2 . j n , j 1 ) и t =( j 1 , j n . j 2 , j 1 ) имат различни дължини и и двете трябва да бъдат взети под внимание. Различни обиколки очевидно ( n -1)!.
Нека фиксираме числото j 1 на първо и последно място в цикличната пермутация и пренаредим останалите n -1 числа по всички ( n -1)! възможни начини. В резултат на това получаваме всички асиметрични обиколки. Има наполовина по-малко симетрични обиколки, т.к всеки се брои два пъти: като t и като t .
Човек може да си представи, че C се състои само от 1s и 0s. Тогава С може да се интерпретира като графика, където ръбът ( i , j ) е начертан, ако С ij =0, а не ако С ij =1. След това, ако има обиколка с дължина 0, тогава тя ще премине през цикъла, който включва всички върхове веднъж. Такъв цикъл се нарича Хамилтонов цикъл. Отворен Хамилтонов цикъл се нарича Хамилтонова верига (Хамилтонов път).
От гледна точка на теорията на графите, симетричен TSP може да се формулира, както следва:
Дадена е пълна мрежа с n върха, дължина на ребра ( i , j )= С ij . Намерете Хамилтонов цикъл с минимална дължина.
В асиметричен ZK вместо „цикъл“ трябва да се каже „контур“, а вместо „ръб“ „дъги“ или „стрелки“.
Някои приложни задачи са формулирани като ZK, но в тях е необходимо да се минимизира дължината не на Хамилтоновия цикъл, а на Хамилтоновата верига. Такива задачи се наричат незатворени. Някои модели се свеждат до проблема сняколко пътуващи търговци, но няма да ги разглеждаме тук.
1.2. Методи за решаване на проблема
1.2.1. Метод на разклоняване и обвързване
Общата идея е тривиална: трябва да разделите огромен брой опции на класове и да получите оценки (отдолу в проблема за минимизиране, отгоре в проблема с максимизиране) за тези класове, за да можете да отхвърляте опциите не един по един, а по цели класове. Трудността се състои в намирането на такова разделение на класове (клонове) и такива оценки (граници), че процедурата да е ефективна.
Нека опишем алгоритъма на Литъл, като използваме пример 1 от предишния раздел.Нека напишем отново матрицата:
За нас ще бъде по-удобно да тълкуваме C ij като тарифата от град i до град j. Да предположим, че добрият кмет на град j е издал указ да плаща 5 долара на всеки пътуващ търговец, който влезе в града. Това означава, че всяка обиколка ще струва $5 по-малко, тъй като всяка обиколка изисква да въведете град j. Но тъй като всички обиколки са поевтинели равномерно, предишната минимална обиколка сега ще струва най-малко. Добрата постъпка на кмета може да бъде представена като намаляване на всички числа в j-тата колона на матрица C с 5. Ако кметът искаше да изпрати пътуващи търговци извън j-тия град и да определи награда за напускане в размер на $10, това може да се изрази чрез изваждане на 10 от всички елементи на j-тия ред на този ред. Това отново ще промени цената на всяка обиколка, но минималната обиколка ще остане минимална. Така се доказва следната лема.
Чрез изваждане на всяка константа от всички елементи на всеки ред или колона на матрица C, ние запазваме минималната обиколка на минимум.
За алгоритъма ще ни е удобно да получим повече нули в матрицата C, без обаче да получаваме отрицателни числа там. За да направим това, изваждаме от всеки ред неговия минимален елемент (това се нарича прехвърляне от ред към ред, вижте по-долу).раздел. 3) и след това извадете от всяка колона на матрицата, дадена от редове, нейния минимален елемент, получавайки матрица, дадена от колони, вижте таблицата. 4).
Диагоналните тирета означават, че не можете да отидете от град i в град i. Обърнете внимание, че сумата от константите за кастинг по редовете е 27, сумата по колоните е 7, а сумата на сумите е 34.
Обиколката може да бъде зададена чрез система от шест подчертани (маркирани с различен цвят) елемента на матрицата C, например, както е показано в табл. 2. Подчертаването на елемент означава, че при обиколката от i -тия елемент се стига точно до j -тия. За обиколка на шест града трябва да има шест подчертани елемента, тъй като има шест ръба в обиколка на шест града. Всяка колона трябва да съдържа точно един подчертан елемент (продавачът е въвел всеки град веднъж), всеки ред трябва да съдържа точно един подчертан елемент (продавачът е напуснал всеки град веднъж); освен това подчертаните елементи трябва да описват една обиколка, а не няколко по-малки цикъла. Сумата от числата на подчертаните елементи е цената на турнето. На масата 2 цена е 36, това е минималната обиколка, която се получава чрез лексикографско изброяване.
Сега ще разсъждаваме от намалената матрица в табл. 2. Ако успее да изгради правилна система от подчертани елементи, т.е. система, която отговаря на трите изисквания, описани по-горе, и тези подчертани елементи са само нули, тогава е ясно, че за тази матрица ще получим минимална обиколка. Но тя също ще бъде минимална за оригиналната матрица C, само за да получите правилната цена на обиколката, ще трябва да добавите обратно всички редуциращи константи и цената на обиколката ще се промени от 0 на 34. По този начин минималната обиколка не може да бъде по-малка от 34. Получихме по-ниска оценка за всички обиколки.
Сега да се заемем сразклоняване. За да направим това, ще предприемем стъпката на оценяване на нули. Помислете за нула в клетка (1,2) на намалената матрица. Това означава, че разходите за преместване от град 1 до град 2 са 0. Какво ще стане, ако не отидем от град 1 до град 2? След това все още трябва да въведете град 2 за цените, показани във втората колона; по-евтино само за 1 (от град 6). Освен това все пак ще трябва да напуснете град 1 за цената, посочена в първия ред; най-евтиният начин е до град 3 за 0. Обобщавайки тези два минимума, имаме 1+0=1: ако не отидете „с нула“ от град 1 до град 2, тогава трябва да платите поне 1. Това е оценката на нула. Оценките на всички нули са дадени в табл. 5 вдясно и над нулата (нулеви резултати, равни на нула, не бяха присвоени).
Нека изберем максимума от тези оценки (в примера има няколко оценки, равни на единица, нека изберем първата от тях, в клетката (1,2)).
И така, нулевият ръб (1,2) е избран. Нека разделим всички обиколки на два класа, включително ръба (1,2) и без ръба (1,2). За втория клас можем да кажем, че трябва да платите 1 повече, така че обиколките в този клас струват 35 или повече.
Що се отнася до първия клас, е необходимо да се вземе предвид матрицата в табл. 6 със задраскани първи ред и втора колона.