Ricerca semplice di grafici in Prolog

Question

Sto cercando di codificare una semplice ricerca grafica in SWI-Prolog. Ho pensato al seguente programma:

adjacent(1,4). adjacent(4,2). adjacent(3,6).
adjacent(6,4). adjacent(7,10). adjacent(4,9).
adjacent(5,10). adjacent(7,10). adjacent(7,12).
adjacent(6, 11). adjacent(13,11). adjacent(9,14).
adjacent(14,12). adjacent(10,15). adjacent(9,12).

connected(X,Y) :- adjacent(X,Y); adjacent(Y,X).

path(A,B,[A|B]) :-
    connected(A,B).
path(A,B,[A|R]) :-
    \+member(R,A),
    connected(A,C),
    A \== C,
    path(C,B,R).

Ma questo programma provoca un overflow dello stack. Cosa sto facendo di sbagliato e come può essere corretto?

Answer 1

Stai tentando di utilizzare il percorso restituito anche come controllo per evitare loop. Ciò non funzionerà quando si cerca un percorso perché il percorso non è ancora istanziato alla negazione.

La soluzione più semplice è aggiungere un altro argomento di input in cui si raccolgono i nodi già visitati e li si controlla per evitare ripetizioni.

Inoltre, penso che dovresti selezionare A \ == B invece di A \ == C. Non hai loop sui nodi, quindi quest'ultimo non accadrà mai. Il caso A == B è gestito nella prima clausola, quindi non vuoi farlo di nuovo nella seconda clausola.

Hai anche le argomentazioni del membro all'indietro e devi correggere l'elenco nella prima clausola, come ha scritto Martin.

Un modo avanzato per evitare cicli infiniti senza un argomento in più è usare freeze / 2 sulla negazione.

Guarda anche come funziona il debug in Prolog, che potrebbe aiutarti a capire meglio le cose.

Answer 2

Il problema principale qui è il test dei membri: la firma è member (Element, List) ; sembri supporre che gli argomenti siano al contrario 'round.

Inoltre, il tuo predicato del primo percorso ha lo scopo di testare un elenco di due elementi, tuttavia B si unifica davvero con l'elenco di resto (che quindi non è collegato).

Se li risolvi, scopri che può funzionare solo con variabili completamente istanziate, poiché la negazione non funziona bene con variabili non associate.