Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: curiozitate  (Citit de 5657 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
bigsarpe
Strain


Karma: -5
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« : Septembrie 10, 2006, 02:26:09 »

am un graf orientat ponderat (si cu cicluri in el) n noduri ,m muchii n>=1000 ,nu mic
daca vreau de la un nod sursa sa aflu distanta maxima pana la un nod destinatie si printr-un nod n-am voie sa trec decat cel mult o data ce algoritm exista?
Memorat
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #1 : Septembrie 10, 2006, 07:32:23 »

Cel mai lung  drum, sau cel mai lung drum minim? Pentru a gasi cel mai lung drum intr-un graf oarecare trebuie sa stii si drumul hamitonean de cost maxim in graful respectiv. Deci problema e  grea Smile.
Memorat
bigsarpe
Strain


Karma: -5
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #2 : Septembrie 10, 2006, 09:22:59 »

nu conteaza cate noduri are un drum,conteaza doar sa il aflu pe cel cu suma costurilor muchiilor maxima
problema e echivalenta(cred) cu:fac negative costurile muchiilor si apoi sa caut drumul de suma minima fara sa trec de mai multe ori printr-un nod....

apropo unde gasesc informatii despre algoritmul bellman-ford?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #3 : Septembrie 10, 2006, 09:55:49 »

Aici, unde altundeva:   Very Happy

http://infoarena.devnet.ro/forum/index.php/topic,608.0.html
Memorat

Am zis Mr. Green
Cosmin
Echipa infoarena
Nu mai tace
*****

Karma: 351
Deconectat Deconectat

Mesaje: 1.799



Vezi Profilul
« Răspunde #4 : Septembrie 10, 2006, 12:33:29 »

Pe un graf unde arcele au cost 1, drumul maxim e un drum hamiltonian, daca acel graf are lant hamiltonian. Deci algoritmul care il vrei tu daca ar exista, ar putea fi aplicat pentru a rezolva o problema NP completa.  Succes in gasirea lui, poate castigi si un milion de dolari pe langa.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines