Как найти точку на 2-й взвешенной карте, которая будет иметь равноудаленные (как можно ближе) пути к нескольким конечным точкам?

Question

Допустим, у меня есть матрица с двумя типами ячеек: 0 и 1. 1 не проходима.

Я хочу найти точку, из которой я могу проложить пути (скажем, A*) к группе пунктов назначения (не ожидайте, что она будет больше 4). И я хочу, чтобы длина этих путей была такой, чтобы l1/l2/l3/l4 = 1 или как можно ближе к 1.

Для двух пунктов назначения все просто: проложите путь между ними и возьмите середину. Для большего количества мест назначения, я полагаю, что я могу запустить пути между каждой парой, тогда они создадут своего рода многоугольник, и я мог бы захватить центроид (или среднее значение всех координат точек пути)? Или было бы лучше взять все середины путей между каждой парой, а затем использовать их как вершины в многоугольнике, который будет содержать желаемую точку?

Answer 1

Кажется, вы хотите найти точку с лучшим доступом к нескольким конечным точкам. Для других читателей это все равно что пытаться найти идеальное поселение для торговли с соседними городами; Вы хотите, чтобы они были максимально доступны. Похоже, это вариант проблемы Вебера, применяемой для поиска путей.

Лучшее решение, так как вы больше не можете полагаться на использование геометрии (представьте, что горная тропа или два препятствуют пути) будет итеративным подходом. Я не думаю, что будет легко найти оптимальное решение, потому что вам нужно будет проверить каждый квадрат; вы не можете угадать, пройдя между конечными точками больше. Почти в любом большом проблемном пространстве вам нужно будет пройти путь от каждого возможного центроида до всех конечных точек. Субоптимальное решение будет довольно быстрым. Я рекомендую эти шаги:

1. попробуй оценить центроид, используя геометрию, формируя область поиска
2. Используйте модифицированный алгоритм A* из каждой точки S в области поиска для всех ваших целевых точек T, чтобы создать идеальный путь из S для каждого T,
3. Добавьте длину каждого пути S -> T вместе, чтобы получить Cost (вероятно, хранится в матрице для всех точек выборки)
4. Выберите самый низкийCost из всех ваших выборок в матрице (или всего населения, если вы не отбраковали пространство поиска).

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

Ранее я упоминал, что вы должны использовать модифицированный алгоритм A*... Вместо того, чтобы повторять общий поиск A* S->Tn для каждого T код A*, так что он ищет несколько целевых местоположений, сохраняя пути к каждому и останавливаясь, когда он нашел их все.

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

Проще говоря, найти точку легко. Чтобы найти его достаточно быстро, может потребоваться много хитрой эвристики (меры экономии) и сохраненных данных.