De ce îi spunem „Relaxarea” unei margini? (Programare, Dijkstra, Bellman Ford)

Eric G a intrebat.

În algoritmul celei mai scurte căi al lui Dijkstra și în alte algoritmi, examinarea unei muchii pentru a vedea dacă oferă o cale mai bună către un nod se numește relaxare a muchiei. De ce se numește „relaxare”?

2 răspunsuri
Charlie Martin

În general, din punct de vedere matematic, relaxare este efectuarea unei modificări care reduce constrângerile. Atunci când algoritmul Dijkstra examinează o muchie, elimină o muchie din grup, reducând astfel numărul de constrângeri.

Nu este o terminologie extrem de utilă, dar gândește-te cât de tare vei suna când o spui.

Comentarii

  • Ați putea clarifica modul în care marginile din bazin pot fi considerate constrângeri? –  > Por Eric G.
  • Gândiți-vă la un vertex cu multe muchii care intră în el. Când începi, știi că soluția trebuie să includă greutatea de la prima muchie, a doua muchie și așa mai departe. De fapt, pentru marginile a,b,c,d și e, începeți să spuneți „cea mai scurtă cale trebuie să includă a,b,c,d,e”. Apoi îl eliminați pe e, iar acum știți că trebuie să includă doar „a,b,c,d”. Fiecare pas este un relaxare pentru că la fiecare pas eliminați o condiție impusă de soluția curentă. –  > Por Charlie Martin.
  • Cred că nu este coming into it ci leaving it? –  > Por Jackson Tale.
  • Sunt duble, Jackson. Ar putea fi chiar un graf neorientat. Ideea este că relaxarea înseamnă întotdeauna eliminarea unei constrângeri. –  > Por Charlie Martin.
  • În cazul unor algoritmi pentru calea cea mai scurtă, relaxarea fie nu elimină muchia din grup, fie o elimină în timp ce adaugă simultan alte muchii. Așadar, nu sunt convins de explicația dumneavoastră. Am auzit că relaxare este un termen din domeniul cercetării operaționale și am văzut relaxare lagrangiană menționată în context, dar nu văd de ce relaxarea marginilor în algoritmul lui Dijkstra ar fi relaxarea Lagrangiană. –  > Por Alexey.
Eric Grinstein

Nu cred că întrebarea are legătură cu conceptul matematic despre care se vorbește în răspunsul acceptat în prezent. Eu îmi bazez răspunsul pe ediția a doua a cărții lui Cormen (CLRS), mai exact pe capitolul 24, într-o secțiune despre relaxare.

Context: Căutați cea mai scurtă cale între un nod s și toate celelalte noduri. Imaginați-vă că aveți două noduri u și v. Aveți deja o cale intermediară pentru acestea.

relax(u,v) este un funcție care trebuie citită ca „relaxează v folosind u„. Eu prefer să înțeleg funcția ca fiind „scurtează vla s folosind u„. Vă întrebați dacă ar trebui să renunțați la calea actuală s-v în favoarea transformării ei în s-u-v. Tot ce trebuie să faceți pentru a vedea dacă distanța de s-u plus costul suplimentar al săgeții u-v sunt mai bune decât distanța s-v. Imaginea ilustrează funcția

O imagine din explicația CLRS privind Relaxarea

Comentarii