Оптимизация алгоритма - краткий маршрут между несколькими точками

In generally you should to strict bad variants... I think you should use some variations of Branch_and_bound method http://en.wikipedia.org/wiki/Branch_and_bound

Either bredth first search as norheim.se said or Dijkstra's algorithm would be my suggestion as well.

This sounds Travelling Salesman-esque? One solution is to use an optimisation technique such as an evolutionary algorithm. Currently you are doing an exhaustive search, which will get very slow very quickly. But I think this is pretty much a travelling salesman problem and it has been tackled for several decades if not centuries, and such there are several possible ways of attack. Google is your friend.

It appears that the edges of your graph are bidirectional. In this case, the algorithm you're looking for is Dijkstra's algorithm.

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

Предположим, у вас уже есть алгоритм кратчайшего пути по двум точкам - у него есть классические решения для различных типов графов. Предположим, что все расстояния неотрицательны и d (A-> B-> C) = d (A-> B) + d (B-> C).

Суть в том, что путь начинается в S, проходит через один из промежуточных городов "abcd" и заканчивается на E:

например, SabcdE, SacbdE и т. Д.

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

Затем, учитывая начальную и конечную точки, Есть 12 возможностей присоединения к одному из abcd и для каждых двух возможностей для интерьера. Вы уже вычислили эти расстояния, поэтому добавьте расстояние от S до головы и от хвоста к E. Выберите минимум. Итак, после того, как вы предварительно вычислили промежуточные расстояния для фиксированного набора внутренних городов, вам нужно выполнить 12 задач кратчайшего пути по двум точкам для любой пары начальной и конечной точек.

Очевидно, что это плохо масштабируется с увеличением количества промежуточных городов. Мне не ясно, может ли он работать лучше, если вы не наложите более строгие ограничения на структуру графа (это в физическом евклидовом пространстве? Неравенство треугольника?).

Мой мысленный пример: предположим, что все промежуточные расстояния между городами равны O (1 ). Без ограничений по графику, тогда расстояние от S до любого промежуточного города может быть 1000, кроме одного - 1. То же самое для хвоста. Таким образом, вы можете заставить посетить первый город что угодно. Теперь перейдите на один уровень вниз и возьмите первый город в качестве «отправной точки». Примените тот же аргумент: вы можете выбрать лучший путь к любому из следующих городов, манипулируя расстояниями на графике.

Таким образом, кажется, что сложность не может быть устранена без дополнительных предположений.