مشكلة المسار الهاميلتوني

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
📷 يحتوي على 4 صور
الموسوعة الحرة

تُعدّ مسألة المسار الهاميلتوني موضوعًا يُناقش في مجالي نظرية التعقيد ونظرية المخططات . وهي تُحدّد ما إذا كان مخطط G ، سواءً كان مُوجّهًا أو غير مُوجّه ، يحتوي على مسار هاميلتوني ، وهو مسار يمرّ بكل رأس في المخطط مرة واحدة فقط. قد تُحدّد المسألة بداية المسار ونهايته، وفي هذه الحالة يجب تحديد رأس البداية s ورأس النهاية t . [ 1 ]

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

تُصنَّف مسألة المسار الهاميلتوني ومسألة الدورة الهاميلتونية ضمن فئة المسائل الكاملة من نوع NP ، كما هو موضح في كتاب مايكل غاري وديفيد إس. جونسون بعنوان "الحواسيب والاستعصاء: دليل لنظرية الاكتمال من نوع NP" وقائمة ريتشارد كارب التي تضم 21 مسألة كاملة من نوع NP . [ 2 ] [ 3 ]

تخفيضات

الاختزال من مشكلة المسار إلى مشكلة الدورة

يمكن ربط مشكلتي إيجاد مسار هاميلتوني ودورة هاميلتونية على النحو التالي:

  • في اتجاه واحد، يمكن ربط مسألة المسار الهاميلتوني للرسم البياني G بمسألة الدورة الهاميلتونية في الرسم البياني H المُشتق من G بإضافة رأس عالمي جديد x ، ​​يربط x بجميع رؤوس G. وبالتالي، لا يمكن أن يكون إيجاد مسار هاميلتوني أبطأ بشكل ملحوظ (في أسوأ الحالات، كدالة لعدد الرؤوس) من إيجاد دورة هاميلتونية.
  • في الاتجاه الآخر، تُكافئ مسألة دورة هاميلتون للرسم البياني G مسألة مسار هاميلتون في الرسم البياني H الناتج عن إضافة رأسين طرفيين ( من الدرجة الأولى) s و t متصلين على التوالي بالرأس v من G وبالرأس v'، وهو نسخة منقسمة من v تُعطي v' نفس جوار v . مسار هاميلتون في H يمر عبر الرؤوس ⁠s-v-x-⋯-y-v′-ت{\displaystyle svx-\cdots -yv'-t}يتوافق مع دورة هاميلتونية في G تمر عبرv-x-⋯-y(-v){\displaystyle vx-\cdots -y(-v)}[ 4 ]​​

الخوارزميات

القوة الغاشمة

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

المسارات الجزئية

كانت خوارزمية مارتيلو التعدادية إحدى الخوارزميات الدقيقة المبكرة لإيجاد دورة هاميلتونية على رسم بياني موجه. [ 3 ] وتقوم خوارزمية بحث فرانك روبين [ 5 ] بتقسيم حواف الرسم البياني إلى ثلاث فئات: حواف يجب أن تكون في المسار، وحواف لا يمكن أن تكون في المسار، وحواف غير محددة. ومع تقدم البحث، تقوم مجموعة من قواعد القرار بتصنيف الحواف غير المحددة، وتحديد ما إذا كان يجب إيقاف البحث أو الاستمرار فيه. ويمكن حذف الحواف التي لا يمكن أن تكون في المسار، مما يؤدي إلى تقليص حجم البحث باستمرار. كما تقسم الخوارزمية الرسم البياني إلى مكونات يمكن حلها بشكل منفصل، مما يقلل حجم البحث بشكل كبير. عمليًا، لا تزال هذه الخوارزمية هي الأسرع.

البرمجة الديناميكية

كذلك، يمكن استخدام خوارزمية البرمجة الديناميكية لبلمان وهيلد وكارب لحل المسألة في زمن O( n² / 2 ). في هذه الطريقة، يتم تحديد ما إذا كان هناك مسار يغطي جميع رؤوس S وينتهي عند v ، وذلك لكل مجموعة S من الرؤوس ولكل رأس v في S. لكل اختيار لـ S و v ، يوجد مسار لـ ( S , v ) إذا وفقط إذا كان لـ v جار w بحيث يوجد مسار لـ ( S - v , w ) ، والذي يمكن استخلاصه من المعلومات المحسوبة مسبقًا في البرنامج الديناميكي. [ 6 ] [ 7 ]

مونت كارلو

قدّم أندرياس بيوركلوند منهجًا بديلًا باستخدام مبدأ الإدراج والاستبعاد لتبسيط مسألة حساب عدد دورات هاميلتون إلى مسألة حساب أبسط، وهي حساب أغطية الدورات، والتي يمكن حلها بحساب محددات مصفوفة معينة. وباستخدام هذه الطريقة، بيّن كيفية حل مسألة دورة هاميلتون في أي رسم بياني ذي n رأس باستخدام خوارزمية مونت كارلو في زمن O(1.657 n )؛ وبالنسبة للرسوم البيانية ثنائية الأجزاء ، يمكن تحسين هذه الخوارزمية لتصل إلى زمن O (1.415 n ). [ 8 ]

التراجع

بالنسبة للرسوم البيانية ذات الدرجة القصوى ثلاثة، يمكن لعملية بحث دقيقة بالتراجع أن تجد دورة هاميلتونية (إن وجدت) في زمن قدره O(1.251 n ). [ 9 ]

قابلية الإرضاء المنطقية

يمكن إيجاد مسارات هاميلتونية باستخدام خوارزمية حل SAT . مسار هاميلتون هو مسألة NP-كاملة، مما يعني أنه يمكن اختزاله إلى مسألة 3-SAT . ونتيجة لذلك، فإن إيجاد حل لمسألة مسار هاميلتون يُكافئ إيجاد حل لمسألة 3-SAT.

أساليب غير تقليدية

نظراً لصعوبة حلّ مسائل المسار والدورة الهاميلتونية على الحواسيب التقليدية، فقد دُرست أيضاً في نماذج حوسبة غير تقليدية. على سبيل المثال، بيّن ليونارد أدلمان إمكانية حلّ مسألة المسار الهاميلتوني باستخدام حاسوب الحمض النووي . وباستغلال التوازي المتأصل في التفاعلات الكيميائية، يمكن حلّ المسألة باستخدام عدد من خطوات التفاعل الكيميائي يتناسب خطياً مع عدد رؤوس الرسم البياني؛ إلا أن ذلك يتطلب عدداً مضروباً من جزيئات الحمض النووي للمشاركة في التفاعل. [ 10 ]

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

تعقيد

تُصنَّف مسألة إيجاد دورة أو مسار هاميلتوني ضمن مسائل NP-الكاملة ؛ وتتمثل المسألة المماثلة في اختبار وجود دورة أو مسار هاميلتوني. وكانت مسألتا الدورة الهاميلتونية الموجهة وغير الموجهة من بين مسائل كارب الـ 21 المصنفة ضمن مسائل NP-الكاملة . وتبقى هذه المسائل مصنفة ضمن مسائل NP-الكاملة حتى بالنسبة لأنواع خاصة من الرسوم البيانية، مثل:

ومع ذلك، بالنسبة لبعض الفئات الخاصة من الرسوم البيانية، يمكن حل المشكلة في وقت متعدد الحدود:

  • تكون الرسوم البيانية المستوية ذات الاتصال الرباعي دائمًا هاميلتونية وفقًا لنتيجة توتي ، ويمكن تنفيذ المهمة الحسابية لإيجاد دورة هاميلتونية في هذه الرسوم البيانية في وقت خطي [ 18 ] عن طريق حساب ما يسمى مسار توتي .
  • أثبت توت هذه النتيجة بإثبات أن كل رسم بياني مستوٍ ثنائي الاتصال يحتوي على مسار توت. ويمكن حساب مسارات توت بدورها في زمن تربيعي حتى بالنسبة للرسوم البيانية المستوية ثنائية الاتصال، [ 19 ] وهو ما يمكن استخدامه لإيجاد دورات هاميلتونية ودورات طويلة في تعميمات الرسوم البيانية المستوية.

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

في الرسوم البيانية التي تكون فيها جميع الرؤوس ذات درجة فردية، تُظهر حجة متعلقة بنظرية المصافحة أن عدد دورات هاميلتون التي تمر عبر أي حافة ثابتة يكون دائمًا زوجيًا، لذا إذا عُلمت دورة هاميلتون واحدة، فلا بد من وجود دورة ثانية أيضًا. [ 20 ] مع ذلك، يبدو أن إيجاد هذه الدورة الثانية ليس مهمة حسابية سهلة. وقد عرّف باباديميتريو فئة التعقيد PPA لتضمين مسائل كهذه. [ 21 ]

مدقق زمني متعدد الحدود

يشكل الحل المقترح {s,w,v,u,t} مسارًا هاميلتونيًا صالحًا في الرسم البياني G.

تُصنف مسألة مسار هاميلتون ضمن فئة NP، مما يعني أنه يمكن التحقق من الحل المقترح في وقت متعدد الحدود . [ 1 ]

تأخذ خوارزمية التحقق من مسار هاميلتوني كمدخلات رسمًا بيانيًا G، ورأس البداية s، ورأس النهاية t. بالإضافة إلى ذلك، تتطلب خوارزمية التحقق حلًا محتملًا يُعرف باسم الشهادة c. في مسألة مسار هاميلتوني، تتكون c من سلسلة من الرؤوس، حيث يمثل الرأس الأول بداية المسار المقترح، ويمثل الرأس الأخير نهايته. [ 22 ] تحدد الخوارزمية ما إذا كانت c مسار هاميلتوني صالحًا في G، وإذا كان الأمر كذلك، تقبله.

لحسم هذا الأمر، يتحقق الخوارزمية أولًا من ظهور جميع رؤوس G مرة واحدة فقط في c. إذا نجح هذا التحقق، يضمن الخوارزمية أن الرأس الأول في c يساوي s والرأس الأخير يساوي t. أخيرًا، للتحقق من أن c مسار صالح، يجب على الخوارزمية التحقق من أن كل حافة بين رؤوس c هي بالفعل حافة في G. إذا فشل أي من هذه التحققات، سيرفض الخوارزمية المسار. وإلا، سيقبله. [ 22 ] [ 23 ]

يمكن للخوارزمية التحقق في وقت متعدد الحدود مما إذا كانت الرؤوس في G تظهر مرة واحدة في c. بالإضافة إلى ذلك، يستغرق التحقق من رؤوس البداية والنهاية، وكذلك الحواف بين الرؤوس، وقتًا متعدد الحدود. لذلك، تُعد الخوارزمية أداة تحقق متعددة الحدود لمسألة المسار الهاميلتوني. [ 22 ]

التطبيقات

الشبكات على رقاقة

تُستخدم الشبكات على الشريحة (NoC) في أنظمة الحاسوب والمعالجات كوسيلة اتصال للمكونات الموجودة على الشريحة. [ 24 ] يتحدد أداء الشبكة على الشريحة (NoC) بالطريقة التي تستخدمها لنقل حزم البيانات عبر الشبكة . [ 25 ] يمكن تطبيق مشكلة مسار هاميلتون كطريقة تعتمد على المسار في توجيه البث المتعدد . تحدد خوارزميات البث المتعدد القائمة على المسار ما إذا كان هناك مسار هاميلتون من عقدة البداية إلى كل عقدة نهاية، ثم ترسل الحزم عبر المسار المناسب. يضمن استخدام هذه الاستراتيجية توجيهًا خاليًا من حالات الجمود والتوقف ، مما يزيد من كفاءة الشبكة على الشريحة (NoC) . [ 26 ]

رسومات الحاسوب

محركات العرض هي نوع من البرامج المستخدمة في رسومات الحاسوب لإنشاء صور أو نماذج من بيانات الإدخال. [ 27 ] في عرض الرسومات ثلاثية الأبعاد ، يكون الإدخال الشائع للمحرك عبارة عن شبكة مضلعات . يعتمد وقت عرض الكائن على معدل استقبال الإدخال، أي كلما زاد حجم الإدخال زاد وقت العرض. أما بالنسبة لشبكات المثلثات، فيمكن تقليل وقت العرض حتى ثلاثة أضعاف. ويتم ذلك من خلال "ترتيب المثلثات بحيث تشترك المثلثات المتتالية في وجه واحد". [ 28 ] بهذه الطريقة، يتغير رأس واحد فقط بين كل مثلثين متتاليين. يتحقق هذا الترتيب إذا احتوى الرسم البياني الثنائي لشبكة المثلثات على مسار هاميلتوني.

مراجع

شعار ويكيميديا ​​كومنزالوسائط المتعلقة بمسألة مسار هاميلتوني على ويكيميديا ​​كومنز

  1. 1 2 سيبسر، مايكل (2013). مقدمة في نظرية الحوسبة (  الطبعة الثالثة). سينجايج ليرنينج. الصفحات 292-314 . 
  2. ↑ غاري، مايكل ر؛ جونسون، ديفيد س. (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان وشركاه. ص 60. 
  3. 1 2 هيلد، م.؛ كارب، ر.م. (1965). "بناء خوارزميات البرمجة الديناميكية المنفصلة" . مجلة أنظمة آي بي إم . 4 (2): 136-147 . doi : 10.1147/sj.42.0136 . ISSN 0018-8670 . 
  4. ↑ الاختزال من دورة هاميلتونية إلى مسار هاميلتوني
  5. ↑ روبين، فرانك (1974)، "إجراء بحث عن مسارات ودوائر هاميلتون"، مجلة ACM ، 21 (4): 576-80 ، doi : 10.1145/321850.321854 ، S2CID 7132716 
  6. ↑ بيلمان، ريتشارد (يناير 1962). "معالجة مسألة البائع المتجول باستخدام البرمجة الديناميكية" . مجلة ACM . 9 (1): 61-63 . doi : 10.1145/321105.321111 . ISSN 0004-5411 . S2CID 15649582 .  
  7. ↑ هيلد، مايكل؛ كارب، ريتشارد م. (مارس 1962). "نهج البرمجة الديناميكية لمشاكل التسلسل" . مجلة جمعية الرياضيات الصناعية والتطبيقية . 10 (1): 196-210 . doi : 10.1137/0110015 . ISSN 0368-4245 . 
  8. ↑ بيوركلوند، أندرياس (أكتوبر 2010). "مجاميع المحددات لهاملتونية غير موجهة" . المؤتمر السنوي الحادي والخمسون لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب، 2010. معهد مهندسي الكهرباء والإلكترونيات. الصفحات 173-182 . arXiv : 1008.0541 . doi : 10.1109/focs.2010.24 . ISBN  978-1-4244-8525-3.
  9. ↑ إيواما، كازو؛ ناكاشيما، تاكويا (2007)، "خوارزمية دقيقة محسّنة لمسألة البائع المتجول للرسم البياني المكعب" ، في لين، غوهوي (محرر)، الحوسبة والتوافقية ، سلسلة محاضرات في علوم الحاسوب، المجلد 4598، برلين، هايدلبرغ: سبرينغر برلين هايدلبرغ، الصفحات 108-117 ، doi : 10.1007/978-3-540-73545-8_13 ، ISBN   978-3-540-73544-1تم الاطلاع عليه بتاريخ 2023-10-07
  10. ↑ أدلمان، ليونارد (نوفمبر 1994)، "الحساب الجزيئي لحلول المسائل التوافقية"، مجلة ساينس ، 266 (5187): 1021-1024 ، Bibcode : 1994Sci...266.1021A ، CiteSeerX 10.1.1.54.2565 ، doi : 10.1126/science.7973651 ، JSTOR 2885489 ، PMID 7973651   .
  11. ↑ ميهاي أولتيان (2006). جهاز يعتمد على الضوء لحل مشكلة مسار هاميلتون . الحوسبة غير التقليدية. سلسلة محاضرات علوم الحاسوب من سبرينغر 4135. الصفحات 217-227. arXiv : 0708.1496 . doi : 10.1007 / 11839132_18 . 
  12. ↑ "إثبات أن وجود مسار هاميلتون في رسم بياني ثنائي الأجزاء هو مسألة NP-كاملة" . موقع Computer Science Stack Exchange . تم الاطلاع عليه بتاريخ 18 مارس 2019 .
  13. ↑ غاري، إم آر ؛ جونسون، دي إس ؛ ستوكمير، إل. (1974)، "بعض مسائل NP-كاملة مبسطة"، وقائع الندوة السادسة لجمعية ACM حول نظرية الحوسبة (STOC '74) ، الصفحات 47-63 ، doi : 10.1145/800119.803884 ، S2CID 207693360  .
  14. ↑ بليسنيك، ج. (1979)، "اكتمال NP لمسألة دورة هاميلتون في الرسوم البيانية الموجهة المستوية ذات درجة حدية اثنين" (ملف PDF) ، رسائل معالجة المعلومات ، 8 (4): 199-201 ، doi : 10.1016/0020-0190(79)90023-1.
  15. ↑ أكياما، تاكانوري؛ نيشيزيكي، تاكاو ؛ سايتو، نوبوجي (1980-1981)، "اكتمال NP لمسألة دورة هاميلتون للرسوم البيانية ثنائية الأجزاء"، مجلة معالجة المعلومات ، 3 (2): 73-76 ، MR 0596313 .
  16. ↑ إيتاي، ألون؛ باباديميتريو، كريستوس؛ شوارزفيتر، جايمي (1982)، "مسارات هاميلتون في الرسوم البيانية الشبكية"، مجلة SIAM للحوسبة ، 4 (11): 676-686 ، CiteSeerX 10.1.1.383.1078 ، doi : 10.1137/0211056 .
  17. ↑ بورو، مايكل (2001)، "نهايات ألعاب أمازون البسيطة وعلاقتها بدوائر هاميلتون في الرسوم البيانية المكعبة الفرعية" (ملف PDF) ، الحوسبة والألعاب ، سلسلة محاضرات في علوم الحاسوب، المجلد 2063، الصفحات 250-261 ، CiteSeerX 10.1.1.40.9731 ، doi : 10.1007/3-540-45579-5_17 ، ISBN    978-3-540-43080-3.
  18. ↑ تشيبا، نوريشيغي؛ نيشيزيكي، تاكاو (1989)، "مسألة دورة هاميلتون قابلة للحل في زمن خطي للرسوم البيانية المستوية ذات الاتصال الرباعي"، مجلة الخوارزميات ، 10 (2): 187-211 ، doi : 10.1016/0196-6774(89)90012-6
  19. ↑ شميد، أندرياس؛ شميدت، ينس م. (2018)، "حساب مسارات Tutte"، وقائع الندوة الدولية الخامسة والأربعين حول الأوتوماتا واللغات والبرمجة (ICALP'18)، سيتم نشرها.
  20. ↑ توماسون، أ. ج. (1978)، "دورات هاميلتون والرسوم البيانية ذات التلوين الفريد للحواف"، التقدم في نظرية الرسوم البيانية (مؤتمر كامبريدج التوافقي، كلية ترينيتي، كامبريدج، 1977) ، حوليات الرياضيات المتقطعة، المجلد 3، الصفحات 259-268 ، doi : 10.1016/S0167-5060(08)70511-9 ، ISBN   9780720408430، MR 0499124 .
  21. ↑ باباديميتريو، كريستوس هـ. (1994)، "حول تعقيد حجة التكافؤ وغيرها من البراهين غير الفعالة للوجود"، مجلة علوم الحاسوب والأنظمة ، 48 (3): 498-532 ، CiteSeerX 10.1.1.321.7008 ، doi : 10.1016/S0022-0000(05)80063-7 ، MR 1279412  .
  22. 1 2 3 بون، مارك (نوفمبر 2022). "نظرية الحوسبة بجامعة بوسطن" (PDF) .
  23. ↑ بريتشر، أ (5 فبراير 2021). "ملاحظات محاضرة الأسبوع 7 من مقرر CSCC63 بجامعة تورنتو" (ملف PDF) .
  24. ↑ بان، جون هو. "نظرة عامة على الشبكة على الشريحة" . جامعة كاليفورنيا إرفاين .
  25. ↑ ساتيش، إي جي (2022). "تحليل مقارن لأداء طوبولوجيا التوجيه لبنية الشبكة على رقاقة" . البحوث الناشئة في الحوسبة والمعلومات والاتصالات والتطبيقات . سلسلة محاضرات في الهندسة الكهربائية. المجلد 790. الصفحات 431-440 . doi : 10.1007/978-981-16-1342-5_34 . ISBN   978-981-16-1341-8– عبر سبرينغر.
  26. ↑ بحربار، ب.؛ ستروباندت ، د. (2014). "تحسين طرق التوجيه القائمة على الهاميلتوني للشبكات على الرقاقة: نهج نموذج الدوران". مؤتمر ومعرض التصميم والأتمتة والاختبار في أوروبا 2014 : 1-4 - عبر IEEE.
  27. ↑ غارسيل، تالي؛ أيريش، بول (5 أغسطس 2011). "كيف تعمل المتصفحات" .
  28. ↑ أركين، إستر م.؛ ميتشل، جوزيف إس بي؛ هيلد، مارتن؛ سكينا، ستيفن إس. "التثليثات الهاميلتونية للعرض السريع" (ملف PDF) . قسم علوم الحاسوب، جامعة ستوني بروك .