الحد الأدنى من التكلفة مرتبطة بقوة digraph

Question

لدي digraph وهي مرتبطة بقوة (أيهناك مسار من i إلى j j i لكل زوج من العقد (i, j) في الرسم البياني ز).أتمنى أن تجد مرتبطة بقوة الرسم البياني من هذا الرسم البياني أن مجموع كل حواف هو الأقل.

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

أعتقد أنه NP مشكلة صعبة.أنا أبحث عن الحل الأمثل ، لا التقريب ، من أجل مجموعة صغيرة من البيانات مثل 20 العقد.

تحرير

المزيد من الوصف العام:بالنظر إلى مسافة ز(V,E) العثور على الرسم البياني G'(V,E) بحيث إذا كان هناك مسار من v1 إلى v2 غرام من هناك أيضا الطريق بين v1 و v2 في ز' و مجموع كل ei في ه' هو أقل قدر ممكن.لذلك مماثل لإيجاد الحد الأدنى يعادل الرسم البياني, هنا فقط نريد للحد من مجموع حافة الأوزان بدلا من مبلغ الحواف.

تحرير:

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

Answer 1

المشكلة كما هو معروف الحد الأدنى تمتد قوية الفرعية(دي)الرسم البياني (MSSS) أو أعم الحد الأدنى من التكلفة التي تغطي الفرعية(دي)الرسم البياني و هو NP-من الصعب في الواقع.انظر أيضا كتاب آخر: الصفحة 501 و الصفحة 480.

أود أن تبدأ مع إزالة الحواف التي لا تستوفي المساواة في المثلث - يمكنك إزالة الحافة مجموعة -> c إذا كان الذهاب a -> b> c هو أرخص.هذا يذكرني ملعقة صغيرة ولكن لا أعرف إذا كان ذلك يؤدي إلى أي مكان.

إجابتي السابقة تم استخدام تشو-ليو/إدموندز الخوارزمية الذي يحل Arborescence المشكلة ؛ كما Kazoom و ShreevatsaR أشار إلى أن هذا لا يساعد.

Answer 2

وأود أن محاولة هذا في البرمجة الديناميكية نوع من الطريق.

0 - وضع الرسم البياني إلى قائمة

1 - تقديم قائمة جديدة subgraphs من كل رسم بياني في القائمة السابقة ، حيث قمت بإزالة أحد مختلفة حافة لكل من جديد subgraphs

2 - إزالة التكرارات من القائمة الجديدة

3 - إزالة جميع الرسوم البيانية من القائمة الجديدة التي ليست مرتبطة بقوة

4 - قارن أفضل الرسم البياني من القائمة الجديدة الحالية أفضل ، إن أفضل مجموعة جديدة الحالية أفضل

5 - إذا الجديدة القائمة فارغة الحالي أفضل هو الحل وإلا recurse/حلقة/goto 1

في اللثغة ، ربما يمكن أن تبدو مثل هذا:

(defun best-subgraph (digraphs &optional (current-best (best digraphs)))
  (let* ((new-list (remove-if-not #'strongly-connected
                                  (remove-duplicates (list-subgraphs-1 digraphs)
                                                     :test #'digraph-equal)))
         (this-best (best (cons current-best new-list))))
    (if (null new-list)
        this-best
        (best-subgraph new-list this-best))))

تعاريف strongly-connected, list-subgraphs-1, digraph-equal, best, ، better يتم ترك باعتبارها ممارسة للقارئ.

Answer 3

وهذه المشكلة ما يعادل صفت المشكلة هنا: HTTP: // شبكة الاتصالات العالمية .facebook.com / وظائف / puzzles.php؟ puzzle_id = 1

Answer 4

بعض الأفكار التي ساعدتني على حل الشهيرة facebull اللغز:

تجهيز خطوة:

1. التقليم:إزالة جميع حواف a-b إذا كان هناك أرخص أو وجود نفس التكلفة مسار, على سبيل المثال:a-c-b.

2. الرسم البياني التحلل:يمكنك حل المسائل الفرعية للحصول إذا كان الرسم البياني توضيح نقاط

3. دمج الذروات إلى أحد الظاهري قمة الرأس إذا كان هناك واحد فقط المنتهية ولايته الحافة.

خطوة حسابية:

1. الحصول على حل تقريبي باستخدام توجيه ملعقة صغيرة مع الزيارات المتكررة.استخدام فلويد Warshall ثم حل التعيين مشكلة O(N^3) باستخدام الطريقة الهنغارية.إذا كان علينا مرة واحدة في دورة إنه توجه ملعقة صغيرة من الحل إن لم يكن - استخدام فرع لا بد ملعقة شاي.بعد أن قمنا الأعلى قيمة - دورة الحد الأدنى من التكلفة.

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

وهذا هو كل الناس.إذا كنت ترغب في اختبار الحلول الخاصة بك - في محاولة هنا: http://codercharts.com/puzzle/caribbean-salesman

Answer 5

ويبدو وكأنه كنت تريد استخدام ديكسترا خوارزمية

Answer 6

يبدو ما تريد أساسا هو الحل الأمثل للسفر-بائع حيث أنه لا يجوز العقد على زيارتها أكثر من مرة.

تحرير:

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

Answer 7

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

وهو خارج المتفرعة, ، المعروف أيضا باسم arborescence, هو توجيه شجرة متجذرة في واحد vertex تغطي جميع الذروات.في المتفرعة هو نفسه مع عكس الحواف.هذه يمكن العثور عليها عن طريق إدموندز' الخوارزمية في الوقت O(VE), و هناك speedups إلى O(هـ سجل(V)) (انظر صفحة ويكي).هناك حتى تنفيذ مفتوحة المصدر.

الأصلي مرجعا 2-تقريب النتيجة ورقة جاجه و Frederickson, لكن الورقة لا يمكن الوصول إليها بحرية.

بل هناك 3/2 تقريب أدريان Vetta (PDF), ولكن أكثر تعقيدا مما سبق.