Исходник программы, показывающей пример решения задачи коммивояжера, которая требует, чтобы мы нашли кратчайший путь, посетив каждый из заданного набора городов и вернулись в исходную точку.
TSP относится к классу задач, которые по какой-то неочевидной причине называются NP-полными. У этих проблем нет известных эффективных алгоритмов их решения. «Неэффективно» здесь означает, что время решения проблемы увеличивается экспоненциально с увеличением размера проблемы, т.е. время решения - это выражение, которое содержит N в качестве показателя степени. Это намного более быстрый темп роста, чем любая задача с полиномиальным временем (сравните значения N2 и 2N для N = 2, 10, 20 и 30, чтобы увидеть эффект экспоненциального роста в простейшем случае).
Похоже, что в настоящее время ведется много исследований эффективных методов решения TSP - первое решение для 15 000 городов было найдено только в 2001 году, что значительно больше по сравнению с знаменательным решением для 49 городов, найденным в 1954 году. Есть и другие приложения TSP, например: проблемы с роботами, такие как пайка или сверление на печатных платах, определение последовательности локальных карт генома для создания глобальной карты, планирование порядка, в котором спутниковый интерферометр изучает последовательность звезд и т.д. Возможно, так же важно, как и прямые приложения, TSP обеспечивает основу для академических исследований проблем дискретной оптимизации. Определенно интригует то, что проблему, которую так легко сформулировать, может быть так сложно решить.
Исчерпывающий поиск разбивается примерно на 15 городов (около триллиона, 1012 путей для проверки). Когда количество городов превысит число подростков, нам придется полагаться на эвристические методы (практическое правило), которые обеспечивают «довольно хорошие» или «достаточно хорошие» решения.
Эта программа показывает карту 48 смежных штатов США и позволяет вам сгенерировать набор из 50 городов и щелкнуть по ним, чтобы сформировать путь с вашим общим пробегом. Для компьютерного поиска пути предусмотрены как кнопки исчерпывающего поиска, так и кнопки эвристических методов.
Базы данных
