Какой тип алгоритма используется для поиска путей с несколькими путями, но с одним источником? - PullRequest
Новая
       5

Какой тип алгоритма используется для поиска путей с несколькими путями, но с одним источником?

0 голосов
/ 13 ноября 2018

У меня есть график с одним источником и несколькими пунктами назначения.Я пытаюсь найти способ обозначить проблему, чтобы найти правильный тип алгоритма для решения.Цель состоит в том, чтобы как можно меньше путей достигло всех точек, однако пути должны всегда следовать точкам сетки (т. Е. Прямым углом).

Например: 

Origin:  (0, 0)
Point A: (3, 3)
Point B: (3, 0)
Point C: (1, 3)

Путь от Происхождения -> C -> A великолепен, потому что для перехода к точке A требуется только 2 дополнительных сегмента, потому что он смог разделить путь от Origin -> C.

Некоторые вещи, которые я обдумал:

  • Исчерпывающий все варианты пути ко всем точкам и затем исчерпывающе пробуя все комбинации.Это, очевидно, грубая сила и самый медленный метод.Не очень хорошо масштабируется.
  • Создаем матрицу из 1 от начала координат до точки _, затем выполняем добавление матрицы, чтобы найти наибольший трафик точек.Затем повторно выполните какой-либо тип исчерпывающего поиска, отдав предпочтение тем путям, которые следуют за сегментами с высоким трафиком.

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

Итак, мой вопрос состоит не столько в поиске ответа на конкретную проблему, сколько в попытках выяснить, как подойти к проблеме, т. Е. Какой путь (каламбур намеревался) пройти, когдапытаясь решить.

В целом, ищем оценки путей на основе (пока нет определенного порядка):

  • Количество общих сегментов против уникальных сегментов
  • Количество витков(предпочитая прямые)
  • Наименьшее расстояние

Ответы [ 2 ]

0 голосов
/ 13 ноября 2018

Это не похоже на минимальное остовное дерево, но на дерево Штейнера, https://en.wikipedia.org/wiki/Steiner_tree_problem, в частности на прямолинейное дерево Штейнера.

https://en.wikipedia.org/wiki/Rectilinear_Steiner_tree

К сожалению, это NP-хард.

0 голосов
/ 13 ноября 2018

Поскольку вы можете фактически достичь всех точек из любой точки в 2D-пространстве, вы можете представить его как полный граф с N узлами и N * (N - 1) / 2 ребрами - от каждой точки до всех остальных,

Вес каждого ребра может выражать расстояние между двумя узлами, которое равно расстоянию между этими точками на x плюс расстояние на y, потому что вы используете только прямые углы:

W [a, b] = = | ax - bx |+ | ay - by |

Теперь у вас есть нормальный граф, представленный множеством узлов и ребер, и вы можете применять любые желаемые алгоритмы.

Довольно непонятно, какой счет именно вы хотите достичь, но построение минимального связующего дерева звучит как ответ на проблему с наиболее оптимальными путями.
Например, вы можете использовать алгоритм Крускала чтобы достичь этого.

...