Хабы: Алгоритмы, Математика
Поиск кратчайшего маршрута является сложной задачей, заключающейся в посещении каждого элемента из набора мест и возвращении в исходную точку, что представляет собой NP-усложнённую задачу. NP(в теории алгоритмов классом NP называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений (так называемого сертификата решения).) Она также известна как задача коммивояжера(ЗК) и изучается в области комбинаторной оптимизации, операционного исследования и теоретической информатики. ЗК используется в качестве эталона для многих методов оптимизации. Цель задачи заключается в нахождении одного пути, который может пройти через все узлы (экземпляры) графа всего один раз (гамильтонов цикл) с наименьшей длиной пути, то есть с минимальным евклидовым расстоянием.
Читать далее