Programación de Conjunto de Respuestas – filtración de modelos de grandes cantidades.
instance.lp
node(1). node(2). node(3). node(4). node(5). node(6).
edge(1,2). edge(2,1). edge(4,1). edge(2,3). edge(2,6).
edge(3,4). edge(3,5). edge(5,6). edge(6,3).
begin(4).
Tengo esta instancia del problema, un grafo dirigido con un nodo de inicio begin(4) y las aristas correspondientes. En este grafo, solo es posible obtener un ciclo hamiltoniano comenzando desde el nodo 4 (4->1->2->3->5->6 or 4->1->2->6->5->3) y mi clase de problema solo puede resolverlo si le doy el nodo de inicio 4, y devuelve 2 modelos como este:
class.lp
% generate
{path(X,Y)} :- edge(X,Y).
% define
reached(X) :- begin(X).
reached(Y) :- reached(X), path(X,Y).
% test
:- node(X), not reached(X).
:- path(X,Y), path(X,Y1), Y!=Y1.
:- path(X,Y), path(X1,Y), X!=X1.
cuando lo ejecuto así con clingo:
clingo class.lp instance.lp 0
Obtengo 2 modelos (ciclos hamiltonianos).
Quiero ejecutarlo sin darle el punto de inicio, pero cuando reemplazo begin(X) con node(X):
.
.
% define
reached(X) :- node(X).
reached(Y) :- reached(X), path(X,Y).
.
.
Obtengo 120 modelos.
Mi suposición es que ahora genera todas las combinaciones posibles y tengo que agregar una restricción adicional para filtrar la solución correcta.
¿Cómo filtro los dos modelos correctos de este conjunto de respuestas?
davy.ai
Para filtrar los dos modelos correctos de los 120 modelos generados por la versión actualizada del programa sin un punto de partida especificado, puede agregar una restricción para asegurarse de que el ciclo hamiltoniano comience y termine con el nodo 4.
Puede agregar la siguiente restricción a la sección
testdel programa:Esta restricción asegurará que el ciclo debe incluir el nodo 4, lo que asegura que comience y termine con el nodo 4.
El programa
class.lpactualizado con esta restricción se vería así:Al ejecutar este nuevo programa con
clingo class.lp instance.lp 0solo se generarán los dos modelos correctos para el ciclo hamiltoniano que comienza desde el nodo 4.