العثور على المسار مع الحد الأدنى من الوزن

Question

أحاول إنشاء خوارزمية للعثور على مسار عبر رسم بياني موجه.إنه ليس مسارًا تقليديًا ولا يمكنني العثور على أي إشارات إلى أي شيء مثل هذا يتم تنفيذه بالفعل.

أريد العثور على المسار الذي يحتوي على الحد الأدنى للوزن.

أي.إذا كان هناك مسارين بأوزان 10->1->10 و 2->2->2 فإن المسار الثاني يعتبر أفضل من الأول لأن الحد الأدنى للوزن (2) أكبر من الحد الأدنى لوزن الأول (1) ).

إذا كان بإمكان أي شخص إيجاد طريقة للقيام بذلك، أو توجيهي في اتجاه بعض المواد المرجعية، فسيكون ذلك مفيدًا للغاية :)

يحرر::يبدو أنني نسيت أن أذكر أنني أحاول الانتقال من قمة محددة إلى قمة محددة أخرى.نقطة مهمة جداً هناك :/

تحرير 2::كما أشار أحد الأشخاص أدناه، يجب أن أسلط الضوء على أن أوزان الحواف ليست سلبية.

Answer 1

استخدم إما متزمت أو <وأ href = "HTTP: //en.wikipedia. غزاله / ويكي / كروسكال٪ 27s_algorithm "يختلط =" نوفولو noreferrer "> كروسكال في خوارزمية . فقط تعديلها بحيث يتوقف عندما يكتشفون أن القمم تسأل عن ترتبط.

وتحرير: عليك أن تسأل لأقصى قدر من الحد الأدنى، ولكن المثال الخاص بك تبدو وكأنك تريد الحد الأدنى الحد الأقصى. في حالة أقصى الحد الأدنى سوف خوارزمية كروسكال لن تفلح.

وتحرير: المثال على ما يرام، خطأي. خوارزمية متزمت إلا سيعمل ذلك الحين.

Answer 2

أنا أقوم بالنسخ هذا الإجابة والإضافة أيضًا إضافة إثبات صحة الخوارزمية:

سأستخدم بعض المتغيرات من ديكسترا.لقد أخذت الكود الزائف أدناه مباشرة من ويكيبيديا وقمت بتغيير 5 أشياء صغيرة فقط:

1. تمت إعادة تسميته dist ل width (من السطر 3 فصاعدًا)
2. تهيئة كل منهما width ل -infinity (السطر 3)
3. تهيئة عرض المصدر ل infinity (السطر 8)
4. اضبط معيار النهاية على -infinity (السطر 14)
5. تم تعديل وظيفة التحديث والتوقيع (السطر 20 + 21)

1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                 // Initializations
3          width[v] := -infinity  ;                                // Unknown width function from 
4                                                                  // source to v
5          previous[v] := undefined ;                              // Previous node in optimal path
6      end for                                                     // from source
7      
8      width[source] := infinity ;                                 // Width from source to source
9      Q := the set of all nodes in Graph ;                        // All nodes in the graph are
10                                                                 // unoptimized – thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with largest width in width[] ;       // Source node in first case
13          remove u from Q ;
14          if width[u] = -infinity:
15              break ;                                            // all remaining vertices are
16          end if                                                 // inaccessible from source
17          
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                 // removed from Q.
20              alt := max(width[v], min(width[u], width_between(u, v))) ;
21              if alt > width[v]:                                 // Relax (u,v,a)
22                  width[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25              end if
26          end for
27      end while
28      return width;
29  endfunction

بعض (التلويح باليد) شرح لماذا يعمل هذا:عليك أن تبدأ بالمصدر.ومن هناك، لديك قدرة لا حصر لها على نفسك.الآن عليك التحقق من جميع جيران المصدر.افترض أن الحواف ليس لها نفس السعة (في المثال الخاص بك، على سبيل المثال (s, a) = 300).ثم، ليس هناك طريقة أفضل للوصول b ثم عبر (s, b), ، حتى تعرف أفضل سعة للحالة b.تستمر في الذهاب إلى أفضل الجيران لمجموعة القمم المعروفة، حتى تصل إلى جميع القمم.

إثبات صحة الخوارزمية:

في أي نقطة في الخوارزمية، سيكون هناك مجموعتان من القمم A و B.ستكون القمم الموجودة في A هي القمم التي تم العثور على الحد الأدنى الصحيح لمسار السعة القصوى لها.والمجموعة B بها رؤوس لم نجد الإجابة عليها.

الفرضية الاستقرائية:في أي خطوة، جميع القمم في المجموعة A لها القيم الصحيحة للحد الأدنى لمسار السعة القصوى إليها.أي أن جميع التكرارات السابقة صحيحة.

صحة الحالة الأساسية:عندما تكون المجموعة A لها الرأس S فقط.إذن قيمة S هي اللانهاية، وهذا صحيح.

في التكرار الحالي، قمنا بتعيين

val[W] = max(val[W], min(val[V], width_between(V-W)))

الخطوة الاستقرائية:لنفترض أن W هو الرأس في المجموعة B ذات القيمة الأكبر [W].ويتم حذف W من قائمة الانتظار وتم تعيين W كقيمة الإجابة [W].

الآن، نحن بحاجة إلى إظهار أن كل مسار S-W آخر له عرض <= val[W].سيكون هذا صحيحًا دائمًا لأن جميع الطرق الأخرى للوصول إلى W سوف تمر عبر قمة أخرى (نسميها X) في المجموعة B.

وبالنسبة لجميع القمم الأخرى X في المجموعة B، val[X] <= val[W]

وبالتالي فإن أي مسار آخر إلى W سيكون مقيدًا بالقيمة val[X]، والتي لن تكون أبدًا أكبر من val[W].

وبالتالي فإن التقدير الحالي لـ val[W] هو الأمثل ومن ثم تحسب الخوارزمية القيم الصحيحة لجميع القمم.

Answer 3

ويمكنك أيضا استخدام "البحث الثنائي على الاجابة" النموذج. وهذا هو، القيام بعملية بحث ثنائي على الأوزان، واختبار لكل وزن w ما إذا كان يمكنك العثور على المسار في الرسم البياني باستخدام فقط حواف الوزن أكبر من w.

ووأكبر w التي يمكنك (وجدت من خلال البحث الثنائي) يعطي الجواب. لاحظ أن تحتاج فقط للتحقق ما إذا كان يوجد مسار، لذلك مجرد O (| E |)، اتساع الأول / متعمقة أول البحث، وليس أقصر طريق. لذلك فمن O(|E|*log(max W)) في كل شيء، مماثلة لO(|E|log |V|) على ديكسترا / كروسكال / زم ل(وأنا لا يمكن أن نرى على الفور ما يثبت تلك، أيضا).

Answer 4

يمكن حل هذه المشكلة باستخدام خوارزمية نمط BFS، ولكنك تحتاج إلى نوعين مختلفين:

• بدلاً من وضع علامة على كل عقدة على أنها "تمت زيارتها"، يمكنك وضع علامة عليها بأقل وزن على طول المسار الذي سلكته للوصول إليها.

على سبيل المثال، إذا كان I وJ جارين، فإن قيمة I هي w1، ووزن الحافة بينهما هو w2، إذن J=min(w1, w2).

• إذا وصلت إلى عقدة محددة بقيمة w1، فقد تحتاج إلى وضع علامة عليها ومعالجتها مرة أخرى، في حالة تعيين قيمة جديدة w2 (وw2>w1).يعد هذا مطلوبًا للتأكد من حصولك على الحد الأقصى من الحد الأدنى.

على سبيل المثال، إذا كان I وJ جارين، فإن لدي قيمة w1، وJ لها قيمة w2، ووزن الحافة بينهما هو w3، ثم إذا min(w2, w3) > w1 يجب عليك ملاحظة J ومعالجة جميع جيرانها مرة أخرى.

Answer 5

وأنا لست متأكدا من أن زم ستعمل هنا. أغتنم هذه بالدليل:

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 4), (4, 2)}

weight function w:
  w((1,2)) = .1, 
  w((2,3)) = .3
  w((1,4)) = .2
  w((4,2)) = .25

إذا قمت بتطبيق متزمت للعثور على مسار maxmin 1-3، بدءا من 1 وتحديد المسار 1 --> 2 --> 3، في حين أن يتحقق المسافة maxmin عن المسار الذي يذهب إلى 4.

Answer 6

وطيب، والإجابة على سؤالي بك هنا فقط لمحاولة الحصول على بعض الشيء من ردود الفعل كان لي على حل مؤقت عملت بها قبل نشرها هنا:

وكل عقدة يخزن "جزء المسار"، وهذا هو المسار بالكامل لنفسها حتى الآن.

و0) وضع رأس الحالية إلى بدء قمة
1) توليد جميع أجزاء المسار من هذا الرأس وإضافتها إلى قائمة الانتظار الأولوية ل
2) خذ جزء من رأس قبالة قائمة الانتظار ذات الأولوية، ووضع الرأس الحالية للقمة تنتهي من هذا الطريق
3) إذا كان رأس الحالية هي قمة الهدف، ثم العودة مسار
4) غوتو 1

وأنا لست متأكد من أن هذا سوف تجد أفضل مسار الرغم من ذلك، أعتقد أن حالة الخروج في الخطوة الثالثة هي طموحة بعض الشيء. لا أستطيع التفكير في أفضل حالة خروج الرغم من ذلك، منذ هذه الخوارزمية لا القمم وثيقة (ويمكن الرجوع إليها في قمة الرأس في العديد من أجزاء الطريق كما يحب) لا يمكنك فقط الانتظار حتى يتم إغلاق كافة القمم (مثل لفي ديكسترا المثال)

Answer 7

ويمكنك الاستمرار في استخدام ديكسترا!

وبدلا من استخدام +، استخدم عامل دقيقة ().
وبالإضافة إلى ذلك، سوف تحتاج إلى توجيه كومة / priority_queue بحيث أكبر الأشياء هي على القمة.

وشيء من هذا القبيل يجب أن تعمل: (ربما لقد غاب عن بعض تفاصيل التنفيذ)

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
   current = pq.top()
   pq.pop()
   for all neighbors of current.node:
      if neighbor has not been visited
          pq.decrease_key(neighbor, min(current.weight, edge.weight))

ومن يضمن أنه كلما تحصل على عقدة كنت تتبع مسار الأمثل (منذ تجد جميع الاحتمالات في ترتيب تنازلي، وأنت لا يمكن أبدا أن تحسين المسار الخاص بك عن طريق إضافة ميزة)

ووحدود الوقت هي نفس ديكسترا - O (مدونة فيديو (E))

وتحرير: يا الانتظار، وهذا هو أساسا ما قمت بنشرها. LOL.