Clasele 11-12 lecția 12 - 3 dec 2014

From Algopedia
Revision as of 10:26, 2 December 2014 by Cata (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Grafuri, partea a treia

În această lecție introducem noțiunea de costuri pe muchii (numite și distanțe, greutăți etc.). Apoi discutăm despre proprietăți ale grafurilor cu costuri.

Aceste note de curs sunt incomplete (sunt doar o schiță a planului de lecție).

Arbori parțiali minimi (grafuri neorientate)

Definim funcția de cost, c(u, v).

Un arbore parțial (sau arbore de acoperire, engl. spanning tree) este o mulțime de muchii T care este aciclică și conectează toate nodurile. Dorim să găsim arborele parțial minim (abreviat APM), adică arborele parțial care minimizează suma costurilor pe muchii.

Exemple din viața reală.

Există algoritmi greedy, ușori, care merg pe următorul schelet:

 inițializează A = { }
 de N - 1 ori
   găsește o muchie (u, v) astfel încât să existe un APM care să includă mulțimea A ∪ {(u, v)}
   A = A ∪ {(u, v)}
 returnează A

Muchia {(u, v)} se numește muchie acceptabilă pentru A (engl. safe edge). Demonstrația de corectitudine se face prin inducție. Desigur, întrebarea este cum găsim, la fiecare iterație, o muchie acceptabilă.

Algoritm generic

Definim:

  • tăieturi în grafuri
  • muchii care traversează o tăietură
  • tăieturi care respectă o mulțime de muchii

Teoremă: Fie G = (V, E) un graf neorientat cu costuri. Fie A o submulțime de muchii care este inclusă într-un APM. Fie (S, V - S) orice tăietură a lui G care respectă mulțimea A. Fie (u, v) o muchie de cost minim care traversează tăietura. Atunci (u, v) este acceptabilă pentru A.

Demonstrație: Fie T un APM care include mulțimea A. Trebuie să arătăm că există un arbore T′ care include mulțimea A ∪ {(u, v)}. Dacă (u, v)T, atunci T′ = T. Altfel arătăm cum îl construim pe T′ din T. Demonstrăm că T′ este (a) arbore parțial; (b) de cost minim; și (c) care include mulțimea A ∪ {(u, v)}.

Această metodă este generală. În practică, algoritmii lui Kruskal și Prim folosesc o tăietură anume. Ei aleg tăietura egală cu una dintre componentele conexe găsite până la acel moment și aleg o muchie care unește două componente conexe.

Algoritmul lui Kruskal

Principiu: Alege, la fiecare iterație, cea mai mică muchie care nu închide un ciclu.

Implementare: cu structuri de mulțimi disjuncte.

Complexitate: , datorită sortării muchiilor.

Algoritmul lui Kruskal este un exemplu de problemă de conexitate incrementală.

Algoritmul lui Prim

Principiu: Pornește cu un arbore format dintr-un singur nod și alege, la fiecare iterație, cea mai mică muchie care unește un nod din arborele curent cu un nod din afara lui.

Implementare: cu o coadă de priorități (heap). Fiecare nod care încă nu a fost inclus în arbore își reține distanța minimă până la oricare nod din arbore.

Complexitate: cu un heap binar; poate fi redusă la cu heapuri Fibonacci.

Algoritmul lui Prim seamănă foarte bine cu algoritmul lui Dijkstra pentru distanțe minime, pe care îl discutăm în continuare.

Exerciții

  • (Cormen 23.1-8) Fie T și T′ doi APM pentru un graf G = (V, E). Fie L și L′ listele ordonate cu costurile muchiilor din T și respectiv T′. Să se arate că L = L′.
  • Cum actualizăm APM când la graf se adaugă o muchie? Vezi problema Zăpada.
  • Cum actualizăm APM când la graf se adaugă un nod și niște muchii din acel nod? Vezi problema Cotoroanța.

Distanțe minime de la o sursă (grafuri orientate)

Definiția problemei. Remarcăm că nu cunoaștem algoritmi eficienți care să calculeze distanța minimă doar între două puncte (mai rapid decât distanța de la o sursă la toate celelalte noduri).

Discuție despre substructura optimă a drumurilor celor mai scurte. Din optimalitatea substructurii rezultă că putem stoca drumurile minime în memorie, folosind un vector de predecesori (ca la parcurgerea în lățime).

Muchii / cicluri de cost negativ. Algoritmul lui Dijkstra presupune că toate muchiile sunt ne-negative. Algoritmul Bellman-Ford găsește și raportează cicluri de cost negativ accesibile din sursă, caz în care problema devine nedefinită.

Definim conceptul de relaxare a unei muchii.

Enumerăm câteva proprietăți ale relaxării, dintre care proprietatea (4) ne dă o idee concretă de algoritm:

  1. pentru orice muchie
  2. Pentru orice algoritm care calculează vectorul prin relaxări, .
  3. Pentru orice muchie , dacă există un drum minim de la s la v care trece prin u și dacă înainte de relaxare, atunci după relaxare.
  4. Pentru orice cale , după o succesiune oarecare de relaxări care include muchiile de pe cale în ordine, pentru fiecare nod de pe cale.

Algoritmul Bellman-Ford

Principiu: De n-1 ori, relaxează toate muchiile grafului.

Complexitate:

La finalul algoritmului, dacă există vreo muchie pentru care , atunci graful conține un ciclu negativ accesibil din sursă.

Demonstrație de corectitudine a distanțelor.

Demonstrație de detecție a ciclurilor negative (prin reducere la absurd: sumă telescopică a costurilor muchiilor de pe ciclu).

Reducerea buclei principale la D iterații, unde D este lungimea maximă (în număr de muchii) a unui drum minim.

Caz particular: DAG.

Algoritmul lui Dijkstra

Principiu: Pornește cu nodul s ca singur nod explorat. Pe rând, adaugă cel mai apropiat nod la mulțimea de noduri explorate.

Complexitate: Ca și algoritmul lui Prim, algoritmul lui Dijkstra rulează în și poate fi redus la dacă folosim heapuri Fibonacci în loc de heapuri binare.

Demonstrație: Prin inducție după numărul de noduri explorate. Trebuie doar să arătăm că, la momentul marcării lui u ca explorat, .

Distanțe minime între oricare două noduri (grafuri orientate)

În limita timpului, algoritmul Floyd-Warshall.

Temă