ما هي مشكلة البائع المتجول؟

هي مشكلة إيجاد أقصر طريق ممكن يزور مجموعة معطاة من المدن كل واحدة مرة واحدة بالضبط ويعود إلى مدينة البداية — مشكلة تحسين NP-صعبة كلاسيكية.

ما هي خوارزمية Held-Karp؟

هي خوارزمية برمجة ديناميكية تحل مشكلة البائع المتجول بدقة في زمن O(n² · 2ⁿ) بتتبع الحد الأدنى من التكلفة للوصول إلى كل مجموعة من (مجموعة جزئية من المدن التي تمت زيارتها، المدينة الحالية)، أفضل بشكل كبير من O(n!) للقوة الغاشمة.

هل هذا يجد الجولة المثلى أم مجرد جولة جيدة؟

الجولة المثلى الدقيقة — Held-Karp ليست إرشادية أو تقريبية؛ من المضمون أنها تجد الجولة الحقيقية ذات التكلفة الأدنى، بخلاف الطرق الإرشادية الأسرع مثل الجار الأقرب أو 2-opt.

لماذا هذا الحلّال محدود بـ 12 مدينة؟

لا يزال زمن ومساحة Held-Karp من الرتبة O(n² · 2ⁿ) ينمو أسيًّا — تُبقي 12 مدينة الحساب فوريًا بشكل مريح في المتصفح، مع تغطية الغالبية العظمى من الأمثلة المُدخلة يدويًا التي يريد الناس حلها بدقة.

هل تحتاج مصفوفة المسافات إلى أن تكون متماثلة؟

لا — يعمل هذا الحلّال مع مسافات غير متماثلة (حيث تختلف تكلفة الانتقال من A إلى B عن B إلى A)، مما يغطي كلًا من أمثلة مسافة الطريق المتماثلة البسيطة والحالات الاتجاهية مثل الشوارع ذات الاتجاه الواحد أو تكاليف الرحلات الجوية.

ما الخوارزمية التي يجب أن أستخدمها لأكثر من 12 مدينة؟

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

كيف يختلف هذا عن آلة حاسبة الشجرة الممتدة الصغرى؟

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

أين تُستخدم مشكلة البائع المتجول في الحياة الواقعية؟

تُستخدم في تخطيط مسارات التوصيل واللوجستيات، وحفر لوحات الدوائر المطبوعة وتصنيعها، وتسلسل الحمض النووي، وكمشكلة مرجعية لخوارزميات التحسين في بحوث العمليات.

حلّال مشكلة البائع المتجول — أوجد أقصر طريق عبر كل مدينة

يجد حلّال مشكلة البائع المتجول الخاص بنا الجولة الدقيقة ذات التكلفة الأدنى التي تزور كل مدينة مرة واحدة بالضبط وتعود إلى مدينة البداية، بمعطى مصفوفة مسافات بين المدن، باستخدام خوارزمية البرمجة الديناميكية بقناع البت Held-Karp — طريقة دقيقة محدودة عمدًا بحد أقصى 12 مدينة لأن المشكلة NP-صعبة بشكل عام.

إجابة سريعة

أدخل مصفوفة مسافات بين المدن لإيجاد جولة الذهاب والعودة الأقصر الدقيقة فورًا عبر البرمجة الديناميكية Held-Karp.

مصفوفة المسافات

أدخل صفًا واحدًا لكل مدينة، بمسافات مفصولة بفواصل، مثل 0,10,15,20 ثم 10,0,35,25. حتى 12 مدينة.

كيفية استخدام حلّال مشكلة البائع المتجول — برمجة ديناميكية دقيقة بخوارزمية Held-Karp عبر الإنترنت

1
أدخل مصفوفة مسافات، صف واحد لكل مدينة، بمسافات مفصولة بفواصل، مثل 0,10,15,20 ثم 10,0,35,25 وهكذا.
2
يجب أن تكون المصفوفة مربعة، مع إعطاء كل مدخل المسافة بين مدينتين (مدخلات القطر عادة 0).
3
انقر على 'احسب' لإيجاد الجولة المثلى الدقيقة عبر البرمجة الديناميكية Held-Karp.

لماذا تستخدم حلّال مشكلة البائع المتجول — برمجة ديناميكية دقيقة بخوارزمية Held-Karp عبر الإنترنت؟

تسأل مشكلة البائع المتجول عن أقصر طريق ممكن يزور كل مدينة مرة واحدة بالضبط ويعود إلى البداية — مشكلة NP-صعبة كلاسيكية حيث يصبح التحقق الشامل من كل (n−1)!/2 جولة ممكنة مستحيلًا بعد عدد قليل من المدن. تُحسّن خوارزمية Held-Karp بشكل كبير على القوة الغاشمة باستخدام برمجة ديناميكية على المجموعات الجزئية: تتتبع، لكل مجموعة جزئية من المدن التي تمت زيارتها وكل مدينة نهاية ممكنة، أرخص طريقة للوصول إلى تلك الحالة، بالبناء من مجموعات جزئية صغيرة إلى المجموعة الكاملة في زمن O(n² · 2ⁿ) بدلاً من O(n!). هذا لا يزال أسيًّا، لذا تحد هذه الآلة الحاسبة المشكلة بـ 12 مدينة، حيث تظل Held-Karp سريعة بشكل مريح مع إيجاد الجولة الدقيقة والمثبتة كأمثل (وليس مجرد تقريب جيد).

الأسئلة الشائعة

أدوات ذات صلة

مدقق مسار هاملتون — زر كل عقدة مرة واحدة عبر الإنترنت

تحقق مما إذا كان لرسم بياني مسار هاملتون — مسار يزور كل عقدة مرة واحدة بالضبط — عبر بحث التراجع. آلة حاسبة مجانية، محدودة برسوم بيانية تصل إلى 10 عقد.

آلة حاسبة الشجرة الممتدة الصغرى — خوارزمية كروسكال عبر الإنترنت

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

حلّال البرمجة الخطية — طريقة نقاط الزاوية لمتغيرين عبر الإنترنت

حلّ برنامجًا خطيًا بمتغيرين بإيجاد وتقييم كل نقطة زاوية في المنطقة الممكنة. آلة حاسبة مجانية، عظّم أو صغّر بقيود خطية.