Если игровая карта разбита на подграфы, как минимизировать границы между подграфами?
У меня проблема, я пытаюсь сделать 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 нет ребра?
Как вы думаете, моя проблема подходит для использования многоуровневого метода? Почему или почему нет?
У вас есть хорошая идея, как уменьшить объем работы, выполняемой с помощью алгоритма kernighan-lin для моей проблемы?