Какво представлява "The Traveling Salesman Problem"?

Проблемът с пътуващия търговец (от английски „The Travelling Salesman Problem“) се състои в следния казус: „Даден е списък с градове и разстоянията между тях. Какъв е най-късият маршрут при който може да се посети всеки град и да се върнем в този, от който сме тръгнали?“. Зад тази простичко-формулирана задача всъщност стои доста сериозен математически проблем, свързан с комбинаторната оптимизация, която е важна в различни сфери сред които и компютърната наука. От къде произлиза този проблем?

Произходът на проблема с пътуващия търговец не е ясен, макар, че се заражда постепенно именно от пътуващите търговци и нуждата да оптимизират времето си за обиколка, през далечния XIX-ти век. През 1832 г. е издаден наръчник за пътуващите търговци, който дава препоръчителни маршрути на територията на Германия и Швейцария. Той е с изцяло практическа насоченост и не съдържа математическа трактовка на проблема.

Първата математическа формулировка се появява по-късно през същия век и е дело на ирландския математик W. R. Hamilton и британския математик Томас Къркман. Хамилтън създава т.нар. „Hamiltonian cycle” - алгоритъм, който се прилага за създаването на затворена верига от отсечки, преминавайки точно един път през всяка точка.

Проблемът обаче е дефиниран по-цялостно едва през 30-те години на XX-ти век, когато вече е привлякъл интереса на множество математици, сред които и Карл Менгер. Той изтъква, че за решаването на всеки отделен случай е неизбежна употребата на т.нар. „груба сила“ или „алгоритъм с груба сила“ - в математиката това означава при наличие на множество елементи, те да се комбинират по всеки един възможен начин, за да се намери търсеният резултат.

Друг подход за решаването на този проблем е чрез т.нар. „Greedy algorithms“ („алчни алгоритми“). Особеното при тях е, че те търсят оптимален резултат при решението на всяка отделна стъпка от даден проблем. Крайният резултат при тях не винаги е най-добрият, но на локално ниво (т.е. при проблем с по-ограничен мащаб) намира оптимално решение, което дава приблизително оптимален глобален резултат, за приемливо количество време. Приложена конкретно към проблема с пътуващия търговец, решението, което greedy стратегията ни предлага е, че достигайки всяка следваща точка, програмата ще търси най-близката следваща точка, която е непосетена. Чрез тази стратегия ние няма да намерим най-доброто решение при даден набор от точки на произволно разстояние една от друга, но ще намерим добро решение, което ще е изпълнено според принцип, при който няма да са необходими много стъпки, за да се достигне до такова.

За да се намери максималното решение на проблем с такава сложност обикновено са необходими други подходи към естеството на проблема, които или включват повече стъпки, което води до по-сложна логическа конструкция, или проверка с „груба сила“.

Днес алгоритмите не са свързани с теоретични задачи и проблеми, а отдавна са неизменна част от арсенала на всеки добър програмист. Затова сме подготвили модула „Algorithms with Java - май 2020“. Той е изцяло онлайн и е подходящ за всеки, усвоил основните принципи на обектно-ориентираното програмиране с езика Java, но е подходящ и за хора с еквивалентни знания с езиците „C”, “C++” и “C#”. Очакваме ви!