نظرية الرسم البياني السؤال جافا.التي الخوارزمية إلى تحقيق ما يلي

Question

لدي البياني ، مع X العقد و Y الحواف.مرجحة الحواف.وهذه النقطة هي أن تبدأ في عقدة واحدة ، ووقف في آخر.الآن هنا يأتي المشكلة ؛

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

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

تحديث: اختبرت من الأشياء التي لم يكن العمل بالنسبة لي.عقدة يجب أن يكون واحد ماكس شاحنة لكل واردة الحافة.

Answer 1

الخاص ديكسترا الخوارزمية يجب أن تعمل ، ولكن "المسافة" في هذه الحالة هو غريب قليلا.الخاص بك "المسافة" هو الحد الأقصى الحجم شاحنة يمكنك الحصول على عقدة.دعونا ندعو أن م[v] عن عقدة ضدتحتاج إلى عملية العقد في أمر من أكبر م[v] إلى أصغر م[v] (عكس العادي الخاص ديكسترا) ، وحساب لكل حافة e v w:

M[w] = max(M[w], min(e.weight, M[v]))

Answer 2

هذه الأصوات (تقريبا) بالضبط مثل أقصى تدفق المشكلة والتي يمكن حلها بكفاءة باستخدام فورد-Fulkerson الخوارزمية.

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

Answer 3

أعتقد أنك تبحث عن هذا

أقصر طريق

تحرير:في الواقع لا تخلخل و أقصى تدفق الرابط الصحيح

Answer 4

أنا أفهم هذا بشكل صحيح, أنت تسأل "ما هو أكبر شاحنة التي يمكن أن تدفع من ألف إلى باء"

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

Answer 5

كنت تبحث لتحسين a [http://en.wikipedia.org/wiki/Flow_network].القدرة هي الطريق ماكس الوزن الحد ؛ وتدفق هو وزن الشاحنة.

Answer 6

هل يمكن أن تأخذ نوعا من الحد الأدنى من شجرة الامتداد النهج.ربط العقد حافة واحدة في كل مرة ، أعلى تدفق حواف أولا ، حتى أ و ب متصلة.آخر حافة إضافة إلى الرسم البياني هو أدنى تدفق الحافة التي يجب أن تعبر للوصول من A إلى B.ربما ليس الحل الأكثر فعالية (O(N²) أسوأ الأحوال) ولكن على الأقل انها واضحة.

Answer 7

هذه ليست مشكلة أقصر مسار ، ولا تدفق ماكس المشكلة.في الواقع ليس هناك مشكلة.وذكر - تريد ماكس الوزن لجميع مسارات أ إلى ب.لذلك يذهب إلى توليد جميع المسارات من BFS.لجميع مسارات تنتهي في ب على العثور على مين وزن مسار الحواف.

Answer 8

استخدام الخاص ديكسترا الخوارزمية مع معكوس الأقصى شاحنة وزن الحافة التكلفة القصوى الفردية حافة الأوزان كما إجمالي التكلفة الطريق.

أي edge_cost يساوي 1/(الحد الأقصى شاحنة للوزن المسموح به) على total_cost من طريق معين هو الحد الأقصى للفرد edge_cost's من جميع حواف في الطريق.

Answer 9

إجابات مختلفة أعلاه نقترح ببساطة الخاص ديكسترا الخوارزمية مع تعديل وظيفة الوزن.على سبيل المثال ، w(e) = -c(e), أو 'w(e) = 1/c(e) ، w(e) وزن الحافة ، وتستخدم من قبل الخوارزمية ، c(e) هو قدرة edge في الأصل صياغة المشكلة.

هذه لا تعمل.

واحد يمكن بسهولة إنشاء أمثلة مضادة أن هذا من شأنه أن تسفر عن نتائج غير صحيحة.على سبيل المثال النظر في الرسم البياني:

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

نفترض قيمة a ('المسافة من عقدة a في الخوارزمية صياغة) هو صفر.اثنين من مسارات a إلى d تعادل في هذه المشكلة.ومع ذلك, إذا نحن فقط ينفي حافة القدرة المسافة(d) باستخدام الطريق الطويل ، (-3)+(-3)+(-3) = -9 أثناء استخدام الطريق القصير سيكون -3.إذا كنا معكوس حافة القدرة المسافة(d) باستخدام الطريق الطويل سيكون (1/3)+(1/3)+(1/3)=1, في حين سيكون (1/3) باستخدام واحدة قصيرة.

ما سوف العمل هو تعديل الاسترخاء خطوة من الخوارزمية ، أيبدلا من استخدام وظائف بالإضافة إلى ذلك (+) وأقل من (<) ، وذلك باستخدام وظائف على التوالي min و أكبر من (>) ، واستخدام أقصى كومة بدلا من مين كومة.يمكننا تجنب الماضيين التعديلات إذا كنا ينفي حافة الأوزان و استخدام أقل ، ولكن لا يمكننا تجنب استبدال +, منذ نحتاج المشغل @ حيث a @ a = a للجميع a القيم ، بينما + يعمل فقط على a=0.

لذا الإجابة الصحيحة أراه هو أول واحد معين ، راندل كيث.

لطيفة العملية رسميا يثبت أن تعديل الخوارزمية هو الصحيح.ما يحتاج إلى أن يثبت هو:- إذا u هو عقدة مع أقصى قيمة d(u) في أي حلقة التكرار ثم أي مسار تنطوي على علامات العقد يمكن إنشاء مسار u العائد مسافة أكبر من d(u).

حدسي فمن السهل أن نرى ، لأن جميع علامات العقد يكون بعد أقل من (أو مساوية) المسافة من 'u' (لأننا نختار u بوصفها واحدة مع المسافة القصوى), والمسافة من إنشاء مسارات تنتجه المتعاقبة من الدعاء min, وبالتالي فإنه يمكن أن تنمو فقط أصغر لا أكبر.