С концептуальной точки зрения, представьте, что вы бросаете камень в пруд и наблюдаете за рябью. Маршруты будут представлять пруд и камень вашей исходной позиции.
Конечно, алгоритм должен искать некоторую пропорцию из n ^ 2 путей по мере увеличения расстояния n. Вы бы заняли исходную позицию и проверили все доступные пути с этой точки. Затем рекурсивно вызывайте точки в конце этих путей и т. Д.
Вы можете повысить производительность, не дублируя путь, не перепроверив маршруты в точке, если она уже пройдена, и отказавшись от путей, которые занимают слишком много времени.
Альтернативным способом является использование подхода с феромонами муравьев, когда муравьи ползут случайным образом из начальной точки и оставляют след, который накапливает больше муравьев, пересекающих данный путь. Если вы отправите (достаточно) муравьев как из начальной, так и из конечной точек, то в конечном итоге путь с самым сильным запахом будет самым коротким. Это связано с тем, что самый короткий путь будет посещаться больше раз за определенный период времени, учитывая, что муравьи ходят с одинаковой скоростью.
РЕДАКТИРОВАТЬ @ Spikie
В качестве дальнейшего объяснения того, как реализовать алгоритм пруда, выделены потенциальные структуры данных:
Вам нужно будет сохранить карту как сеть. Это просто набор nodes и edges между ними. Набор nodes составляет route. Край соединяет два узла (возможно, оба и тот же узел) и имеет связанный cost, такой как distance или time, для прохождения края. Край может быть либо двунаправленным, либо однонаправленным. Вероятно, проще всего иметь однонаправленные и удвоить для двухстороннего перемещения между узлами (то есть один край от А до В и другой для В от А).
В качестве примера представьте три железнодорожные станции, расположенные в равностороннем треугольнике, направленном вверх. Есть также еще три станции каждая на полпути между ними. Края соединяют все соседние станции вместе, на последней диаграмме перевернутый треугольник будет находиться внутри большего треугольника.
Отметьте узлы, начиная снизу слева, слева направо и вверх, как A, B, C, D, E, F (F вверху).
Предположим, что края могут проходить в любом направлении. Каждый край имеет стоимость 1 км.
Хорошо, поэтому мы хотим проложить маршрут от левого нижнего A к верхней станции F. Есть много возможных маршрутов, в том числе те, которые удваиваются назад, например, ABCEBDEF.
У нас есть рутина, скажем, NextNode, которая принимает node и cost и вызывает себя для каждого узла, к которому она может перейти.
Очевидно, что если мы позволим этой подпрограмме выполняться, она в конечном итоге обнаружит все маршруты, включая потенциально бесконечные по длине (например, ABABABAB и т. Д.). Мы не допустим этого, сверяясь с cost. Всякий раз, когда мы посещаем узел, который ранее не посещался, мы сравниваем стоимость и узел, с которого пришли, с этим узлом. Если узел был посещен до того, как мы проверим его по существующей стоимости, и если мы дешевле, мы обновим узел и продолжим (рекурсивный). Если мы дороже, тогда мы пропускаем узел. Если все узлы пропущены, мы выходим из процедуры.
Если мы дойдем до нашего целевого узла, то также выйдем из подпрограммы.
Таким образом, проверяются все жизнеспособные маршруты, но, главное, только те, которые имеют самую низкую стоимость. К концу процесса каждый узел будет иметь самую низкую стоимость для доступа к этому узлу, включая наш целевой узел.
Чтобы получить маршрут, мы работаем в обратном направлении от нашего целевого узла. Так как мы сохранили узел, из которого мы пришли, вместе со стоимостью, мы просто прыгнули назад, создавая маршрут. Для нашего примера мы получим что-то вроде:
Узел A - (Всего) Стоимость 0 - От Узла Нет
Узел B - Стоимость 1 - От Узла A
Узел C - Стоимость 2 - От Узла B
Узел D - Стоимость 1 - От Узла A
Узел E - Стоимость 2 - От Узла D / Стоимость 2 - От Узла B (это исключение, поскольку существует равная стоимость)
Узел F - Стоимость 2 - От Узла D
Итак, самый короткий маршрут - АПД.