Graf

[•Tudorutzu]

Spuneti-mi si mie va rog cum calculez drumul de cost minim de la un nod al unui graf la alt nod, drum care sa treaca printr-un numar fixat de noduri

[•fireatmyself]

Poti rezolva problema prin programare dinamica:
D[ i ][ j ] = distanta minima de la nodul de start panala nodul i trecand prin exact j noduri. Initial D[ sursa ][1] = 0, iar pentru o stare (i,j) deja calculata vei trece intr-o stare (i',j+1) unde i' este un vecin al lui i.

[•wefgef]

Nodurile presupun ca au voie sa se repete

[•amadaeus]

Daca nu au voie sa se repete, e NP-completa.

[•fireatmyself]

Nodurile presupun ca au voie sa se repete

si eu am presupus acelasi lucru 

[•Tudorutzu]

nu au voie sa se repete   

[•amadaeus]

Atunci nu se poate rezolva in timp polinomial. Daca ai gasi un astfel de algoritm, ai rezolva si problema drumului hamiltonian (cauti drumul dintre doua noduri care sa treaca prin toate celelalte |V|-2 noduri).
Cred ca poti gasi o rezolvare intr-o dinamica pe stari in O(2^N * N^2), similara cu gasirea drumului hamiltonian de cost minim.

[•wefgef]

In cazul in care nu se poate sa repeti nodurile ai 2 posibilitati:

1. Faci un backtracking optimizat
2. Folosesti rezolvarea de care spunea amadeus mai sus cu dinamica pe configuratii. Ar trebui sa te uiti peste rezolvarea de la problema ADN pentru mai multe detalii

[•amadaeus]

...sau niste random-uri inteligente, in sistem Ciucu 

[•CezarMocan]

Ia zi si mie cum ar merge cu randomuri problema asta... sunt chiar curios

[•amadaeus]

Asta numai el iti poate spune

[•Cosmin]

Cezare poti baga si pe aici k-opturi cum ti-am mai zis la ciclu hamiltonean.

[•devilkind]

ce sunt k-opturile??

[•Cosmin]

http://en.wikipedia.org/wiki/Traveling_salesman_problem

cauta aici k-opt

Am avut la ginfo prin 2001 sau 2002 nu mai stiu sa determinam lantul hamiltonean de cost minim intr-un graf unde n era vreo 200. Prietenul meu Adrian Carcu a facut cel mai bine pe problema si a folosit o combinatie de 2-opt si 3-opt.

Am folosit in o gramada de probleme de euristici de la Bursele Agora metode de imbunatatire a solutiei de tipul asta.

[•Marius]

Sa punem o problema pe infoarena care sa determine lantul hamiltonian de cost minim pentru n mare (200 cum zice Cosmin) si sa se evalueze astfel incat daca obtii un cost mai bun decat al comisiei sa primesti mai mult de 10 puncte pe test? Sa fie o problema care obtine mai mult de 100 de puncte.

[•wefgef]

Nu se poate sa obtii mai mult de 100 de puncte la o problema pe infoarena .

[•Marius]

Eu am avut si un milion de puncte si nu se poate 101 ...

[•amadaeus]

Ar merge o intreaga clasa de astfel de probleme, pentru care sa nu existe solutie polinomiala sau solutie exponentiala care s-ar incadra in timp, iar punctarea sa se faca in functie de cea mai buna solutie valida pana la momentul respectiv (care ar lua 100p), restul surselor primind puncte in funtie de o anumita distributie (de exemplu Gaussiana).

Cred ca este totusi destula munca pentru implementarea unei astfel de functionalitati; poate in infoarena 3.0 vom avea si "arhiva de bulaneli", plasata cu o eticheta mai formala sub arhiva de probleme si arhiva educationala