modificare algoritm dfs

Avand matricea binara drept exemplu:
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
In care "1" poate fi parcurs si "0" nu.
Pornind din (1,1),
Ma intereseaza sa explorez toate drumurile posibile pornind din acest punct. Pentru aceasta m-am gandit sa folosesc DFS.
Ce modificare as putea sa-i aduc algoritmului astfel incat dupa ce s-a explorat una dintre ramuri, sa nu exploreze cea de-a doua ramura fara sa se intoarca in punctul de intersectie?
Exemplu:
Vreau ca iesirea programului, pornind din (1,1) sa arate asa:
(1,1)
(1,2)
(1,3)
(2,3)
(3,3)
(2,3)
(1,3) //acesta nu este obligatoriu intrucat se poate permite deplasare pe diagonala
(1,4)
(1,5)
pentru ca in mod normal ar arata asa:
(1,1)
(1,2)
(1,3)
(2,3)
(3,3)
(1,4)
(1,5)
Deci vreau se intoarca pe drumul pe care a venit inainte sa exploreze alte ramuri.
Pentru implementarea DFS standard, am luat exemplul de aici: http://www.java2blog...ch-in-java.html (implementarea pe stiva<obligatoriu>)
Mentionez ca matricea poate contine si bucle.
Simt ca solutia nu e foarte complicata, insa nu-mi dau seama.
Imi trebuie doar o idee.
Idei?
LE: Nu am stiut exact unde sa postez, problema nu intra in categoria vreunui limbaj intrucat este un algoritm. Am ales C/C++ pentru ca aici e mai multa lume.

Aici nu este mai multă lume, ci mai puțină lume. Din totalitatea programatorilor, mai puțini știu C/C++.

Alea două noduri în plus pe care le-ai listat sunt nodurile parcurse la ieșirea din recursivitate.

La cum ai expus problema, pare potrivita o parcurgere a unui arbore.
Insa.. in exemplul tau nu apar cicluri deci.. nu inteleg cum ai vrea sa se comporte algoritmul in cazul ciclurilor (adica sa ai bucle de 1)


Aniway.. intai trebuie sa-l gandesti formal, inainte de a te apuca de optimiza pe-acolo, functie de specificul problemei. Din punctul de plecare poti construi arborele partial ceva de genul...
Imparti graful pe nivele  de vecinatate plecand de la punctul de interes.
Pastrezi doar cate o legatura catre nivelul anterior sa poti avea structura de arbore. Orice alta legatura in plus, formeaza un ciclu (independent de celelalte)
In cadrul fiecarui nivel, poti avea alt sub-arbore pentru care trebuie sa procedezi la fel. Insa.. fiecare muchie din acel sub-graf formeaza alt ciclu independent.

Prima problema e .. cum anume arata ordinea de vizitare in cazul ciclurilor. Ciclurile(buclele) sunt multe in cazul in care ai insule cu multi de 1.
Intai din pct de vedere formal, cum vrei sa faci.
Si presupun ca odata cu formularea precisa a problemei, vine si rezolvarea.
https://gyazo.com/c4...bd8d18713f5ca4f
In desenul meu (paint) ai cu negru muchiile arborelui partial
cu rosu muchiile care creeaza cicluri in cazul trecerii la alt nivel de vecinatare.
cu albastru ai muchiile care creeaza cicluri independente in cazul aceluiasi nivel de vecinatate.

Ideea e.. cum parcurgi acele cicluri.
Sa zicem ca fiecare muchie e de fapt un lant de "1", adica 2 sau mai multi de "1", nustiu exact cum vrei sa pui problema.

Gandeste-te cum vrei sa vizitezi insule mari de "1", cred ca-ti va furniza si raspunsul.

Edited by maccip, 25 July 2017 - 09:28.

Uite ca vin cu o completare, am gresit mai sus in sensul ca .. graful nu e planar (e o muchie in plus intre 2 si 3)

Dar pun alt desen, poate e mai precis..
 55554805018a91803417a8846e96c71a.png   21.51K   7 downloads

Cu verde am facut o posibila ordine de vizitare, inteleg ca ..cam toate muchiile se vor parcurge de 2 ori, dus-intors.

Problema apare la noduri de mai multe muchii, mai ales cand ai cicli.
Cum faci?
Ramane sa parcurgi tot de 2 ori, sau parcurgi un nod oridecateori apare?

Pentru ca.. dupa ce ai terminat sa te decizi, algoritmul trebuie sa fie consistent si cu zonele in care ai insule de multi "1" in matricea aia a ta.
Solutia nu este unica (mai ales cand ai simetrii in matrice, nu ai cum sa fortezi unicitatea decat... greu)

Si.. daca de ex parcurgi de mai multe ori "1" ala din noduri, exista posibilitatea reparcurgerii de mai multe ori a aceluiasi "1"

Algoritmul pentru insule trebuie sa fie acelasi ca si ala pentru grafuri.
Mai e o varianta de a parcurge de 2 ori aceiasi muchie doar cand este necesar, adica cand nu ai cicli, deoarece poti ajunge la nodul urmator si pe calea alternativa.
Deci.. trebuie formulata foarte bine si precis problema. Si cred ca vine si rezolvarea, ajutandu-te tot de DFS.

visitedMatrix = { NOT_VISITED }
visitedList = {}
currentNode = startNode = ...
visitedMatrix[startNode] = startNode
visitedList.append(startNode)
do {
if (existsUnvisitedNeighbourNode(currentNode)) {
	 unvisitedNode = firstUnvisitedNeighbourNode(currentNode)
	 visitedMatrix[unvisitedNode] = currentNode
	 currentNode = unvisitedNode
} else
	 currentNode = visitedMatrix[currentNode]
visitedList.append(currentNode)
} while (currentNode != startNode)

Un pseudocod pentru un posibil algoritm de rezolvare. Ideea de bază este că pentru fiecare nod, memorezi nodul "părinte", adică nodul care l-a vizitat pe nodul curent, iar atunci când nodul curent nu mai are noduri adiacente nevizitate, ne întoarcem la nodul părinte și vedem dacă acesta are noduri adiacente nevizitate. Contează destul de mult ordinea în care cauți noduri adiacente nevizitate, adică firstUnvisitedNeighnourNode(), pentru ordinea finală în visitedList. De asemenea algoritmul de mai sus se va întoarce la nodul de început, deci e posibil să aibă noduri în plus față de nevoile tale, dar astea pot fi eliminate ușor cu o mică modificare. Și ar mai fi ceva optimizări, dar asta mai târziu.

Va multumesc tuturor pentru ajutor si sugestii!
Le-am citit pe toate. Au fost de ajutor.
Intr-un final am decis ca cel mai bine sa caut path-ul inapoi, cu ajutorul BFS(pe care il folosesc pentru a gasi cel mai scurt drum inapoi).M-am folosit intr-o oarecare masura de ceea ce a sugerat tavitu.
Mi-am dat seama ca nu ar fi fost bine sa ma intorc pe exact aceeasi cale pe care am venit intrucat existau multe cazuri in care DFS explora anumite zone, apoi altele, apoi sarea. Iar reconstructia drumului intocmai de unde am venit ar fi presupus sa ma intorc in niste zone in care chiar nu mi-as fi dorit sa ma intorc.

Edited by crs12decoder, 04 August 2017 - 02:54.