Si un mapa del juego está dividido en subgrafos, ¿cómo minimizar los bordes entre subgrafos?

Tengo un problema, estoy tratando de hacer búsquedas A * a través de un juego basado en cuadrícula como pacman o sokoban, pero necesito encontrar "recintos". ¿Qué quiero decir con recintos? subgrafos con tan pocosbordes cortados como sea posible dado un tamaño máximo y un tamaño mínimo para el número de vértices para cada subgrafo que actúan como restricciones suaves.
Alternativamente, podría decir que estoy buscando puentes entre subgrafías, pero generalmente es el mismo problema.

Ejemplo

Ejemplo de mapa de juego basado en cuadrícula http://dl.dropbox.com/u/1029671/map1.jpg

Dado un juego que se parece a esto, lo que quiero hacer es encontrar recintos para poder encontrar adecuadamente las entradas a ellos y así obtener una buena heurística para alcanzar los vértices dentro de estos recintos.

texto alternativo http://dl.dropbox.com/u/1029671/map.jpg

Entonces, lo que quiero es encontrar estas regiones coloreadas en cualquier mapa dado.

Mi motivación

La razón por la que me molesto en hacer esto y no solo en contentarme con el rendimiento de una simple heurística de distancia de Manhattan es que una heurística de cerramiento puede dar resultados más óptimos y no tendría que hacer la A * para obtener algunos cálculos de distancia adecuados y también para luego agregar el bloqueo competitivo de los oponentes dentro de estos recintos al jugar juegos de tipo sokoban. Además, la heurística del recinto se puede utilizar para un enfoque minimax para encontrar vértices de meta más adecuadamente.

Solución posible

Una posible solución al problema es elAlgoritmo de 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)

Mi problema con este algoritmo es su tiempo de ejecución en O (n ^ 2 * lg (n)), estoy pensando en limitar los nodos en A1 y B1 al borde de cada subgrafo para reducir la cantidad de trabajo realizado.

Tampoco entiendo el costo c [a] [b] en el algoritmo, si a y b no tienen una ventaja entre ellos, se supone que el costo es 0 o infinito, o debería crear una ventaja basada en alguna heurística.

¿Sabes qué se supone que es c [a] [b] cuando no hay borde entre a y b? ¿Crees que mi problema es adecuado para usar un método multinivel? ¿Por qué o por qué no? ¿Tiene una buena idea de cómo reducir el trabajo realizado con el algoritmo kernighan-lin para mi problema?