العثور على أقصر مسار في الرسم البياني الذي يزور بعض العقد

Question

لدي صليات الرسم البياني مع حوالي 100 العقد حوالي 200 الحواف.عقدة واحدة هو المسمى 'ابدأ' ، واحد هو 'نهاية' و هناك عشرات المسمى 'mustpass'.

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

( http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txt هو الرسم البياني في السؤال - فإنه يمثل متاهة الذرة في Lancaster, PA)

Answer 1

وأي شخص آخر يقارن هذا إلى مشكلة بائع السفر ربما لم يقرأ سؤالك بعناية. في TSP، والهدف من ذلك هو إيجاد أقصر دورة أن يزور <م> جميع القمم (دورة هاملتون) - أنه يتوافق مع وجود <م> كل عقدة المسمى "mustpass '

في قضيتك، بالنظر إلى أن لديك فقط حوالي اثني عشر المسمى 'mustpass، وبالنظر إلى أن 12! صغيرة نسبيا (479001600)، يمكنك ببساطة محاولة كل التباديل فقط العقد في "mustpass، وإلقاء نظرة على أقصر الطرق من 'بداية' إلى 'نهاية' أن يزور العقد على" mustpass "في هذا النظام - وسوف ببساطة يكون سلسلة من أقصر الطرق بين عقدتين كل متتالية في تلك القائمة.

وبعبارة أخرى، أولا إيجاد أقصر مسافة بين كل زوج من القمم (يمكنك استخدام خوارزمية ديكسترا أو غيرها، ولكن مع هذه الأرقام صغيرة (100 العقد)، وحتى، أبسط، إلى رمز <لأ href = "HTTP: //en.wikipedia.org/wiki/Floyd-Warshall_algorithm "يختلط =" noreferrer "> فلويد-ارشال خوارزمية سيتم تشغيل في الوقت المناسب). ثم، مرة واحدة لديك هذا في الجدول، في محاولة كل التباديل العقد الخاص بك mustpass، وبقية العالم.

وشيء من هذا القبيل:

//Precomputation: Find all pairs shortest paths, e.g. using Floyd-Warshall
n = number of nodes
for i=1 to n: for j=1 to n: d[i][j]=INF
for k=1 to n:
    for i=1 to n:
        for j=1 to n:
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])
//That *really* gives the shortest distance between every pair of nodes! :-)

//Now try all permutations
shortest = INF
for each permutation a[1],a[2],...a[k] of the 'mustpass' nodes:
    shortest = min(shortest, d['start'][a[1]]+d[a[1]][a[2]]+...+d[a[k]]['end'])
print shortest

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

وفستعمل في في معظم بضع ثوان على أي لغة معقولة :)
[إذا كان لديك عقد ن والعقد ك "mustpass، إدارة الوقت لها هو O (ن <سوب> 3 ) بالنسبة للجزء فلويد-ارشال، وO (ك! ن) بالنسبة للجزء جميع التباديل، و 100 ^ 3 + (12!) (100) هو عمليا الفول السوداني إلا إذا كان لديك بعض القيود المقيدة حقا.]

Answer 2

خوارزمية

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

Answer 3

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

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

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

ومجرد بديل للنظر فيها. أنها لا تبدو <م> ملحوظة مثل مشكلة السفر بائع، وتلك هي الأوراق جيدة لقراءة ما يصل، ولكن نظرة فاحصة وسترى أن الأمور فقط overcomplicating لها. ^ _ ^ هذا القادمة من عقل مبرمج لعبة فيديو من الذي تعامل مع مثل هذه الامور من قبل.

Answer 4

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

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

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

Answer 5

وأندرو الأعلى لديه فكرة الحق:

1) خوارزمية Djikstra ل 2) بعض TSP الكشف عن مجريات الأمور.

وأوصي ارشادي لين كيرنيغان: انها واحدة من أشهر عن أي مشكلة كاملة NP. الشيء الوحيد الآخر هو أن نتذكر أنه بعد توسيع خارج الرسم البياني مرة أخرى بعد الخطوة 2، قد يكون لديك الحلقات في المسار الموسعة، لذلك يجب عليك يرحل تلامس تلك (نظرة على درجة من القمم على طول المسار الخاص بك).

وانا فعلا لست متأكدا كيف جيدة هذا الحل ستكون نسبة إلى الأمثل. ربما يكون هناك بعض الحالات المرضية للقيام مع الدائرة القصيرة. بعد كل شيء، هذه المشكلة يتطلع الكثير مثل شتاينر شجرة: http://en.wikipedia.org/wiki/Steiner_tree و أنت بالتأكيد لا يمكن تقريب شتاينر شجرة فقط عن طريق التعاقد الرسم البياني الخاص بك وتشغيلها في كروسكال على سبيل المثال.

Answer 6

هذا هو لا ملعقة المشكلة وليس NP-hard لأن السؤال الأصلي لا يحتاج إلى ذلك يجب أن تمر العقد زار مرة واحدة فقط.وهذا ما يجعل الإجابة كثيرا ، أبسط من ذلك بكثير فقط القوة الغاشمة بعد تجميع قائمة من أقصر المسارات بين جميع يجب أن تمر العقد عبر الخاص ديكسترا الخوارزمية.هناك قد يكون أفضل طريقة للذهاب ولكن واحد بسيط سيكون ببساطة عمل شجرة ثنائية إلى الوراء.تخيل قائمة العقد [بداية,a,b,c,end].مبلغ بسيط مسافات [start->a->b>c>end] هذا هو هدفك الجديد مسافة للفوز.حاول الآن [start->أ>ج>ب->end] وإذا كان هذا هو أفضل وضع هذا الهدف (وتذكر أنه جاء من هذا النمط من العقد).العمل إلى الوراء أكثر من التباديل:

• [start->a->b>c>end]
• [start->أ>ج>ب->end]
• [start->b->->c->end]
• [start->b>c>a->end]
• [start->c>a->b>end]
• [start->c>b->->end]

واحد من هؤلاء سوف يكون أقصر.

(أين هي 'زار عدة مرات' العقد ، إن وجدت ؟ هم فقط خفية في أقصر مسار التهيئة الخطوة.أقصر طريق بين a و b قد تحتوي على c أو حتى نقطة النهاية.أنت لا تحتاج إلى الرعاية)

Answer 7

ونظرا لكمية من العقد والحواف غير محدود نسبيا، ربما يمكنك حساب كل طريق ممكن واتخاذ أقصر واحدة.

وعموما هذا المعروفة باسم مشكلة السفر بائع، ولها وقت متعدد الحدود غير القطعية، بغض النظر عن خوارزمية الذي تستخدمه.

http://en.wikipedia.org/wiki/Traveling_salesman_problem

Answer 8

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

والآن تم تبسيط مشكلتك إلى واحدة من إيجاد الطرق المثلى من عقدة البداية الى الدائرة، والتي ثم اتبع حولها حتى كنت قد غطت عليها، ومن ثم العثور على الطريق من ذلك إلى نهاية.

يتكون

ومسار النهائي:

والبدء -> الطريق إلى الدائرة * -> دائرة من يجب أن زيارة العقد -> مسار لانهاء * -> نهاية

ويمكنك العثور على مسارات أنا التي تحمل علامة * مثل هذا

هل لA * البحث من عقدة البداية الى كل نقطة على الدائرة لكل من هذه قيام A * البحث عن عقدة القادمة والسابقة على حلبة لنهاية (لأنه يمكنك متابعة الجولة دائرة في أي من الاتجاهين) ما ينتهي بك الأمر مع هو الكثير من مسارات البحث، ويمكنك اختيار واحد مع بأقل تكلفة.

وهناك الكثير من الغرفة لتعظيم الاستفادة من التخزين المؤقت عمليات البحث، ولكن أعتقد أن هذا سوف تولد حلولا جيدة.

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

Answer 9

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

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