Лучший алгоритм пути, избегая врагов?

Question

У меня есть общий вопрос, который у меня был для интервью.

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

Мне очень любопытен лучший алгоритм или общий подход к этому.

PS: Вы знаете, где вражеские единицы находятся

Answer 1

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

1. Запуск ширины первого поиска, начиная с цели по всему графику, чтобы сохранить расстояние до цели в каждом узле. На этом этапе игнорируйте врагов. Конечно, это предполагает, что у вас есть определенная дистанция в вашем графике. В противном случае простое подсчет количества узлов во время bfs будет выполняться для некоторых приложений. Также держите расстояние до последнего узла до цели, назовем это количество maxdist.

2. Выполнение «маленькой» ширины первого поиска от каждого врага во всех направлениях. Маленький, потому что вы останавливаете это после расстояния k, где k - это количество узлов графика, которые вы хотите держать в стороне от врагов или какой-либо другой подходящей метрики (это означает, что «видят»). Сделайте аналогичную вещь в этом bfs: сохраните расстояние до этого врага, где находится противник, обозначите его как d_i для произвольного узла i. В этом BFS вы перезаписать расстояние до цели в узле я по MaxDist + к - D_i. Обратите внимание, что эта величина всегда не менее maxdist. На этом этапе вам нужно быть осторожным в том, как обновлять этот узел i, когда другой противник записал в него (сохраните большее значение).

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

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

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