Если игровая карта разбита на подграфы, как минимизировать ребра между подграфами?
У меня проблема, я пытаюсь выполнить поиск A* в играх, основанных на сетке, таких как pacman или sokoban, но мне нужно найти «корпуса». Что я имею в виду под корпусами? подграфы с как можно меньшим количеством разрезов с учетом максимального и минимального размера числа вершин для каждого подграфа, которые действуют как мягкие ограничения.
В качестве альтернативы можно сказать, что я ищу мосты между подграфами, но в целом это та же проблема.
Пример
http://dl.dropbox.com/u/1029671/map1.jpg
Учитывая игру, которая выглядит так, я хочу найти ограждения, чтобы я мог правильно найти входы в них и, таким образом, получить хорошую эвристику для достижения вершин внутри этих ограждений.
замещающий текст http://dl.dropbox.com/u/1029671/map.jpg< /а>
Итак, я хочу найти эти цветные регионы на любой карте.
Моя мотивация
Причина, по которой я потрудился сделать это, а не просто довольствоваться производительностью простой эвристики манхэттенского расстояния, заключается в том, что эвристика ограждения может дать более оптимальные результаты, и мне не нужно было бы на самом деле выполнять A *, чтобы получить некоторые правильные расчеты расстояния и также для последующего добавления конкурентной блокировки противников в этих ограждениях при игре в игры типа сокобан. Также эвристику ограждения можно использовать для минимаксного подхода к более правильному поиску целевых вершин.
Возможное решение
Возможным решением проблемы является алгоритм Kernighan Lin:
function Kernighan-Lin(G(V,E)):
determine a balanced initial partition of the nodes into sets A and B
do
A1 := A; B1 := B
compute D values for all a in A1 and b in B1
for (i := 1 to |V|/2)
find a[i] from A1 and b[i] from B1, such that g[i] = D[a[i]] + D[b[i]] - 2*c[a][b] is maximal
move a[i] to B1 and b[i] to A1
remove a[i] and b[i] from further consideration in this pass
update D values for the elements of A1 = A1 / a[i] and B1 = B1 / b[i]
end for
find k which maximizes g_max, the sum of g[1],...,g[k]
if (g_max > 0) then
Exchange a[1],a[2],...,a[k] with b[1],b[2],...,b[k]
until (g_max <= 0)
return G(V,E)
Моя проблема с этим алгоритмом заключается в его времени выполнения при O (n ^ 2 * lg (n)), я думаю об ограничении узлов в A1 и B1 границей каждого подграфа, чтобы уменьшить объем проделанной работы.
Я также не понимаю стоимость c[a][b] в алгоритме, если a и b не имеют ребра между ними, считается, что стоимость равна 0 или бесконечности, или я должен создать ребро на основе некоторой эвристики.
Знаете ли вы, что должно быть c[a][b], когда между a и b нет ребра? Как вы думаете, подходит ли моя проблема для использования многоуровневого метода? Почему или почему нет? У вас есть хорошая идея, как уменьшить работу, выполняемую алгоритмом Кернигана-Лина для моей задачи?
