А вот скажите, существует ли неэвристический алгоритм поиска кратчайшего обхода подмножества вершин графа? Граф ненаправленный, связанный, без весов. Вершин порядка 10,000, ребёр примерно вдвое-втрое больше. Даётся список из, скажем, N=100 вершин графа, нужно выдать кратчайший маршрут, проходящий по всем заданным в списке вершинам.

Можно ли сделать это неэвристически и чтоб не за O(N!) по времени было?

Кстати, граф можно считать неизменным, потому если можно уменьшить время выполнения за счёт каких-то предварительных подсчётов — это тоже вариант.