Алгоритм: где разместить объект, копать колодец, чтобы иметь минимальное расстояние в общей сложности

Question

Вопрос в том, что вы назначены неправительственной организацией, миссия которой заключается в расширении доступа к питьевой воде, чтобы найти оптимальное место для рытья колодца в деревне.Сумма расстояний до домов должна быть минимальной, но на пути есть препятствия (стены, скалы, деревья).Примером может быть:Где # - препятствие, а * - дом.

Что я пробовал: 1) для каждой пустой сетки запустите алгоритм поиска в ширину.и рассчитать общее расстояние от этой сетки до всех домов.Наконец, найдите тот, который имеет наименьшее расстояние.

2) постройте полный график для этой карты.То есть, соединить все возможные маршруты.Наконец, запустите алгоритм Minimum Spanning Tree для него.Все пустые сетки располагаются на MST-решениях

Answer 1

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

Answer 2

Я считаю, что это чрезмерная инженерия.

Целевая функция не обязательно должна быть «суммой»: что если есть выброс, который вносит большой вклад?

Также решения, которые вы пробовалинедостатки: поиск в ширину и MST применяются к древовидной топологии, которой нет в вашей задаче.

Почему бы вам не выполнить расчет географического центра тяжести;найти эту начальную точку;затем применить методы возмущения для уточнения решения?