مدقق مسار هاملتون — أوجد مسارًا يزور كل عقدة مرة واحدة بالضبط
يبحث مدقق مسار هاملتون الخاص بنا عن مسار عبر رسم بياني يزور كل عقدة مرة واحدة بالضبط، بتجربة كل عقدة بداية ممكنة والتراجع عبر المسارات الممكنة، مع إدخال رسمك البياني كقائمة حواف نصية بسيطة (مثل A-B, B-C, C-D).
إجابة سريعة
أدخل رسمك البياني كقائمة حواف (حتى 10 عقد) للبحث فورًا عن مسار هاملتون — طريق يزور كل عقدة مرة واحدة بالضبط — عبر التراجع.
أدخل حوافًا بصيغة عقدةA-عقدةB، مثل A-B, B-C, C-D. حتى 10 عقد.
كيفية استخدام مدقق مسار هاملتون — زر كل عقدة مرة واحدة عبر الإنترنت
- 1
أدخل رسمك البياني كقائمة حواف مفصولة بفواصل، مثل A-B, B-C, C-D.
- 2
انقر على 'احسب' للبحث عن مسار هاملتون.
- 3
راجع المسار الموجود، أو تأكيد عدم وجود أي مسار.
لماذا تستخدم مدقق مسار هاملتون — زر كل عقدة مرة واحدة عبر الإنترنت؟
يزور مسار هاملتون كل رأس في رسم بياني مرة واحدة بالضبط — بخلاف مسار أويلر، الذي يتعلق بزيارة كل حافة، يتعلق هذا بزيارة كل عقدة. تحديد ما إذا كان أحدها موجودًا هو مسألة NP-كاملة بشكل عام، مما يعني عدم وجود خوارزمية معروفة أسرع بشكل كبير من تجربة الاحتمالات بشكل منهجي، لذا تستخدم هذه الآلة الحاسبة بحث التراجع: ابنِ مسارًا عقدة واحدة في كل مرة، وتراجع كلما وصلت إلى طريق مسدود، مع تجربة كل عقدة بداية ممكنة. نظرًا لأن مساحة البحث تنمو بشكل عاملي مع حجم الرسم البياني، فإن هذه الآلة الحاسبة محدودة عمدًا بحد أقصى 10 عقد، حيث لا يزال البحث الشامل بالتراجع يكتمل فورًا.
الأسئلة الشائعة
أدوات ذات صلة
حلّال مشكلة البائع المتجول — برمجة ديناميكية دقيقة بخوارزمية Held-Karp عبر الإنترنت
أوجد طريق الذهاب والعودة الأقصر الدقيق الذي يزور كل مدينة مرة واحدة بالضبط، باستخدام خوارزمية البرمجة الديناميكية Held-Karp. آلة حاسبة مجانية، حتى 12 مدينة.
آلة حاسبة الترتيب الطوبولوجي — خوارزمية Kahn عبر الإنترنت
أوجد ترتيبًا طوبولوجيًا صالحًا لرسم بياني موجه باستخدام خوارزمية Kahn، أو اكتشف عدم وجود ترتيب بسبب دورة. آلة حاسبة مجانية بإدخال قائمة حواف بسيط.
آلة حاسبة الشجرة الممتدة الصغرى — خوارزمية كروسكال عبر الإنترنت
أوجد الشجرة الممتدة الصغرى لرسم بياني موزون باستخدام خوارزمية كروسكال. آلة حاسبة مجانية بإدخال بسيط لقائمة الحواف واكتشاف الدورات عبر Union-Find.