ग्राफ सिद्धांत

Question

में छूट की स्थिति क्या है मैं ग्राफ सिद्धांत की मुख्य अवधारणाओं और इसके भीतर एल्गोरिदम को समझने की कोशिश कर रहा हूं। अधिकांश एल्गोरिदम में "आराम की स्थिति" होती है, मुझे इस बारे में अनिश्चितता है कि यह क्या है।

क्या कोई इसे कृपया मुझे समझा सकता है।

इसका एक उदाहरण डिजस्ट्रस एल्गोरिदम है, यहां छद्म कोड है।

1 function Dijkstra(Graph, source): 
2  for each vertex v in Graph:   // Initializations 
3   dist[v] := infinity    // Unknown distance function from source to v 
4   previous[v] := undefined   // Previous node in optimal path from source 
5  dist[source] := 0      // Distance from source to source 
6  Q := the set of all nodes in Graph 
    // All nodes in the graph are unoptimized - thus are in Q 
7  while Q is not empty:     // The main loop 
8   u := vertex in Q with smallest dist[] 
9   if dist[u] = infinity: 
10    break       // all remaining vertices are inaccessible from source 
11   remove u from Q 
12   for each neighbor v of u:   // where v has not yet been removed from Q. 
13    alt := dist[u] + dist_between(u, v) 
14    if alt < dist[v]:    // Relax (u,v,a) 
15     dist[v] := alt 
16     previous[v] := u 
17  return dist[] 

धन्यवाद

Answer 1

विश्राम कदम:

• आप दो नोड्स, u और v
• प्रत्येक नोड के लिए है, तो आप स्रोत नोड (स्रोत को छोड़कर सभी नोड्स के लिए से एक जांच दूरी है, यह शुरू होता है सकारात्मक अनंतता पर और यह केवल न्यूनतम तक पहुंचने के लिए घट जाती है)।

छूट कदम मूल रूप से इस पूछ रहा है:

• मैं पहले से ही पता है कि मैं दूरी dist[v] के कुछ पथ के साथ v पहुँच सकते हैं। क्या मैं इसके बजाय पर u के माध्यम से इस पर सुधार कर सकता हूं? (जहां उत्तरार्द्ध की दूरी dist[u] + weight(u, v) होगा)

रेखांकन:

s ~~~~~~~> v 
\  ^
    \  | 
    \~~~~~> u 

आप कुछ पथ s~>v दूरी dist[v] है जो पता है, और आप कुछ पथ s~>u दूरी dist[u] है जो पता है। यदि dist[u] + weight(u, v) < dist[v], तो पथ s~>u->vs~>v से छोटा है, तो आप बेहतर इसका उपयोग करेंगे!

(मैं a~>b लिखने a से b को किसी भी लंबाई के रास्ते मतलब करने के लिए है, जबकि a->b मैं a से b के लिए एक सीधा एकल बढ़त मतलब)।

आप इस व्याख्यान को भी देखना चाहेंगे: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed17.htm

Answer 2

अंग्रेज़ी शब्द के अर्थ में से एक "छूट" कुछ कम हो रही है। क्योंकि 14,15 और 16 लाइनों पर आप अनिवार्य रूप से जांच कर रहे हैं कि क्या आप वर्तमान में गणना की गई दूरी को कम (अनुकूलित) कर सकते हैं, मुझे लगता है कि यही कारण है कि इसे "विश्राम की स्थिति" कहा जाता है।