Получите наиболее оптимальную комбинацию мест из списка мест с помощью алгоритма графа. ⇐ Python

[Anonymous]

У нас есть сетевая ситуация, когда у него есть четыре узла — скажем, A, B, C и D. Проблема - A, B, C и D не исправлены, но имеют кучу возможностей.
Скажите A может иметь значения от A1, A2 до An.
То же самое для B — B1, B2, Bn .
То же самое касается C и D. Каждый из An, Bn, Cn и Dn имеет координаты в качестве свойств (кортеж - (21.2134, -32.1189)).Чего мы пытаемся достичь — найти наилучшую комбинацию An, Bn, Cn и Dn, которые наиболее близки друг к другу при прохождении в этот заказ(

Код: Выделить всё

A -> B -> C -> D). Например, это может быть A11 -> B1 -> C9 -> D4

— в основном выберите по одному варианту из каждого из A, B, C и D. из всех их соответствующих возможных значений так, чтобы комбинация этих значений была наиболее близкой друг к другу среди всех таких комбинаций.
Мы, конечно, пробуем подход грубой силы, но это очень дорого, поскольку его временная сложность равна N(A) * N(A) * N(C) * N(D).
Итак, мы ищем какое-то решение на основе графа, в котором мы мы можем использовать график, сохраняя в нем все точки с координатами, а во время выполнения мы можем просто передавать все наборы точек (все n точек для A, все k точек для B, все точки j для C и все точки l для D), и он выведет правильную точку для каждого из этих классов (

Код: Выделить всё

A

, B, C и D), для которых маршрут наиболее оптимален.
Если граф необходимо сохранить в память, это тоже нормально, чем меньше время отклика во время выполнения, тем лучше, память не является ограничением, а также, существует ли маршрут между An и Bn, здесь не имеет значения, все, что мы хотим сделать определить близость на основе координат (при условии, что между каждым набором точек существует линейный маршрут).
Кроме того, это не обязательно, на самом деле почти всегда будет так, что время выполнения запрос включает только несколько категорий мест, например, в исчерпывающем списке есть A, B, C и D, но запрос во время выполнения может попытаться найти комбинацию только B и C, или A и D, или A, B и D, и т. д.

Подробнее здесь: https://stackoverflow.com/questions/787 ... gh-graph-a