|
Titlul: curiozitate Scris de: adrian din 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? Titlul: Raspuns: curiozitate Scris de: Cosmin Negruseri din 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 :).
Titlul: Raspuns: curiozitate Scris de: adrian din 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? Titlul: Raspuns: curiozitate Scris de: Paul-Dan Baltescu din Septembrie 10, 2006, 09:55:49 Aici, unde altundeva: :D
http://infoarena.devnet.ro/forum/index.php/topic,608.0.html Titlul: Raspuns: curiozitate Scris de: Cosmin Negruseri din 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.
|