Provocarea saptamanii – TSP

Andrei doreste sa plece din Bucuresti, sa viziteze fiecare resedinta de judet din tara (o singura data), si sa se intoarca inapoi in Bucuresti.

Care este distanta (km) minima necesara (fara zecimale)? In ce ordine ar urma sa viziteze orasele?

Distanta dintre doua orase poate fi considerata:

• In linie dreapta functie de coordonatele geografice ale primariilor (se ignora diferenta de inaltime)
  
• Pe sosele existente

Edited by dani.user, 18 April 2018 - 21:59.

O să aibă problemă cu IF.

p.s.

jobist, on 18 aprilie 2018 - 22:16, said:

Raspunde in linii de cod daca se poate..

asta e cu grafuri, noduri, arbori  de minim(drum minim/cost minim, bla bla) , in  cazul asta e vorba de arborele de drum minim cel mai probabil sau drum optim.
Care  e problema de fapt ca nu inteleg ?

Un ajutor vizual, uniti punctele
 romania_judete.gif   39.72K   26 downloads

Pai sa le uneasca cine are problema asta.

In plus nu ai figurat , graful descris de totalitatea soselor din Romania, inclusiv si subgrafurile generate de buclele de descarcare traficului si nu sunt figurate nici nodurile intermediare
de intarziere a traficului  ale grafului general. De ce ar conta asa ceva intr-o problema de minim de distanta ?

Pai eu cred ca  scopul final ca sa aflu drumul minim intr-un graf in acest caz este ca sa ma ajute sa realizez  un timp  minim de parcurgere si asta ma ajuta ca sa realizez acel drum cu minimul de combustibil folosit ?  Ceea ce se traduce in economie substantiala de cheltuilei(bani) ?
Iar daca acest drum este facut de o flota de tiruri (astea consuma combustibil cum respiram noi aer) ale unui curier care livreaza marfa in toata tara, si ii faci un astfel de program, te-a facut peste noapte milionar in euro in domeniul software-ului de logistica.

Adica sa rezolvi un problema de drum minim in timp real. intr-un graf in condiitile in care o parte a grafului este fixa iar subparti ale acestuia sunt dinamice in functie de traficul care deja exista la ora executarii algoritmului .

Iar asta nu este provocarea saptamanii  ci este provocarea vrei sa fii cu adevarat miliionar de pe urma aplicarii teoriei grafurilor(dinamice si reconfigurabile in timp real) ?

Edited by WinstonMontana, 19 April 2018 - 05:13.

Provocarea saptaminii e problema comis-voiajorului? Asta e o problema supermegacomplicata

Mosotti, on 19 aprilie 2018 - 07:54, said:

Aia cu un tip are N amante in mai multe orase.Sa afle drumul minim de la o amanta la alta astfel incat tipul sa dea cat mai puti bani pe flori .
sau
O baba trebuie sa ajunga la groapa mosului ei. Tinand cont ca cimitirul are N alei sa se faca un program astfel incat baba sa navigheze printre
morminte pe drumul cel mai scurt posbil ca sa nu oboseasca.

Edited by WinstonMontana, 19 April 2018 - 08:15.

Mosotti, on 19 aprilie 2018 - 07:54, said:

E o problema unde e usor de inteles ce trebuie obtinut, e usor de codat de o solutie precisa ineficienta si, zic eu, destul de provocator de gasit o solutie (precisa sau aproximativa) mai eficienta.

In plus, algoritmul in sine e doar o parte a provocarii. Cealalta este gasirea datelor de intrare. Am ales sa le specific intr-un limbaj comun cum adesea se intampla in proiectele reale unde cerintele rareori sunt atat de precise ca cele din probleme

WinstonMontana, on 19 aprilie 2018 - 05:02, said:

Nu face asta mai orice soft de navigare ce primeste si date despre trafic?

Edited by dani.user, 20 April 2018 - 18:46.