Как обнаружить квадраты в сетке, которые НИКОГДА не могут быть частью кратчайшего пути после добавления блоков?

У меня есть сетка с началом, концом и некоторыми стенами. Юниты выбирают кратчайший путь (двигаются только вверх/вниз/влево/вправо) от начала до конца, минуя стены.

кратчайший путь

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

добавление стен

Однако обратите внимание, что независимо от того, сколько стен добавлено или где они добавлены, есть некоторые квадраты, которые никогда не могут быть частью кратчайшего пути!

Эти квадраты никогда не могут быть частью кратчайшего пути!
Эти квадраты никогда не могут быть частью кратчайший путь!

Я ищу способ определить, какие квадраты никогда не могут быть частью кратчайшего пути.

Вышеуказанные случаи достаточно легко найти; но бывают и более сложные случаи. Учитывать:

Ни один из квадратов с красными точками не может быть частью наилучшего пути

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

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


graph algorithm path-finding shortest-path graph-theory
person BlueRaja - Danny Pflughoeft    schedule 13.09.2012    source источник
comment
Одна общая черта, которую разделяют оба ваших примера, — наличие разделителя клик размера 1 или 2. Может Вы думаете о примере, где это не так?   -  person krjampani    schedule 14.09.2012
comment
@jkraju, я не придумал пример, в котором мертвые ячейки (т.е. ячейки, которые не могут быть частью какого-либо кратчайшего пути) не имеют разделителей размера 1 или 2; но легко придумать примеры с разделителями размера 2 для немертвых ячеек.   -  person James Waldby - jwpat7    schedule 14.09.2012
comment
@ jwpat7 Я рассматривал только разделители, которые сохраняют s и f в одном компоненте. Возможно, вы имели в виду двухкликовые разделители, отделяющие s от f? Я согласен, что такой пример легко построить.   -  person krjampani    schedule 14.09.2012

Ответы (2)


arrow_upward
4
arrow_downward

Рассмотрим любой путь из S в F. Этот путь может быть кратчайшим путем (если вы удалите все остальные квадраты), если вы не можете использовать «ярлыки», используя только эти плитки. Это происходит только тогда, когда у вас есть два соседних квадрата, которые не являются соседними на пути. Итак, вам нужно рассмотреть все пары соседних квадратов; все, что они отсоединяют от S или F (не отсоединяя S от F), не может быть частью кратчайшего пути. Кроме того, плитки, которые могут быть разделены одним квадратом, не могут быть частью пути (не повторяющего вершины) из S в F, поэтому они тоже должны идти.

Пусть N будет количеством квадратов в сетке. Для любой конкретной пары квадратов (их O(N)), то, что отключается, может быть вычислено за время O(N) с заполнением, так что это O(N^2). Это дешевле, чем min-cut, о котором вы упомянули, поэтому я предполагаю, что это достаточно дешево для вас.

person Jonathan Paulson    schedule 14.09.2012
comment
Черт, я был так близок к этому решению (см. ответ @Topro)! Мне нравятся оба ответа, но я выбрал этот из-за убедительного доказательства того, что других случаев для рассмотрения нет. Спасибо вам обоим - я реализовал это, и это прекрасно работает! - person BlueRaja - Danny Pflughoeft; 14.09.2012
comment
хороший способ объяснить это. Мой ответ в основном тот же метод, но попытки сделать это в O (N) - однако реализация будет намного сложнее. - person robert king; 15.09.2012

arrow_upward
1
arrow_downward

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

см. случай в вашем примере, это две желтые сетки, которые блокируют точки.

введите здесь описание изображения

блокируется одной сеткой, легко понять. При блокировке двумя:

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

Итак, алгоритм:

перечислить каждую пустую сетку

  1. поставьте на него стену и используйте заливку, чтобы найти заблокированные области, они бесполезны.
  2. попробуйте поставить стену на одну из четырех соседних сеток (если она пуста), используйте заливку, чтобы найти заблокированные области, они бесполезны.
person iloahz    schedule 14.09.2012
comment
Хм, я думаю, что вы правы с этим (с оговоркой, что нам нужно также залить отдельные квадраты, чтобы найти квадраты, которые изначально недоступны. Кроме того, вам нужно проверить только двух соседей, а не четыре) . Все это время я сбивался с толку, потому что желтые квадраты на вашем изображении могут быть частью лучшего пути, но я только что понял, что после заливки мы не рассматриваем два квадрата, в которые мы поместили стены, как часть этого недостижимого пути. площадь. До'х! - person BlueRaja - Danny Pflughoeft; 14.09.2012