Достаточно пафосное название скрывает за собой интересную задачу. Если кто с ней не знаком, вот её описание.

(Классическая) задача Коммивояжера

Коммивояжер хочет объехать N городов и затем вернуться в начальный город. При этом желательно сделать это по наиболее короткому пути (т.к. коммивояжер не располагает лишними средствами на излишние перемещения между городами).

Лобовая атака

Допустим, мы решили перебрать все варианты возможных путей, удовлетворяющих условиям задачи, измерить их и, таким образом, найти наикратчайший. Не сложно заставить сделать это за нас компьютер. Но оценим прежде число вариантов Nvar в зависимости от N. Nvar = (N-1)!. Можно также исключить пути, которые повторяют друг друга но в обратном порядке. Тогда Nvar=0.5*(N-1)!. Уже для 30 городов нам прийдется оценить Nvar=4.4e30 вариантов пути. Даже если заставить эту работу проделать компьютер и написать при этом программу, которая анализирует 1000000 вариантов пути в секунду, то на решение задачи потребуется не менее 1.4e17 лет. А тем временем пра-правнуки коммивояжера будут погибать от голода. ;)

На самом деле нет нужды перебирать все варианты пути, если нет необходимости в поиске наикратчайшего. Оказалось, что существуют алгоритмы, которые за конечное, так сказать, время находят почти самый лучший путь. Это означает, что коммивояжер не останется голодным. ;)

Метод генетического алгоритма

Используя генетический алгоритм я сляпал программку, которая решает эту задачу. Что такое генетические алгоритмы — можно поискать в интернете. Но кратко суть в следующем.Давно замечено, что живые организмы в результате естественного отбора и при наличии изменений генетического материала приспосабливаются к окружающей среде. Можно бесконечно удивляться и учиться у природы тому как хитроумно устроены живые существа. Но это лишь результат решения природной задачи оптимизации. Почему бы и нам не использовать методы, которые использует природа?

Сопоставим некую биологическую особь и один из вариантов путей. Разработав некоторые методы изменения пути, мы получим прототипы инструментов природы — кросовера и мутации. Применяя операции изменения пути — мы получим набор решений, что в терминах биологических будет соответствовать популяции. Тогда отбор — это отбрасывание некоторой части путей, которые длинее остальных.

Решение задачи о коммивояжере — архив программы. Качайте, запускайте, и да не останется коммивояжер голодным!
А вот архив исходников проекта под Delphi 7 — скачать.