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

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

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

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

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

Обозначим его как Nvar. Тогда:

• Nvar = (N-1)! — если считать все возможные маршруты;
• Nvar = 0.5 × (N-1)! — если не учитывать обратные дубликаты маршрутов (т.е. считать A→B→C тем же, что C→B→A).

Для 30 городов получаем Nvar ≈ 4.4 × 10³⁰. Даже если написать программу, которая проверяет миллион маршрутов в секунду, на полный перебор уйдёт около 1.4 × 10¹⁷ лет. К тому времени пра-праправнуки коммивояжёра уже успеют умереть с голоду. ;)

Не всё так плохо

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

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

Я собрал небольшую программку, которая решает задачу с помощью генетического алгоритма.

Если коротко: в природе живые организмы эволюционируют за счёт мутаций и отбора — и именно это позволяет им приспосабливаться к окружающей среде. Почему бы нам не применить похожий подход к задачам оптимизации?

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

Скачать

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