grafic nedirecționat

Cum pot găsi tot drumul pentru a trece la un grafic nedirecționat?

Graph :

    Node : S, Y, F, T                visualization :    S ----- Y ---- T
    Edge : S --- Y                                       \     /
           Y --- F                                        \   /
           S --- F                                         \ /
           Y --- T                                          F


Assume that

       Start   S 
       Finish  F

       after run   go 

       result will be :

              S F
              S Y F

Nu vreau să vizitez un nod de mai multe ori. Dacă vizitez, această problemă devine una din problemele NP.

EDITAȚI | ×:

intrarea poate fi orice formă

example:

       edge (S,Y).     OR          edge (Y,S).
       edge (Y,F).                 edge (F,Y).
       edge (S,F).                 edge (F,S).
       edge (Y,T).                 edge (T,Y).

ALIMENTAREA TREBUIE SĂ URMEAZĂ

0
ex S Y T Y S ... S Y T ... CÂND se va termina? Poate niciodată
adăugat autor user1428237, sursa
Ce vrei sa spui prin "Daca vizitez, aceasta problema devine una din problemele NP"?
adăugat autor Fred Foo, sursa
Ce legătură are asta cu NP?
adăugat autor Fred Foo, sursa
Au fost adăugate mai multe etichete descriptive.
adăugat autor Junuxx, sursa

1 răspunsuri

Păstrați o urmă a nodurilor vizitate și excludeți-le atunci când adăugați destinațiile posibile în pasul următor.

Am schimbat câteva margini și am adăugat unul, pentru a vă asigura că funcționează și atunci când marginile sunt listate în ordinea "greșită" pentru a merge de la S la F.

edge('S','Y').    visualization:    S -- Y -- T
edge('F','Y').                    /\  /
edge('S','F').                   /  \/
edge('Y','T').                   A --- F
edge('A','S').
edge('F','A').

În prolog acest lucru ar trebui să arate cam așa:

pathBetween(A,A,_):- !, fail.
pathBetween(S,F,Visited) :- (edge(S,F) ; edge(F,S)),
    append(Visited,[S,F],L),
    write(L).
pathBetween(S,F,Visited) :-
    (   edge(S,A) ; edge(A,S)  ),
    not(member(A,Visited)),
    pathBetween(A,F,[S|Visited]).

Puteți folosi ; pentru a găsi manual toate soluțiile sau findall .

?- findall(Visited, pathBetween('S', 'F', []), _).
[S,F][S,Y,F][S,A,F]
true.
0
adăugat
apoi Cum poți extrage membrul din lista de soluții pentru a obține rezultatul așteptat, pe care l-am definit la întrebare? Oricum, vă mulțumesc pentru răspuns
adăugat autor user1428237, sursa
Nu este nevoie de BFS. DFS cu un set închis este suficient.
adăugat autor Fred Foo, sursa
OP-ul dorește să găsească toate căile, făcând astfel un DFS backtracking urmat de un fel de lungime ar putea fi o idee mai bună. BFS, esp. când se utilizează liste obișnuite pentru cozi, este incredibil de memorie intensivă pentru grafice mai mari.
adăugat autor Fred Foo, sursa
@Junuxx: (Sper că nu te mai obosesti încă de mine) BFS, atunci când i-ai cerut soluțiile toate , va încerca, de asemenea, toate capetele în grafic.
adăugat autor Fred Foo, sursa
@larsmann: Absolut adevărat, cred că implicit am presupus că PO ar dori să găsească mai întâi calea cea mai scurtă.
adăugat autor Junuxx, sursa
@larsmans: Și DFS ar putea dura mai mult decât este necesar dacă există multe căi lungi care nu conduc la obiectiv. Dar oricum, codul pe care l-am postat nu era de fapt BFS, în primul rând, așa că voi elimina referința. BFS/DFS este oricum puțin subiectul. Dar bine văzute, mulțumesc.
adăugat autor Junuxx, sursa
@ user1428237: Dacă folosiți predicatul printlists de la aici pe Soluții , ar trebui să obțineți exact acest lucru.
adăugat autor Junuxx, sursa
@larsmans: Da, dar numai după ce am găsit toate căile bune. Ai putea termina-o la un moment dat. În cel mai rău caz, DFS nu a găsit un singur răspuns în momentul în care BFS le-a găsit pe toate. Dar într-adevăr depinde de grafic. Nu mă deranjează deloc, dar cred că ar trebui să oprim poluarea întrebării;)
adăugat autor Junuxx, sursa
@gcc (care a eliminat de atunci comentariul său): Ai avut dreptate că acest lucru funcționează numai pentru grafice direcționate, voi schimba răspunsul meu într-un moment!
adăugat autor Junuxx, sursa
Fixat, nu știu de ce gcc și-a eliminat comentariul, totuși, a fost o observație bună.
adăugat autor Junuxx, sursa