Drum simplu de cost MAXIM

[•paliuca]

Salut , ce algoritm as putea folosi pentru a determina un drum simplu de cost maxim intr-un graf neorientat ?
Mentionez ca trebuie sa reconstitui si drumul daca asta influenteaza cu ceva..

[•wefgef]

E problema NP-completa, nu exista rezolvare polinomiala pentru ea .

Poti face dinamica pe stari sau back optimizat.

[•paliuca]

Mi-ai putea da un mic ajutor in legatura cu dinamica pe stari deoarece nu am mai auzit de asa ceva ?
Ar fi un fel de Roy Floyd doar ca nu ar merge daca exista cicluri ? Sau merge tot timpul ?

[•cos_min]

Hmm cred ca ai putea face ceva de genul:

A[i,j] - costul maxim de a ajunge in nodul i, avand configuratia j. Prin configuratie se intelege un numar care in baza 2 tine minte daca ai fost intr-un nod. Spre exemplu daca ai avea j=9 in baza 2 ai avea 1001, asta insemnand ca ai deja parcurse nodurile 1 si 4. Sper sa mearga , daca este ceva gresit corectati-ma.

[•paliuca]

Ce inseamna ca sunt parcurse nodurile 1 si 4 ? Ca drumul este 1 , 4 si i ?

[•cos_min]

Ce inseamna ca sunt parcurse nodurile 1 si 4 ? Ca drumul este 1 , 4 si i ?

In cazul asta ii ca si cum ai avea drumul 1-4-i. Dar, de exemplu daca ai avea mai multe noduri parcurse, spre exemplu 1,2,3,4 nu insemna ca drumul este 1-2-3-4-i, ci doar ca ai trecut prin nodurile 1,2,3,4 deja. Astfel te asiguri ca nu mai treci inca o data prin ele.

[•paliuca]

Hmmm , sunt curios daca merge asa... Si care ar fi recurenta pentru a actualiza un element din matrice ? In functie de ce actualizezi ?

[•cos_min]

Ai putea face un Bellman Ford cu coada pentru o implementare mai simpla.

[•paliuca]

Pana la urma e sau nu NP-completa ? Daca fac un Bellman-Ford pt fiecare nod mi se pare ca nu gaseste drum simplu tot timpul

[•Cosmin]

E np hard.

Poti sa te uiti la problema ADN si la solutia ei din articolele cu solutii, ca sa prinzi trucul.

Cosmine nu faci cu bellman ford ci umplii pur si simplu matricea aia cu dinamica. Nu vad cu ce te ajuta bellman ford.

Daca problema e mai particulara si graful accepta o sortare topologica atunci exista algoritmi eficienti, sau daca graful e un arbore.

[•paliuca]

Am citit articolul cu solutii , frumoasa abordare . In general am inteles, sper sa-mi iasa si implementarea.

Mersi mult.

[•cos_min]

@Cosmin

Defapt nu aplici un Bellman Ford cu coada in adevaratul sens al cuvantului, ci doar ti o coada de care te folosesti. Mie mi se pare mult mai usor sa umpli matricea asa.

[•paliuca]

Doar daca exista si costuri negative este NP-completa ?

[•devilkind]

Este NP si fara costuri negative. Gandeste-te ca dak as putea rezolva problema ta, atunci as putea sa rezolv problema si pentru un graf in  care costurile muchiilor sunt 1, ceea ce inseamna ca as putea gasi un ciclul hamiltonian, problema demonstrata ca fiind NP.

[•paliuca]

Multumesc.

Inca ceva , poate poti sa ma ajuti.

Nu-mi dai un exemplu pentru care pica Dijkstra aplicat pt fiecare nod ?

[•devilkind]

pai cum verifici cu djikstra sa nu vizitezi un nod de 2 ori?? cu djikstra o sa te plimbi pe cicluri de o infinitate de ori si costul o sa tot creasca.

[•paliuca]

Cu vectorul in care verifici daca ai trecut sau nu printr-un nod

[•byndrsn]

Nu-mi dai un exemplu pentru care pica Dijkstra aplicat pt fiecare nod ?

Nu imi dau seama exact la ce te referi. Vrei sa modifici algoritmul lui Dijkstra astfel incant sa aleaga la fiecare pas nodul cu distantza temporara maxima?

[•paliuca]

Un contraexemplu pentru care Dijkstra nu gaseste drum simplu de cost maxim daca iei pe rand fiecare nod ca sursa... nevermind...abandonez problema

[•byndrsn]

Dijkstra calculeaza drumurile minime. Daca folosesti Dijkstra pornind din fiecare nod, cel mai costisitor drum pe care il gasesti e distanza maxima dintre oricare 2 noduri. "Roata" (http://en.wikipedia.org/wiki/Wheel_graph wheel graph) cu 7 noduri este un contraexemplu: un ciclu de lungime 6 cu un nod in centru conectat cu toate nodurile de pe ciclu. Sa zicem ca fiecare muchie are cost 1. Distanta maxima intre oricare 2 varfuri este 2. Dar drumul de cost maxim are cost 6.