ما هو مثال على خوارزمية مونت كارلو لإيجاد مسار هاميلتون؟

Question

لقد أدرك مؤخرا أنه توجد خوارزمية (خوارزمية) مونتي كارلو لتحديد ما إذا كان مسار هاميلتون موجود في رسم بياني.أنا تكافح لمعرفة كيف ستعمل.ما هو العنصر العشوائي؟

Answer 1

هناك العديد من الخوارزميات لمشاكل الرسم البياني المختلفة؛بالنسبة لمسار هاميلتون، يمثل مثال واحد إلى Björklund [1].غالبا ما تكون هذه الخوارزميات جبرية و "العنصر العشوائي" ينبع من تطبيق Schwartz-Zippel Lemma .عادة، تعمل الخوارزميات بحيث تكون خاصية الرسم البياني المهتمين بما يتم تمثيله بطريقة أو بأخرى كأحد متعدد الحدود (متعدد المتغيرات) بممتلكات أن الحل على وجه التحديد عندما لا يكون متعدد الحدود صفريا.

---

[1] björklund، andreas."المبالغ المحددة لهما هاميلتون غير المعردة".سيام مجلة على الحوسبة 43.1 (2014): 280-299.