Решаване на проблема с пътуващия търговец»
Съдържание
1. Цел на работата 3
2. Математика част 4
3. Описание на използвания софтуер 11
4. Списък на програмата 12
5. Ръководство за потребителя 13
7. Списък на използваната литература 15
На езика за програмиране C++ разработете програма за решаване на проблема с пътуващия търговец, като използвате метода на разклоняване и обвързване.
Математическа част
Задачата на пътуващия търговец (пътуващ търговец е пътуващ търговец) е да намери най-изгодния маршрут, минаващ поне веднъж през посочените градове. В условията на проблема са посочени критерият за рентабилност на маршрута (най-краткият, най-евтиният, кумулативен критерий и т.н.) и съответните матрици на разстояния, разходи и т.н.. Като правило е посочено, че маршрутът трябва да минава през всеки град само веднъж - в този случай изборът се прави между цикли на Хамилтон.
Съществуват много разновидности на обобщената формулировка на проблема, по-специално геометричният проблем на пътуващия търговец (когато матрицата на разстоянието отразява разстоянията между точките в равнината), триъгълният проблем на пътуващия търговец (когато неравенството на триъгълника е изпълнено в матрицата на разходите), симетрични и асиметрични проблеми на пътуващия търговец.
Най-простите методи за решаване на проблема с пътуващия търговец: пълно лексикално изброяване, алчни алгоритми (метод на най-близкия съсед, метод на включване на най-близкия град, метод на най-евтиното включване), метод на минимално обхващащо дърво. На практика се използват различни модификации на по-ефективни методи: методът на разклоненията и границите и методът на генетичните алгоритми, както и алгоритъмът на колонията на мравките.
За да приведем проблема в научна форма, въвеждаме някои термини. И така, градовете се преномерират с числа jТ=(1,2,3..n).Обиколката на пътуващия търговец може да се опише чрез циклична пермутация t=(j1,j2. jn,j1) и всички j1..jn са различни числа; повторен в началото и в края на j1, показва, че пермутацията е циклична. Разстоянията между двойки върхове Cij образуват матрица C. Проблемът е да се намери такава обиколка t, която минимизира функционалната
Метод на разклоняване и обвързване
Общата идея е тривиална: трябва да разделите огромен брой опции, които да бъдат сортирани в класове и да получите оценки (отдолу - в проблема за минимизиране, отгоре - в проблема за максимизиране) за тези класове, за да можете да отхвърляте опциите не един по един, а по цели класове. Трудността се състои в намирането на такова разделение на класове (клонове) и такива оценки (граници), че процедурата да е ефективна.
За нас ще бъде по-удобно да интерпретираме Cij като тарифата от град i до град j. Да предположим, че добрият кмет на града j е издал указ, че всеки пътуващ търговец, който влезе в града, трябва да получава 5 долара. Това означава, че всяка обиколка ще струва $5 по-малко, защото всяка обиколка изисква да влезете в града. Но тъй като всички обиколки са поевтинели равномерно, предишната минимална обиколка сега ще струва най-малко. Любезният акт на кмета, от друга страна, може да бъде представен като намаляване на всички числа в j-тата колона на матрицата C с 5. Ако кметът искаше да изведе пътуващите търговци от j-тия град и да определи награда за излизане от $10, това може да се изрази чрез изваждане на 10 от всички елементи на j-тия ред. Това отново ще промени цената на всяка обиколка, но минималната обиколка ще остане минимална. Така се доказва следната лема.
Чрез изваждане на всяка константа от всички елементи на който и да е ред или колона на матрица C, поддържаме минималната обиколка минимална.
За алгоритъма ще ни е удобно да получим повече нули в матрицата C, без обаче да стигнем до там,отрицателни числа. За да направим това, изваждаме от всеки ред неговия минимален елемент (това се нарича намаление по редове, вижте таблица 3) и след това изваждаме от всяка колона на матрицата, намалена по редове, нейния минимален елемент, получавайки матрица, намалена по колони, вижте таблицата. 4).
Диагоналните тирета означават, че не можете да ходите от град на град. Обърнете внимание, че сумата от константите за кастинг по редовете е 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 със задраскани първи ред и втора колона.