У меня есть проблема, я пытаюсь сделать*, перерывает основанную на сетке игру как pacman или sokoban, но я должен найти "корпуса". Что я подразумеваю под корпусами? подграфы с как можно меньшим количеством краев сокращения, учитывая максимальный размер и минимальный размер для количества вершин для каждого подграфа, которые действуют как мягкие ограничения.
Кроме того, Вы могли сказать, что я надеюсь находить мосты между подграфами, но обычно та же проблема.
Пример Gridbased gamemap http://dl.dropbox.com/u/1029671/map1.jpg
Учитывая игру, которая похожа на это, что я хочу сделать, корпуса находки так, чтобы я мог правильно найти входы им и таким образом получить хорошую эвристику для достижения вершин в этих корпусах.
сопроводительный текст http://dl.dropbox.com/u/1029671/map.jpg
Таким образом, то, что я хочу, должно найти эти цветные регионы на любой данной карте.
Причина для меня потрудившийся делать это и не просто остающееся содержание с работой простой манхэттенской эвристики расстояния - то, что эвристика корпуса может дать более оптимальные результаты, и я не должен был бы на самом деле делать* для получения некоторых надлежащих расчетов расстояния и также для более позднего добавляющего конкурентоспособного блокирования противников в этих корпусах, играя sokoban в игры типа. Также эвристика корпуса может использоваться для минимаксного подхода к нахождению вершин цели более правильно.
Возможное решение проблемы является алгоритмом 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 [b] стоят в алгоритме, если a и b не имеют края между ними, стоимость, которая, как предполагают, была 0 или бесконечность, или если я создаю край на основе некоторой эвристики.
Вы знаете то, что c [b], как предполагается, - когда нет никакого края между a и b? Вы думаете, что моя проблема подходит для использования много метода уровня? Почему или почему нет? У Вас есть хорошая идея для того, как уменьшить работу, сделанную с kernighan-lin алгоритмом для моей проблемы?
Может быть, взгляните на эту ссылку в Википедии для дальнейшего чтения.
Задача разделения графа в математике состоит в разделении графа на части, так что части примерно одинакового размера и { {1}} есть несколько соединений между частями.
Не уверен в вопросе, но, возможно, вы можете использовать дуальность max-flow / min-cut.
Существуют специализированные и эффективные алгоритмы для максимального потока , которые можно использовать для решения первичной задачи.
Затем вам необходимо получить решение двойного , используя метод, описанный здесь .
PS: дайте мне знать, если вам понадобится помощь с жаргоном исследования операций .