cel mai lung drum

[•mips]

Problema mea este urmatoarea:Am un graf(cu cicluri), un punct de pornire si un punct de oprire.Trebuie sa gasesc cel mai lung drum intre cele 2 puncte fara se trec prin aceeasi muchie de 2 ori ,avand voie sa trec prin orice nod de cate ori vreau.Nu stiu dak are importanta dar fiecare muchie are costul 1.Ce algoritmi as putea folosi pt a rezolva cat mai optim problema?

[•DITzoneC]

Nu cred ca are rezolvare polinomiala. Altfel ai putea rezolva prin aceeasi metoda si problema comis voiajorului.

[•wefgef]

Ai voie sa treci prin destinatie de mai multe ori?

[•byndrsn]

Nu cred ca are rezolvare polinomiala. Altfel ai putea rezolva prin aceeasi metoda si problema comis voiajorului.

cum reduci hamilton path la problema aceasta? nu mi se pare evident pentru ca in problema aceasta ai voie sa vizitezi un nod de mai multe ori..
exista o varianta a acestei probleme care e NP-complete, si anume sa gasesti cel mai lung drum simplu (nu ai voie sa repetzi un nod) (aici reducerea e evidenta, cel mai lung drum simplu intr-un graf hamiltonian este un drum hamiltonian)
in schimb, sa gasesti un drum care viziteaza orice muchie cel mult o data (adica "walk") (care poate sa inceapa si sa se termine in orice nod) intr-un graf pare polinomial (ma gandeam la un algoritm de genul: fie s un nod al grafului si w_s un walk constuit astfel: pornesti din s si traversezi o muchie la intamplare cu conditia sa nu traversezi un bridge (bridge sau cut-edge e o muchie e a.i. G\e are mai multe componente conexe decat G) decat daca esti fortzat sa o faci (bineinteles, stergi muchia traversata); continui pana cand nu mai poti extinde walkul.. intuitiv, un walk maximal cred ca este w_s a carui lungime este maxima)

[•devilkind]

nu cred ca se poate reduce la ciclu hamiltonian dar daca sursa = destinatie atunci iti iesa ciclu eulerian.

[•alex_damian]

pai bagi muchia (0, s) si (d, 0) si faci ciclu eulerian

[•devilkind]

da dar totusi chiar si cu adaugarea acelor nu cred ca poti aplica algoritmul ptr determinarea ciclului eulerian ptr ca nu iti garanteaza nimeni ca in graful tau exista un astfel de ciclu.

[•Darth_Niculus]

  Eu tot nu inteleg... dc nu merge faza cu (0,s) (d,0) ? ... daca nu exista un astfel de ciclu inseamna ca nu exista nici solutie... right?

[•devilkind]

nu neaparat.
uite de exemplu pe graful
1 2
2 3
3 4
nodul sursa 1, nodul destinatie 3. Daca adaugi muchi 1 0, 0 3 atunci vei avea ciclul 1 2 3 0, insa acesta nu este ciclu eulerian deoarece nu ai vizitat muchia 3 4 (ciclu eulerian implica vizitarea tuturor muchiilor o singura data). Sper ca nu ma insel   

Adaugarea acelei muchii iti aduce problema la determinarea unui ciclu de lungime maxima care sa treaca prin 2 noduri fara a traversa de 2 ori aceeasi muchie si nu stiu daca exista o rezolvare polinomiala ptr asa ceva, posibil sa fie.

[•cos_min]

Pai daca ai sursa = 1 si destinatia = 3, nu ai ciclu eulerian, chiar daca nu adaugi cele 2 much .

[•Darth_Niculus]

  Ok, am inteles... dar ai putea sa modifici putin algoritmul sa nu fie necesar sa vizezi toate muchiile.... adica sa faci ceva de genu:
  pui faza (0,s) (d,0) dupaia cauti un ciclu care trece prin s. Dupaia tot incerci sa adaugi alte cicluri la ciclu asta si chiar daca la final nu le ai pe toate muchiile... tu o consideri o solutie valida, pt. ca oricum ai numarul maxim de muchii posibile (sper ca n-am gresit pe undeva).

[•domino]

Daca ai graf oarecare si inlocuiesti fiecare nod cu o muchie atunci un drum cat mai lung care nu trece printr-o muchie decat odata e echivalent cu un drum hamiltonian.

[•devilkind]

Daca ai graf oarecare si inlocuiesti fiecare nod cu o muchie atunci un drum cat mai lung care nu trece printr-o muchie decat odata e echivalent cu un drum hamiltonian.

pai atunci de ce ptr ciclu eulerian exista algoritm polinomial iar ptr ciclu hamiltonian nu?? adik la urma urmei ptr a determina un ciclu hamiltonian poti sa faci acea inlocuire si sa aplici algoritmu ptr ciclu eulerian si iata cum ai rezolvat polinomial problema comis-voiajorului. Sau nu am inteles eu bine??

[•mips]

Daca ai graf oarecare si inlocuiesti fiecare nod cu o muchie atunci un drum cat mai lung care nu trece printr-o muchie decat odata e echivalent cu un drum hamiltonian.

Da nu-i sigur ca poate exista un ciclu hamiltonian in graf chiar daca adaugam un nod prin care legam sursa de destinatie.Adik poate de la sursa la destinatie putem trece numai prin cateva noduri nu neaparat prin toate(daca avem noduri terminale de exemplu).
Nu?

[•devilkind]

mircea pasoi se referea la drum hamiltonia nu la ciclu. ciclul hamiltonian era doar o paranteza la ce a zis adi diaconu referitor la problema comis-voiajorului.

[•domino]

Daca ai graf oarecare si inlocuiesti fiecare nod cu o muchie atunci un drum cat mai lung care nu trece printr-o muchie decat odata e echivalent cu un drum hamiltonian.

pai atunci de ce ptr ciclu eulerian exista algoritm polinomial iar ptr ciclu hamiltonian nu?? adik la urma urmei ptr a determina un ciclu hamiltonian poti sa faci acea inlocuire si sa aplici algoritmu ptr ciclu eulerian si iata cum ai rezolvat polinomial problema comis-voiajorului. Sau nu am inteles eu bine??

Nu ai inteles tu bine. Daca faci inlocuirea si faci ciclu eulerian vei obtine un ciclu care trece prin fiecare muchie FIX odata (daca e posibil). Nu exista nici o echivalenta intr-un ciclu eulerian astfel obtinut si un ciclu hamiltonian in graful initial... Un ciclu hamiltonian trece doar prin N muchii (sau 2N daca faci transformarea) dar nu prin toate.. sper ca e clar ca nu e deloc acelasi lucru.

[•domino]

Daca ai graf oarecare si inlocuiesti fiecare nod cu o muchie atunci un drum cat mai lung care nu trece printr-o muchie decat odata e echivalent cu un drum hamiltonian.

Da nu-i sigur ca poate exista un ciclu hamiltonian in graf chiar daca adaugam un nod prin care legam sursa de destinatie.Adik poate de la sursa la destinatie putem trece numai prin cateva noduri nu neaparat prin toate(daca avem noduri terminale de exemplu).
Nu?

Daca as putea rezolva problema initiala, as putea rezolva si problema sa gasesc cel mai lung drum intre doua noduri dintr-un graf care nu trece de doua ori printr-un nod (inlocuire triviala nod cu muchie) .. daca pot rezolva asta, pot rezolva si problema de lant/ciclu hamiltonian , pentru ca intr-un graf care are lant hamiltonian ala e cel mai lung drum care nu trece de doua ori printr-un nod.. deci e NP... 

[•DITzoneC]

Da... cam asta am zis si eu in primul post