Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- laboratoare:laborator-10 [2017/04/29 18:29]
mihai.iacov [2.3 Probleme tip rezolvate cu acest algoritm]
+++ laboratoare:laborator-10 [2017/04/29 19:28]
mihai.iacov [2.3 Probleme tip rezolvate cu acest algoritm]
@@ Linia 57: / Linia 57: @@
    *Nu intră în totalitate în rucsac și atunci se determină ce procent din obiectul respectiv va intra în rucsac; în acest caz se va cumula la câștigul total procentul de profit asociat părții din obiectul încărcat în rucsac, iar greutatea rămasă va fi zero.\\
-===2.3.4 Problema comisului voiajor===
+===2.3.4 Problema comisului voiajor (TSP)===
-TODO !!!!!!
+Un comis-voiajor stă într-un oraş (X1) şi vrea să viziteze toate cele N oraşe dintr-o regiune (X1, X2, ..., XN), plecând dimineaţa de acasă (X1) şi întorcandu-se (tot în X1) la finalul zilei.
+În mod ideal, el îşi doreşte să viziteze fiecare oraş exact o singură dată (excepţie făcând numai oraşul X1 unde se întoarce seara), iar drumul găsit să fie cât mai scurt.
+Problema poate fi modelată cu grafuri (oraş = nod, drum între 2 oraşe = muchie) şi cerinţa devine găsirea unui **Ciclu/Circuit Hamiltonian minim** (un ciclu care conţine o singură dată fiecare nod, cu excepţia nodului de plecare care coincide doar cu nodul final, şi care este de cost minim).
+<note warning>
+Soluţia de **cost minim** pentru TSP **nu poate fi garantată** cu un algoritm de tip Greedy, dar un astfel de algoritm poate fi folosit pentru a găsi în timp util un drum.
+</note>
+Varianta **Greedy** (pură): -parcurgem în adâncime (DFS) graful din nodul de plecare (X1), continuând mereu pe cea mai ieftină muchie. La prima fundătură (primul nod din care nu mai avem vecini nevizitaţi), algoritmul se opreşte:
+  * dacă algoritmul s-a blocat după ce a vizitat N noduri şi ultimul nod găsit (nodul curent) este vecin cu nodul de plecare (X1), atunci: mesaj de reuşită + soluţia găsită.
+  * altfel: mesaj de nereuşită (+ eventual soluţia parţială).
+Varianta **Greedy + revenire**: -la fel ca varianta Greedy (pură), dar permitem revenirea în cazul unui blocaj, respectând parcurgerea DFS (eliminăm nodul curent din soluţie, ne întoarcem la nodul găsit imediat înainte de nodul curent şi, din acel nod, alegem următoarea variantă).
+<note warning>
+Această variantă **nu** mai respectă principiul de bază al tehnicii Greedy, va avea nevoie de mai mult timp, dar va oferi un răspuns mai bun.
+</note>
 =====3 Paradigma Divide et impera =====

Structuri de Date și Algoritmi (seria 1AB)

Unelte utilizator

Unelte site

Diferențe

Unelte pagină