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:23]
mihai.iacov [2.1 Prezentare generală]
+++ laboratoare:laborator-10 [2017/04/29 19:28]
mihai.iacov [2.3 Probleme tip rezolvate cu acest algoritm]
@@ Linia 45: / Linia 45: @@
 *Explicație: punctul 2 se afla în primele 3 intervale, iar punctul 14 în ultimele 2
-Soluție:Se observă că dacă x este un punct din M care nu este capăt dreapta al nici unui interval, o translație a lui x la dreapta care îl duce în capătul dreapta cel mai apropiat nu va schimba intervalele care conțin punctul. Prin urmare,există o mulțime de cardinal minim M pentru care toate punctele x sunt capete dreapta.
+Soluție:Se observă că dacă x este un punct din M care nu este capăt dreapta al nici unui interval, o translație a lui x la dreapta care îl duce în capătul dreapta cel mai apropiat nu va schimba intervalele care conțin punctul. Prin urmare,există o mulțime (M) de cardinal minim pentru care toate punctele x sunt capete dreapta.
 \\
 ===2.3.3 Problema rucsacului===
@@ 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ă