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
Monografías
