Componenti collegati di un grafico usando Prolog

Question

Componenti collegati di un grafico usando Prolog

#1 da (2 voti)
#2 da (0 voti)

1

Dato un angolo x di un grafico non orientato G Vorrei chiedere il componente connesso di x , ma il mio primo tentativo non funziona come desiderato. Eccolo:

edge( a,b ).
edge( b,a ).

edge( b,c ).
edge( c,b ).

edge( c,d ).
edge( d,c ).

connected( X,X ).
connected( X,Y ) :- edge(X,Y).
connected( X,Y ) :- \+ edge(X,Y), edge( X,Z ), connected( Z,Y ).

E qui ci sono le mie domande e i risultati:

| ?- connected(b,What).

What = b ? ;

What = a ? ;

What = c ? ;

no

| ?- connected(b,b).   

true ? ;

true ? ;

true ? ;

no

Perché l'angolo b non è connesso all'angolo d ? Perché l'angolo b è connesso a se stesso tre volte? Ho paura di altri problemi che otterrò con grafici più complessi. Ce ne sono?

graph prolog

posta Ronin Tom 20.06.2013 - 16:58

fonte

2 risposte

Leggi altre domande sui tag graph prolog

Potrei avere un esempio reale di utilizzo del modulo di scripting Spring nella tua applicazione Java? Motivo di progettazione per la creazione di viste complesse in spartiti

score 2 · Answer 1

In sostanza, stai utilizzando \+ troppo presto (e non dovresti utilizzarlo in primo luogo).

Traccia l'esecuzione della tua query e vedrai che la prima risposta viene dalla prima clausola, e la seconda dalla seconda, ma la tua terza clausola non ha mai successo. Perché? Perché chiedi al sistema di dimostrare che edge(b,Variable) non è vero, ma è vero, ad esempio tramite edge(b,a) . Il fatto che il tuo What sarebbe in seguito associato a un altro valore se l'elaborazione continuata è irrilevante - nel momento in cui lo abbini, non è vincolato, quindi il edge ha esito positivo, e quindi il \+ fallisce e interrompe l'elaborazione.

Questo è anche il motivo per cui \+ è l'approccio sbagliato qui; per elaborare grafici arbitrari, non c'è modo di programmare la ricorsione illimitata, e quindi è necessario tenere traccia dei nodi che hai già provato in modo da non rimanere bloccati in cicli infiniti. La soluzione più semplice aggiunge un altro parametro al caso ricorsivo che fa questa contabilità.

score 0 · Answer 2

La prima clausola potrebbe rimanere la stessa se vuoi dimostrare un caso speciale, dove il nodo X si connette a X.

È mia opinione che le clausole del terzo predicato cercherebbero letteralmente il vantaggio reciproco di EXACTLY ONE , rendendolo più hard-coded. Potresti renderlo dinamico rendendolo ricorsivo.

  connected( X,Z ) :-
     edge(X,Y),
     connected(Y,Z). % This line would fail when the program can no longer find an edge that Y connects to.%

Quando fallisce, (il secondo predicato nella tua risposta deve essere qui), stai chiedendo al programma di avere successo soddisfacendo che è riuscito a trovare l'ultimo nodo a cui potrebbe indirizzare.

      connected ( X,Z ) :-
         edge(X,Z).