Создание лабиринта для защиты башни (самый длинный лабиринт с ограниченными стенами) - почти оптимальная эвристика?

Ответ 1

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

Чтобы превратить его в график, возьмите двойной лабиринт. Найдите минимальную (s, f) вершину, вырезанную на этом графике. Затем мы исследуем каждую вершину в этом разрезе. Мы удаляем вершину, ее удаление увеличивает длину всех путей s, f или если она находится в пути минимальной длины от s до f. После удаления вершины рекурсивно повторите описанный выше процесс для k времени.

Но есть проблема с этим, это когда мы удаляем вершину, которая разрезает любой путь от s до f. Чтобы предотвратить это, мы можем максимально сократить вес node, это означает, что сначала вычисляется минимальный (s, f) срез, если результат разреза - всего лишь один node, сделать его взвешенным и установить большой вес, как n ^ 3, вершина, теперь снова вычисляем минимум s, f cut, единственная режущая вершина в предыдущем вычислении не принадлежит к новому разрезу из-за ожидания.

Но если есть только один путь между s, f (после некоторых итераций), мы не можем его улучшить. В этом случае мы можем использовать обычные жадные алгоритмы, такие как удаление node с одного из кратчайшего пути от s до f, который не принадлежит ни одному разрезу. после этого мы можем справиться с минимальным разрезом вершины.

Время работы алгоритма на каждом шаге:

min-cut + path finding for all nodes in min-cut
O(min cut) + O(n^2)*O(number of nodes in min-cut)

И поскольку число узлов в min cut не может быть больше O (n ^ 2) в очень пессимистической ситуации, алгоритм O (kn ^ 4), но обычно он не должен принимать больше O (kn ^ 3), так как обычно алгоритм минимального разреза доминирует в поиске пути, также обычно поиск пути не принимает O (n ^ 2).

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

PS: минимальный разрез вершины похож на минимальный разрез края, и подобный подход, такой как max-flow/min-cut, может быть применен к минимальному разрезу вершины, просто предположим, что каждая вершина имеет две вершины, одну V _i, один V _o, означает ввод и вывод, также преобразование неориентированного графика в направленное одно не сложно.

Ответ 2

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

Но есть больше оптимизаций. Вы также можете всегда решить, что вы поместите следующую блокаду, чтобы она стала ПЕРВОЙ блокировкой на текущем маршруте минимальной длины, т.е. Вы работаете так, что если вы поместите блокаду на 10-й квадрат на маршруте, то вы пометьте квадраты 1..9 как "постоянно открытые", пока вы не отступите. Это снова сохраняет экспоненциальное число квадратов для поиска во время поиска в обратном направлении.

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

Ответ 3

Я считаю, что мы можем уменьшить содержащуюся проблему максимального многообразия до boolean satisifability и показать NP-полноту через любую зависимость от этой подзадачи. Из-за этого алгоритмы spinning_plate, предоставленные, являются разумными, поскольку эвристика, предварительная компьютерная обработка и машинное обучение являются разумными, а трюк становится нахождение наилучшего эвристического решения, если мы хотим промахнуться здесь.

Рассмотрим следующую плату:

..S........
#.#..#..###
...........
...........
..........F

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

#.#..#..###

Наши логические логики находятся в 2D-массиве на основе 0, упорядоченном как [row][column]:

[1][4], [1][5], [1][6], [1][7], [1][8]

Мы можем повторно представить это как уравнение для удовлетворения блока:

if ([1][9] AND ([1][10] AND [1][11]) AND ([1][12] AND [1][13]):
    traversal_cost = INFINITY; longest = False # Infinity does not qualify

За исключением бесконечности как неудовлетворительного случая, мы возвращаемся назад и ретранслируем это как:

if ([1][14] AND ([1][15] AND [1][16]) AND [1][17]:
    traversal_cost = 6; longest = True

И наши скрытые логические отношения попадают среди всех этих ворот. Вы также можете показать, что геометрические доказательства не могут фракционализироваться рекурсивно, потому что мы всегда можем создать стену, которая имеет ровно N-1 ширину или высоту, и это является важной частью решения во всех случаях (поэтому divide and conquer не поможет вам).

Кроме того, поскольку возмущения в разных строках значительны:

..S........
#.#........
...#..#....
.......#..#
..........F

Мы можем показать, что без полного набора вычислимых геометрических тождеств полное пространство поиска сводится к N-SAT.

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

Обратите внимание, что вы можете значительно уменьшить n-член в отношении n-select-k. Поскольку мы можем рекурсивно показать, что каждое возмущение должно лежать на критическом пути и потому, что критический путь всегда вычисляется в O (V + E) времени (с несколькими оптимизациями для ускорения процесса для каждого возмущения), вы можете значительно сократить свои поиск пространства за счет поиска в ширину каждой дополнительной башни, добавленной к доске.

Поскольку мы можем с высокой вероятностью считать O (n ^ k) для детерминированного решения, эвристический подход является разумным. Мой совет, таким образом, находится где-то между spinning_plate answer и Soravux, с прицелом на методы машинного обучения, применимые к проблеме.

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

Решение 1-го порядка: используйте базу данных. Учитывая формулировку проблемы, вы не совсем доказали необходимость вычисления оптимального решения "на лету". Поэтому, если мы расслабляем ограничение приближения к случайной доске без информации, мы можем просто предкоммутировать оптимальный для всех K допустимый для каждой платы. Очевидно, что это работает только для небольшого количества плат: с V! потенциальными состояниями платы для каждой конфигурации, мы не можем с высокой степенью предкомпрометировать все оптимумы, так как V становится очень большим.

Решение 2-го порядка: используйте шаг машинного обучения. Содействуйте каждому шагу по мере того, как вы закрываете разрыв, который приводит к очень высокой стоимости обхода, до тех пор, пока ваш алгоритм не сходится или не будет найдено более оптимального решения, чем жадные. Здесь применимо множество алгоритмов, поэтому я рекомендую преследовать классику и литература для выбора правильного, который работает в рамках ограничений вашей программы.

Лучшая эвристика может быть простой тепловой картой, созданной локальным государственным рекурсивным обходом глубины, сортируя результаты по большинство из них, как правило, пересекаются после обхода О (V ^ 2). Выполняя этот вывод, он с жадностью идентифицирует все узкие места, и сделать это, не делая невозможных путей, вполне возможно (проверка этого - O (V + E)).

Объединяя все это, я бы попытался перекрещиваться с этими подходами, объединив тепловую карту и идентификаторы критического пути. Я бы предположил, что здесь достаточно, чтобы придумать хорошее функциональное геометрическое доказательство, удовлетворяющее всем ограничениям проблемы.

Ответ 4

Рискуя заявить очевидное, здесь один алгоритм

1) Find the shortest path
2) Test blocking everything node on that path and see which one results in the longest path
3) Repeat K times

Наивно, это займет O (K * (V + E log E) ^ 2), но вы могли бы с некоторой небольшой работой улучшить 2, только пересчитывая частичные пути.

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

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

1) Find the shortest path 
2) Find the min-cut of the whole graph
3) Find the maximal contiguous node set that intersects one point on the path, block those.
4) Wash, rinse, repeat

3) - большая часть, и почему этот алгоритм также может плохо работать. Вы также можете попробовать

• самый маленький node набор, который соединяется с другими существующими блоками.
• нахождение всех группировок смежных вершин в вершине разреза, тестирование каждого из них для самого длинного пути a la первого алгоритма

Последнее, что может быть наиболее перспективным

Если вы найдете минимальную вершину, вырезанную на весь график, вы найдете точки задувания для всего графика.

Ответ 5

Вот мысль. В вашей сетке группируйте соседние стены на острова и обрабатывайте каждый остров в виде графика node. Расстояние между узлами - это минимальное количество стенок, которые необходимы для их соединения (чтобы заблокировать врага).

В этом случае вы можете начать максимизировать длину пути, заблокировав самые дешевые дуги.

Ответ 6

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

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

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

Используйте трассировку лучей, чтобы увидеть, какие другие острова могут попасть в свет.

say Island1 (i1) попадает в i2, i3, i4, i5, но не попадает в i6, i7..

тогда у вас будет строка (i1, i2), строка (i1, i3), строка (i1, i4) и строка (i1, i5)

Отметьте расстояние всех точек сетки до бесконечности. Задайте начальную точку как 0.

Теперь используйте первый поиск по ширине с самого начала. Каждая точка сетки отметьте расстояние этой точки сетки минимальным расстоянием от ее соседей.

Но вот вот уловка.

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

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

Ответ 7

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

Если вы можете сделать это заранее, а затем просто сделайте AI, создайте камень лабиринта скалой, как если бы это было какое-то дерево, вы могли бы использовать генетические алгоритмы, чтобы облегчить вашу потребность в эвристике. Вам нужно будет загрузить любую структуру генетического алгоритма, начните с совокупности несдвижных блоков (ваша карта) и случайных перемещаемых блоков (блоков, которые будет размещать ИИ). Затем вы развиваете население, делая переходы и трансмутации над движущимися блоками, а затем оцениваете индивидуумов, давая больше вознаграждения за рассчитанный самый длинный путь. Тогда вам просто нужно написать ресурс-эффективный калькулятор пути, не требуя эвристики в вашем коде. В вашем последнем поколении вашей эволюции вы бы взяли человека самого высокого ранга, которое было бы вашим решением, таким образом, ваш желаемый шаблон блока для этой карты.

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

Вы не указали язык, на котором вы собираетесь разработать этот алгоритм, поэтому я не могу предложить рамки, которые вполне могут удовлетворить ваши потребности.

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

Ответ 8

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

У вас уже есть показатель пригодности по длине пути крипов, поэтому вы можете выбрать лучший из них соответственно. Я не знаю, насколько хорошо (если вообще) это приблизит наилучший путь, но было бы интересно использовать в решении.