TL;DR: Краткое описание проблемы:
Я ищу эффективный алгоритм, оптимизирующий размещение N агентов, расположенных в двумерном пространстве, в M убежищ, сводя к минимуму расстояние, которое агенты должны пройти.
Каждое убежище может содержать только 1 агента. Если N > M (агентов больше, чем доступных убежищ), то некоторые агенты не попадут в убежища (все агенты одинаковы).
(Необязательное упрощение: в то время как агенты могут свободно располагаться в 2D-пространстве, укрытия всегда располагаются на квадратной сетке. Ни один агент не находится за пределами выпуклой оболочки укрытий.)
Это все, что вам нужно знать. Однако, если вы считаете, что у этой проблемы нет эффективного решения, то вот...
более конкретная (и наиболее актуальная для меня) версия проблемы:
Имеется ровно 9 укрытий, расположенных на квадратной сетке (на расстоянии d). Все N агентов расположены вокруг центрального укрытия (в ящике размера d*d с центром вокруг центрального укрытия). Однако в этом случае центральное убежище всегда пусто, но все остальные укрытия могут быть или не быть доступными (пустыми) в начале.
Для этого случая мне нужен алгоритм, решающий проблему произвольного количества агентов N (обычно N ‹ 9) и наличия произвольных укрытий (либо всех 9, либо в крайнем случае только центрального укрытия).
Алгоритм должен быть эффективным, так как мне нужно быстро решить многие из этих задач.
Пример:
Вот пример с N=3 агентами (черные точки) и M=5 доступными убежищами (зеленые точки). Красными точками показаны недоступные убежища. 
]1 Я использую буквы для приютов и цифры для агентов.
Что я сделал на данный момент:
Я уверен, что эта проблема имеет конкретное название и уже решалась/изучалась, но я не могу найти ни ее названия, ни каких-либо решений. Мне нужно решить многие из этих проблем быстро, и я всегда хочу найти оптимальное решение (если это невозможно, достаточно и почти оптимального решения). Вот что я пробовал/думал до сих пор:
- Грубая сила: я знаю, что оптимальное решение задачи можно найти методом грубой силы, проверив все возможные варианты, вычислив общее расстояние перемещения для каждого и выбрав вариант с наименьшим общим расстоянием перемещения. Это может потребовать много вычислений, если M и N велики.
- Быстрое, но очень неоптимальное решение работает следующим образом: для каждого агента i вычислить расстояние до центрального узла E. Начиная с агента i с наименьшим расстоянием до E, назначить i его ближайшему убежищу (в данном случае: E). Затем назначьте следующего агента в его ближайшее убежище, учитывая, что E больше не доступен, и т. д., пока все агенты не будут назначены, или остановитесь, если больше нет свободных убежищ. Это работает, быстро, но, конечно, дает неоптимальные результаты (на примере изображения: 2->E, 1->B, 3->F, тогда как оптимальное решение должно быть 3->E, 2->F , 1-›Б)
- Еще одна идея, над которой я работаю, состоит в том, чтобы сначала найти агентов, которые находятся под наибольшим давлением, то есть все их хорошие варианты находятся далеко. Начиная с агента, находящегося под самым высоким давлением, назначьте его в ближайшее убежище. Продолжить для всех остальных агентов. Тем не менее, я не уверен, как правильно определить давление для этой проблемы, так как, вероятно, это должна быть комбинация расстояний до первых нескольких укрытий. Также я не уверен, что это приведет к оптимальному решению, но может привести к почти оптимальному решению.
- Я пытаюсь думать об этой проблеме как о своего рода взвешенной перестановке, то есть мне нужно выбрать N убежищ и сопоставить их с N агентами, но каждое сопоставление имеет свою цену. Мне нужно минимизировать общую стоимость, но я понятия не имею, как это сделать.
- Кроме того, я думаю о каком-то симулированном отжиге или о какой-то форме алгоритма «тяни-толкай», где каждое убежище привлекает агентов, или агенты привлекаются к убежищам в зависимости от их расстояния. Хотя это может показаться интересным, я ожидаю, что это неэффективно в вычислительном отношении.
Я рад любому вкладу, особенно если у этой проблемы уже есть собственное имя и решения. Я также доволен простым и быстрым алгоритмом вычислений, который дает почти оптимальное решение.
