Задача Коммивояжёра (англ.: Traveling Salesman Problem , сокр. TSP) является одной из классических проблем комбинаторики. Оптимальные решения для TSP с большим количеством городов представляют собой специальные случаи и как таковые действительны только в метрических пространствах. В отличие от этого, отимальные решения для общих TSP возможны только посредством полного анализа всех возможных n! замкнутых путей обхода. По этой причине, их решение таким способом оказывается не эффективным.

 Настоящая публикация представляет новый метод разложения - Метод ZIP (по-русски: "Метод Молнии"), позволяющий существенно уменьшить порядок необходимых расчетов. По существу этот метод может применятся и к несимметричным TSP. Содержащиеся примеры могут быть толчком для дальнейших исследований по решению Задачи Коммивояжёра.

(перевод с немецкого)

Weiter zum Inhaltsverzeichnis