zenturion
22 de Abril del 2010
?-hamiltoniano(C).
C=[cd1,cd2,cd3,cd4,cd5,cd6]
?-findall(-C,hamiltoniano(_C),_L),length(_L,N).
N=16.
PRIMERA DEFINICION DE HAMILTON
Hamiltoniano_1(C):-
camino(_,_,C),
nodos(L),
length(L,N),
length(C,N).
SEGUNDA DEFINCION DE HAMILTON
hamiltoniano_2(C):-
nodos(L),
length(L,N),
length(C,N),
camino(_,_,C).
el problema es que no logro interpretarlo bien
si alguien quisiera tomarse la molestia de explicarme que es lo que sucede se lo agradecere mucho.
Ese código es una búsqueda por fuerza bruta con backtracking, típica de Prolog para este tipo de problemas de grafos. Lo interesante para entenderlo es separar las dos partes:
camino(_,_,C) genera (por backtracking) una posible secuencia de nodos C que forma un camino válido en el grafo, probando combinaciones y descartando las que no cumplen las reglas (normalmente: no repetir nodo, y que exista arista entre cada par consecutivo). Cada vez que Prolog encuentra un callback fallido, retrocede (backtrack) y prueba la siguiente combinación posible, hasta agotar todas.
findall(-C, hamiltoniano(_C), _L) no busca solo un camino, fuerza a Prolog a encontrar todas las soluciones posibles (todos los caminos hamiltonianos distintos) y las va acumulando en la lista _L. Por eso el resultado es N=16: hay 16 caminos hamiltonianos distintos en ese grafo de 6 nodos.
El motivo de que este enfoque funcione bien aquí es que 6 nodos es un tamaño pequeño. El problema del camino hamiltoniano es NP-completo, y esta búsqueda por fuerza bruta explora esencialmente todas las permutaciones posibles de nodos filtrando las inválidas, así que el número de combinaciones a probar crece factorialmente con el número de nodos. Con 6 nodos son pocas, pero si tu grafo crece a 15-20 nodos, este mismo código puede tardar minutos u horas. Para grafos más grandes hace falta poda más agresiva (cortar ramas en cuanto se detecta que no pueden llevar a una solución válida) en vez de generar y filtrar al final.
Marta