Explicación del problema, Definición formal del problema, Representación del problema, Solución propuesta, Respecto a temas de investigación relacionados, Conclusiones.
Agregado: 29 de AGOSTO de 2000 (Por
) | Palabras: 2972 |
Votar | Sin Votos |
Sin comentarios |
Agregar ComentarioCategoría:
Apuntes y MonografÃas >
Computación >
Varios >
Material educativo de Alipso relacionado con
partición grafoSucesiones: acompana avaluo, inventario y particion.: Sucesiones: renuncia termino.solicita aprobacion de la operacion de inventario y avaluo y particion y adjudicacion de bienes.: Biografia y vida de Timón el Silógrafo: Breve Biografia de Timón el SilógrafoEnlaces externos relacionados con
partición grafo
Universidad Técnica Federico Santa
María
Departamento de Informática
Inteligencia Artificial
Trabajo de Investigación
"k partición de un grafo"
Daniel Prieto
Valparaíso, Noviembre de 1999
Introducción
En el ámbito de la solución a
situaciones reales por medio de algoritmos basados en técnicas de Inteligencia
Artificial, para todos es claro que nadie a dicho la "última palabra" en
materia de eficacia y robustez de algoritmos. Lo anterior se debe a la "peculiaridad" que cada situación representa en
la realidad, porque cada una de ellas tiene sus propias "variables" las cuales
determinan lo que podría o no modificarse, y además, cada una de estas variables tiene su propio rango de acción;
su propio dominio definido.
Existen innumerables situaciones que
eventualmente se podrían implementar usando un algoritmo de los descritos
anteriormente. En el informe anterior,
explicamos una situación característica de los grafos, un típico problema de resolución
en tiempo NO polinomial. Este consistía
en que dado un grafo determinado con arcos conectados, hacer una "bipartición"
de este con en dos "subgrafos" con el mismo número de nodos cada uno con el
propósito de minimizar la cantidad de arcos que relacionarían ambos subgrafos. No cabe duda que, como se ejemplificó en el
informe anterior, esto tiene un sinnúmero de posibles usos. En vista de lo estudiado anteriormente,
discutimos esto con el profesor guía del tema y hemos llegado a la conclusión
de que esta "aplicación" es un caso específico de otro aun más general.
Por lo
anteriormente estipulado las aplicaciones de este nuevo caso, aun más general,
serían mucho más grandes sin perder de vista la especificación de las variables
mencionadas en el inciso anterior.
A
continuación el informe de la "nueva" aplicación.
Explicación del problema
En esta
oportunidad tengo en el tapete el mismo grafo solicitado en el informe
anterior, solo que esta vez lo dividí no en 2 subgrafos, sino que en "k" subgrafos diferentes. Además de esto los arcos tienen un peso, una
ponderación, que les da un cierto orden entre los de su especie.
Ahora bien, a
manera de recordatorio, el objetivo principal propuesto en e el informe
anterior para ese ejemplo específico, era particionar un grafo en 2 (con una
cantidad de nodos cada uno) y minimizar el número de arcos de conexión entre
ambos subgrafos(ver figura).
Como lo mencioné
en la introducción, este problema básicamente fue descartado debido a que nos
dimos cuenta de que su aplicación era bastante limitada. Optamos mejor por expandir las fronteras y
observar hasta donde podríamos llegar en la realidad y sin duda que existen
otras aplicaciones con una capacidad de abarcar un rango más amplio de
situaciones reales.
Partición de grafos en "k"
subgrafos
Si yo decido
dividir el grafo en "k" subgrafos con un numero determinado de nodos cada uno,
y definimos un valor de k=2, entonces tenemos el caso anterior, siempre y
cuando el objetivo final sea minimizar el número de arcos que conectan ambos
subgrafos.
Ahora modificare
más aun el problema dedicándonos al objetivo en sí. Según preví, la situación da para muchas interpretaciones desde
el punto de vista de que es lo que se desea. Por esto a continuación doy unos cuantos puntos de vista de que es lo
que se desea hacer con un grafo determinado después de haberlo particionado en
"k" subgrafos con el mismo número de nodos cada uno.
§
Nodos con un peso específico y los arcos sin peso: si se desea buscar
un objetivo claro a este planteamiento, podríamos decir que queremos un parcelamiento de los k subgrafos con el
fin de obtener subgrafos con el mismo peso, quizás con la intención de generar
una especie de equilibrio del grafo e general. No me convence esta visión del problema porque aparte de ser muy difícil
de encontrarle una utilidad real, no presenta mayor dificultad de resolución.
§
§
Nodos con un peso específico al igual que los arcos del grafo: esta
situación es sin duda más compleja que la anterior. Lo principal es fijarse en
que es lo que realmente nos interesa, o bien un objetivo basado directamente en
los nodos(como el caso anterior) o bien basado en los arcos del grafo. Si nos situamos en los nodos como referencia
no tenemos mucho que portar. Pero si no
situamos en los arcos podríamos darnos cuenta que el peso de los nodos no hacen
más que entorpecer la funcionalidad de un objetivo sobre los arcos, por esto se
eligió solo pesos de arcos, ya que pesos sobre nodos sería una caso específico
del caso con arcos con peso.
§
Nodos sin peso y arcos con un peso específico: este es el caso que más adecuado me pareció
debido a que tiene una mayor cantidad de aplicaciones prácticas, y tiene un
objetivo claro y de óptimas condiciones para aplicar una técnica de algoritmo
inteligente.
Descripción
del problema en detalle(nodos sin peso y arcos con un peso específico)
Hasta el momento
tenemos claro ciertos aspectos del problema. Retomando, dije que tenemos un grafo con "n" nodos. Este es un grafo completamente conexo en el
cual los arcos tienen un peso específico.
Dadas las anteriores
características podemos formalizar aun más la situación y expondré que el
principal objetivo es dividir el grafo en "k" subgrafos con una cantidad de
nodos diferentes, y la condición principal es que los arcos entre los
subgrafos.(ver figura)
¿Porque IA para este tipo de problemas?
Este tipo de problemas tal y como se
describió acá, es un tipo de problemas que se resuelve en tiempo NO
polinomial(problema de tipo NP). A
medida que crece el número de variables, el tiempo de resolución total aumenta
en forma exponencial. Generalmente esto
ocurre en gran medida para problemas de optimización. En cambio, si este fuese un problema de satisfacción de restricciones solamente, a pesar de que se
trata con heurísticas parecidas, es más probable que se llegue a la solución
más rápidamente que con el otro método que además de pedir una solución, pide
la óptima.
Si se intentara resolver esto con
métodos tradicionales existentes, el problema radicaría en como representar las
restricciones adecuadamente. Las
restricciones varían de acuerdo a la especificación del problema, entonces, si
yo quisiese implementar una solución a esta situación debo basarme
necesariamente en su especificidad: sus restricciones.
Por otro lado, como abordé esta
situación con una técnica de IA tuve que adaptar la metodología y así generar
un algoritmo robusto SOLO para problemas como los míos. Lo que hice fue hacer una mezcla de Hill
Climbing con restart incluido y algo Algoritmo voraz todo esto para darle más
eficacia a el método resolutivo.
Definición formal del problema
A continuación el
Objetivo, variables, dominios, restricciones y función objetivo del problema
planteado.
Objetivo
Dado un grafo de
"n" nodos completamente conexo y sus arcos con un peso determinado. El objetivo es dividir el grafo K
subgrafos. Todos estos subgrafos deben
tener incorporados a lo menos 2 nodos y a lo más el doble de los nodos que habría
de existir en cada subgrafo si se divide el grafo total en K subgrafos de igual
cantidad de nodos. La principal idea y
final es que estos subgrafos al quedar conectados entre sí por arcos, tengan el
menor grado de cohesión posible, es decir, que los arcos que unen los subgrafos
pesen lo menos posible y de esa manera poder evitar una cierta "dependencia
trascendental" entre ellos.
Variables
En cuanto a
la información de los nodos
Xif :representa al nodo i que pertenece al subgrafo f
i = {1,2,3,... ,n}
f = {1,2,3,... ,l}
l : # total de grafos
n: # total de nodos
En cuanto a
la información de los arcos
pij :representa al peso o ponderación del arco que sustentan los arcos
"i" y "j"
i = {1,2,3,... ,n}
j = {1,2,3,... ,n}
Dominios
Estos
son pesos discretos entre 1 y 100
,si el nodo "i" NO pertenece al
subgrafo "j"
,si el nodo "i" SI pertenece al subgrafo "j"
Restricciones
Básicamente la única restricción
trascendental es que hay un número mínimo y máximo de nodos pertenecientes a
cada subgrafo, a continuación las definiciones formales.
Vemos que la
cantidad máxima de nodos, sumadas todas las variables, es "n"
Donde "l" es el
número promedio de nodos por subgrafo si se desea una partición de "k"
subgrafos sobre un total de "n" nodos.
Para un
determinado subgrafo "f" la cantidad de nodos esta limitada por "abajo" con 2 y
"arriba" con 2l. Esto para no disparar
la cantidad de nodos agrupada.
La función objetivo
Esta función
objetivo como ya se señaló en una oportunidad pretende minimizar los arcos de
conexión entre subgrafos. Lo anterior
es equivalente a analizar su complemento también, o sea, intentar maximizar el
peso de los arcos que pertenecen a un subgrafo. Por lo tanto la función objetivo sería la siguiente
Ahora, a esta
función objetivo le vamos a incorporar una penalización, relativa a la
restricción de que tiene un número mínimo y máximo de nodos por subgrafo. Esta referencia no la habíamos mencionado
anteriormente porque que se basa en un subjetivismo personal de la solución final. Acá pienso, y que sería muy cómodo(aunque
todo depende del contexto donde se este desarrollando la aplicación), que la
mayoría de los nodos por subgrafo se mantenga constante en a lo largo del grafo
en general, digo esto porque en la realidad lo lógico de una aplicación de este
tipo es que se tienda a esto.
Representación del problema
La forma de representar el grafo será por medio de
una matriz de conectividad, donde cada casillero indicará el peso de los arcos
que sustentan los nodos señalados en la fila y la columna en particular(ver
figura).
|
1
|
2
|
3
|
|
|
n
|
1
|
-
|
0
|
12
|
|
|
5
|
2
|
0
|
-
|
67
|
|
|
0
|
3
|
12
|
67
|
-
|
|
|
99
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n
|
5
|
0
|
99
|
|
|
-
|
En la figura
anterior los casilleros que indican "0" implica que entre el nodo
"i"(perteneciente a la fila) y el nodo "j"(perteneciente a la columna) no
existe un arco que los sustenta. Por el
contrario aquellos casilleros distintos de "0" con un valor "X" implica que SI
existe un arco entre el nodo "i"(fila) y "j"(columna) y cuyo peso es "X"(valor
que fluctúa entre 1 y 100).
Para llevar a
cabo un "camino" hacia una solución debemos definir la representación de una
solución provisoria. Vamos a definir un individuo.
X1
|
X2
|
X3
|
X4
|
X5
|
X6
|
|
|
|
|
Xn
|
1
|
3
|
4
|
k
|
6
|
12
|
|
|
|
|
2
|
Donde para
llenar cada una de las casillas multiplicaremos la variable por "f"(# de subgrafo)
X11*1=1,
X23*3=3, X34*4=4, X4k*k=k,....., Xn2*2=2
Otra cosa
importante es como vamos a ir llenando(método) esta solución para generar un
primer individuo y así poder ir formando poblaciones, ¿porque esto?, tan simple
porque si elegimos términos aleatorios, estos seguramente van a costar caro
debido a que no van a respetar las restricciones, luego las verificaciones que
se vendrán a posteriori por cada instanciación de una situación inicial,
tendremos el mismo proceso una y otra vez.
Por lo anterior,
pienso que un algoritmo voraz es lo adecuado para obtener una primera situación
inicial.
Pienso que
posibilidades de resolución hay muchas, es más, todas las vistas en clases
sirven para encontrar una solución sin necesariamente perder de vista lo del
algoritmo voraz. Debido a la
experiencia que tengo del tema podría señalar que una combinación de algoritmo
voraz y Hill Climbing con restart daría buenos resultados.
Hill Climbing
Hilando un poco
más fino en lo que respecta a la solución del problema, señalaremos que acá
existen dos instancias de iteración:
§
La respecta a la cantidad de "restart" que se van a hacer, lo cual le
da el grado de exploración del problema.
§
Por otra parte, esta la cantidad de iteraciones que se harán para
realizar mutaciones sobre una determinada variable con el fin de ir siempre
aumentando el valor de la función de objetivo.
Solución propuesta
En este momento
la cancha ya esta rayada, por lo tanto, a continuación asiento el problema
planteando el algoritmo resolutivo de la k partición de un grafo.
Paso 1: definición constantes
rmax: = # máximo de iteraciones relativas a "restart"
emax = # máximo de iteraciones relativas a
mejores soluciones(explotación).
mejor_solucion = vacío
Paso 2: si rmax > 0
Generar una solución
inicial con un algoritmo voraz
sino
ir al Paso 4
Paso 3: si emax > 0
Seleccionar una variable
Xi
Buscar un valor del
dominio que mejore la función objetivo según una heurística
si existe un
valor
mejor_solucion
= sol. con nuevo valor
emax = emax -
1
ir al Paso 3
sino
emax = 0
sino
rmax = rmax -- 1
ir al Paso 2
Paso 4: Retornar mejor_solucion
Terminar
Respecto a temas de investigación
relacionados
Para ser sincero,
averigüé con profesores del departamento y recibí algunas ideas que me
sirvieron para interpretar el problema. Además, busque mucho material con el fin de poder encontrar información
de nuevas técnicas evolutivas más originales y novedosas. Existen muchas pero en el ámbito de
multiparticionamiento de grafos encontré un solo paper.
Me use en
contacto con Rina Dechter por medio de correo electrónico con el propósito
de darme algunos materiales. Felizmente ella no vaciló en prestarme ayuda
y recibí algunos papers donde mi trabajo tenía alguna relación. No sé si sea el
momento adecuado para señalarlo pero recibí un paper(de ella) donde explicaba
todos los métodos de recorrido de grafos que nosotros estudiamos en clases.
En uno de los
paper que ella me mandó encontré a un multiparticionamiento de grafos fue el
particionamiento de grafos en DOS subgrafos con el principal objetivo es
minimizar el peso del total de arcos que unen ambos subgrafos y también el
multiparticionamiento con el mismo objetivo que yo tengo planteado.
Vi que acá se
aplica un algoritmo resolutivo denominado "Bottleneck algorithm"(algoritmo
cuello de botella). Este algoritmo es
capaz de resolver los problemas en un tiempo polinomial debido a una función de
decisión adecuada denominada "test", PERO esta función "test", que es una
decisión que realiza el algoritmo en tiempo NP.
Veremos la
definición de la generalización del problema de particionamiento del grafo
"bottleneck".
Las instancias
son:
G=(V,E), grafo
con V vértices y E arcos
k=1... k, numero de subgrafos
Wj=
subconjunto de nodos que forman el subgrafo
fj(n),gj(n)
especifican los máximos y mínimos peso por subgrafo "j"
V1,... ,Vk
subparticiones del grafo.
Deben satisfacer
que " j: gi(n)£ |Vj| £fj(n), y Wj
[DP1]í Vj.
Acá tenemos un
función de Test que diría:
Test(Gi):
¿es acaso Gi una partición de componentes conexas que resulte una
partición legal?
Y su algoritmo
sería:
1.- Sea C un set
de componentes conexas de Gi
2.- Inicializa Vj
= f, j=1,... ,k
3.- for cada c Î C
a) si existe j1¹j2 tal que (CÇW1¹f) y (CÇW2¹f) entonces
retornar "NO"
STOP
b) if (CÇW1¹f)
C = C - {c}
fj(n) = fj(n) - {c}
gj(n) = gj(n) - {c}
Vj = Vj É {c}
4.- llamar a
k-subgrafo-suma con Aj=fj(n) y Bj=gj(n),
j=1,...,k
si k-subgrafo-suma retorna "NO"
entonces
retorna "NO"
sino
retorna "SI"
(Vj = Vj É
Sj, donde Sj contiene las componentes elegidas
para es el
subgrafo j)
Como ya señalamos anteriormente, en
general el problema de la partición del grafo "bottleneck" es un problema que
se resuelve en tiempo polinomial, a pesar de esto, este es un problema que se
soluciona en tiempo NP-duro. En nuestro
caso el algoritmo "bottleneck" descrito lo resuelve en un tiempo pseudo
polinomial, del orden de O(n2log(n)), donde n es el número de
vértices del grafo. Si se trata de
grafos densos este tiempo de resolución es asintóticamente óptimo a cualquier
algoritmo que requiera un ordenamiento del peso de los arcos con un orden mas o
menos de O(mlog(m)), por supuesto que este no es nuestro caso.
Conclusiones
Debido a mis
problemas de organización no pude investigar más con detalle la existencia de
trabajos respecto al tema presentado en este informe, además me hubiese gustado
también generar un programa en un lenguaje de programación.
Puedo inferir
que, por algo que leí en algún paper relativo al porque no "mas dedicación" de
los investigadores a este tema, el futuro de este punto específico ya terminó,
se habla mas de una bipartición como base de futuros proyectos pero no sé, en
lo personal, de futuros proyectos basados en la k partición de un grafo.
Creo que de todas
las técnicas que yo conozco, la combinación que yo elegí acá fue la mas
adecuada porque es un método relativamente robusto que no requiere de muchos
cálculos, no así como lo hubiese sido alguna implementación basada en
algoritmos genéticos.
Comentarios de los usuarios
Agregar un comentario:
Aún no hay comentarios para este recurso.