مشكلة وضع المسار/الطريق

Question

اليوم حصلنا على مهمة لإكمالها في المختبر (في ساعتين). كان السؤال:

• لقد أعطيت مصفوفة m*n.
• تحتوي المصفوفة على قاعات سكنية "H" ومداخل المبنى الرئيسي "B".
• يُعرف موقع مداخل "H" ومداخل "B" (من حيث الإحداثيات (X ، Y)).
• تحتاج إلى وضع مسارات بحيث يكون لكل قاعة سكنية طريقة واحدة على الأقل للوصول إلى أحد مداخل "B".
• يمكن أن يكون هناك على الأكثر "B" مثل هذه المسارات غير المتصل.
• يجب أن يكون طول المسار الحد الأدنى.
• يمكنك فقط التحرك لأعلى أو لأسفل أو يسارًا أو يمينًا.
• يجب ألا يكون الحل محاولة القوة الغاشمة.

انتهت المهمة. لكنني ما زلت أفكر في كيفية حل هذا. هل هناك مصطلح قياسي لمثل هذه المشكلات؟ ماذا يجب أن أقرأ؟

هل يستخدم الناس هذه الخوارزميات لوضع الطرق في المدن أيضًا؟

Answer 1

هذا حل توصلت إليه. لا يولد مسارات "ب" غير متصل. يولد مسارًا واحدًا يمر عبر جميع القاعات السكنية والمداخل.

• احسب المسافة بين كل زوج من العقد (اختلاف الإحداثيات X + اختلاف إحداثيات Y). الآن لديك رسم بياني كامل.
• ابحث عن MST لهذا الرسم البياني الكامل
• يمكن تقسيم كل حافة مائلة لـ MST (تلك التي ليست رأسية أو أفقية) إلى جزأين - الأفقي والرأسي.
• يمكن إجراء كل تقسيم بطريقتين - إما أفقي أولاً متبوعًا بعمودي أو عكس.
• تمر من خلال كل هذا التقليب وحساب المسار بأقل طول. هذا هو الجواب.

Answer 2

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

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

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

آمل أن يوفر هذا بعض السياق المفيد.

Answer 3

هناك جانب من جوانب وصف المشكلة غير واضح بالنسبة لي:

• عندما تقول ، "تحتاج إلى وضع مسار" ، هل يعني ذلك "واحدة فقط مسار متصل؟ "أو هل يمكن أن يكون هناك مسارات متعددة غير متصلة؟ (على سبيل المثال ، مسار من القاعة H1 إلى بناء مدخل B1 ومسار منفصل من القاعة H2 إلى بناء مدخل B2)

لكنك تجيب على سؤالي ، فهذه مشكلة صعبة للغاية: إنها np-hard لأنها تشمل شجرة شتاينر المستطيلة مشكلة كحالة خاصة (عندما يكون هناك مدخل بناء رئيسي واحد فقط).

لذلك لا أحد يعرف كيفية حلها بكفاءة في الحالة العامة!

Answer 4

أعتقد أن المشكلة أبسط وليس شجرة شتاينر أو حتى شجرة تمتد على الأقل.

1. تمثل المصفوفة M كرسومات G مع v = {mij | i <= m ، j <= n} ، e = {(mi1j1 ، mi2j2): i1 ، i2 <= m ، j1 ، j2 <= n ، | i1-i2 | = 1-الحصري أو | j1-j2 | = 2}

2. خذ المجموعة B من المداخل ، مجموعة H من القاعات

3. h '= h/b ، b' = b/h (حدد القاعات التي هي مداخل ، يتم الوصول إليها على العمق 0 ، وإزالة كل هذه المداخل لأن تلك القاعات)

4. القيام بعرض العرض الأول. في كل عمق علامة القاعات التي يمكن الوصول إليها من B حتى يتم تمييز جميع القاعات. اختيار المسارات المقابلة.

Answer 5

إنها مشكلة في البحث. كان من المتوقع أن تفعل ذلك خلال ساعتين ، أليس كذلك؟ أود DFS و برقوق مجفف. يمكنك استخدام الاستدلال للوصول إلى الحلول الأفضل بشكل أسرع. ولكن ضع في اعتبارك أن الاستدلال لا يمكن أن تضمن الحلول المثلى لذلك سيتعين عليك ذلك جرب كل الاحتمالات. يبدو أن np-hard.