เครื่องตรวจสอบเส้นทางฮามิลตัน

เกี่ยวกับ เครื่องตรวจสอบเส้นทางฮามิลตัน

เครื่องตรวจสอบเส้นทางฮามิลตัน จะตัดสินว่ากราฟประกอบด้วย เส้นทางฮามิลตัน (ลำดับที่ไปเยือนทุกจุดยอดเพียงหนึ่งครั้ง) หรือ วัฏจักรฮามิลตัน (ซึ่งย้อนกลับไปยังจุดยอดเริ่มต้นเพิ่มเติม) เครื่องมือนี้รวมการตรวจสอบโครงสร้างเบื้องต้นที่รวดเร็ว (ความเชื่อมโยง, เงื่อนไขระดับขั้น, ทฤษฎีบทของ Dirac, ทฤษฎีบทของ Ore) เข้ากับการค้นหาแบบย้อนรอยที่ปรับแต่งโดยฮิวริสติกของ Warnsdorff และแสดงภาพเส้นทางพยานด้วยแอนิเมชันทีละขั้นตอน

เส้นทางฮามิลตันคืออะไร?

กำหนดให้กราฟ G = (V, E) ที่มีจุดยอด n จุด เส้นทางฮามิลตัน คือลำดับของจุดยอด v₁, v₂, …, v_n ทั้งหมด โดยที่คู่ที่อยู่ติดกันแต่ละคู่ (v_i, v_i+1) เป็นขอบของ G และทุกจุดยอดปรากฏเพียงครั้งเดียวเท่านั้น หากเพิ่มเติมว่า (v_n, v₁) เป็นขอบด้วย ลำดับนั้นจะเป็น วัฏจักรฮามิลตัน

ปัญหานี้ตั้งชื่อตาม William Rowan Hamilton ซึ่งในปี 1857 ได้คิดค้นเกม Icosian game ซึ่งเป็นปริศนาที่ให้ผู้เล่นค้นหาวัฏจักรที่ไปเยือนทุกจุดยอดของกราฟทรงสิบสองหน้าปกติเพียงครั้งเดียวพอดี

ทำไมมันจึงยาก: ความซับซ้อนแบบ NP-Completeness

ทั้งปัญหาการตัดสินใจเรื่องเส้นทางฮามิลตันและวัฏจักรฮามิลตันเป็นปัญหา NP-complete (Karp, 1972) เว้นแต่ว่า P = NP ก็จะไม่มีอัลกอริทึมเวลาพหุนามที่แก้ปัญหานี้ได้ทุกกรณี ในกรณีที่เลวร้ายที่สุด การย้อนรอยจะสำรวจต้นไม้การค้นหาที่มีขนาดสูงสุดถึง (n−1)! สำหรับวัฏจักร นี่คือเหตุผลที่เครื่องคิดเลขจำกัดข้อมูลเข้าไว้ที่ 20 จุดยอด เนื่องจากการเพิ่ม n เพียงเล็กน้อยจะทำให้เวลาในการรันเพิ่มขึ้นอย่างมหาศาล

ในทางปฏิบัติ ฮิวริสติกของ Warnsdorff (เดิมถูกคิดค้นโดย Heinrich Warnsdorff ในปี 1823 สำหรับปัญหาการเดินของอัศวิน) ช่วยให้การค้นหาทำได้เร็วขึ้นอย่างมากในกราฟที่มีโครงสร้าง: ในแต่ละขั้นตอน อัลกอริทึมจะขยายเส้นทางปัจจุบันไปยังเพื่อนบ้านที่ยังไม่ถูกเยือนที่มีจำนวนเพื่อนบ้านที่ยังไม่ถูกเยือน น้อยที่สุด กฎแบบละโมบนี้ช่วยป้องกันไม่ให้การค้นหาติดมุม และมักจะพบเส้นทางฮามิลตันโดยไม่ต้องย้อนรอยเลยในกราฟที่เหมาะสม

เงื่อนไขที่จำเป็น — การปฏิเสธอย่างรวดเร็ว

ก่อนที่จะรันการค้นหาที่มีค่าใช้จ่ายสูง เครื่องคิดเลขจะปฏิเสธกราฟที่ไม่สามารถมีเส้นทางฮามิลตันได้อย่างแน่นอน:

• ความเชื่อมโยง (Connectivity) เส้นทางฮามิลตันต้องไปเยือนทุกจุดยอด ดังนั้นกราฟต้องมีส่วนประกอบที่เชื่อมกันเพียงส่วนเดียว สำหรับกราฟแบบมีทิศทาง จำเป็นต้องมีความเชื่อมโยงแบบอ่อน (ละทิ้งทิศทางลูกศร)
• ระดับขั้น (กราฟไม่มีทิศทาง) มีจุดยอดสูงสุดเพียงสองจุดเท่านั้นที่มีระดับขั้นเป็น 1 ซึ่งเป็นจุดเริ่มต้นและจุดสิ้นสุดของเส้นทาง สำหรับ วัฏจักร ฮามิลตัน ทุกจุดยอดต้องมีระดับขั้นอย่างน้อย 2
• ระดับขั้น (กราฟมีทิศทาง) สำหรับเส้นทางฮามิลตัน จะมีจุดยอดสูงสุดหนึ่งจุดที่มีระดับขั้นเข้าเป็น 0 (จุดเริ่ม) และสูงสุดหนึ่งจุดที่มีระดับขั้นออกเป็น 0 (จุดจบ) สำหรับวัฏจักรฮามิลตัน ทุกจุดยอดต้องมีระดับขั้นเข้า ≥ 1 และระดับขั้นออก ≥ 1

กฎเหล่านี้จะปฏิเสธข้อมูลนำเข้าที่ไม่มีความหวังในเวลาเชิงเส้น ช่วยหลีกเลี่ยงความพยายามในการย้อนรอยที่สูญเปล่า

เงื่อนไขที่เพียงพอ — ทฤษฎีบทคลาสสิก

ทฤษฎีบทคลาสสิกหลายบทให้เงื่อนไขที่ เพียงพอ (แต่ไม่จำเป็น) ซึ่งรับประกันว่าจะมีวัฏจักรฮามิลตันในกราฟไม่มีทิศทางเชิงเดี่ยว หากเงื่อนไขใดเหล่านี้ใช้ได้ เครื่องคิดเลขจะระบุผลลัพธ์ว่า "การันตีว่ามี" โดยไม่ต้องรันการค้นหา (แม้ว่าจะยังแสดงวัฏจักรพยานให้เห็นก็ตาม)

ทฤษฎีบทของ Dirac (1952)

หาก G เป็นกราฟไม่มีทิศทางเชิงเดี่ยวที่มีจุดยอด n ≥ 3 และทุกจุดยอดมีระดับขั้นอย่างน้อย n / 2 กราฟ G จะมีวัฏจักรฮามิลตัน

ทฤษฎีบทของ Ore (1960)

หากทุกคู่ของจุดยอดที่ไม่ประชิดกัน u และ v มีผลรวม deg(u) + deg(v) ≥ n กราฟ G จะมีวัฏจักรฮามิลตัน เงื่อนไขของ Ore นั้นกว้างกว่าของ Dirac ดังนั้น Ore จึงครอบคลุม Dirac

การไม่ผ่านเงื่อนไขของ Dirac หรือ Ore ไม่ได้ หมายความว่ากราฟนั้นไม่มีวัฏจักรฮามิลตัน กราฟจำนวนมากไม่ผ่านเกณฑ์ทั้งสองแต่ยังคงมีวัฏจักร (เช่น วัฏจักร n เชิงเดี่ยวจะมีระดับขั้นต่ำสุดเป็น 2 ซึ่งต่ำกว่า n/2 มากเมื่อ n มีค่ามาก)

อัลกอริทึมการค้นหาภายใน

เมื่อการตรวจสอบเบื้องต้นไม่สามารถสรุปผลได้ เครื่องคิดเลขจะรันการค้นหาแบบย้อนรอยบนตัวแทนประชิดของกราฟ กลยุทธ์สำคัญ:

1. Bitmask visited-set ชุดของจุดยอดที่ไปเยือนแล้วจะถูกเก็บเป็น Bitmask (การทดสอบสมาชิก O(1) ที่รวดเร็วสำหรับจุดยอดสูงสุด 20 จุด)
2. Warnsdorff heuristic ในการขยายเส้นทางแต่ละครั้ง จะลองไปที่เพื่อนบ้านตามลำดับระดับขั้นที่ยังไม่เยือน (น้อยที่สุดก่อน) ซึ่งเลียนแบบลำดับที่มีกิ่งน้อย
3. การเลือกราก (Root selection) สำหรับ วัฏจักร ฮามิลตัน ต้องการจุดยอดเริ่มต้นเพียงจุดเดียว (วัฏจักรมีสมบัติไม่เปลี่ยนตามการหมุน) สำหรับ เส้นทาง ฮามิลตัน จะลองเริ่มจากจุดยอดตามลำดับระดับขั้นออกแบบน้อยไปหามาก
4. งบประมาณขั้นตอน มีการจำกัดจำนวนขั้นตอนเพื่อป้องกันไม่ให้บางกรณีรันไปอย่างไม่มีที่สิ้นสุด โดย UI จะรายงานผลเป็น "หมดเวลา" หากใช้งบประมาณจนหมด

ฮามิลตัน vs ออยเลอร์

มันง่ายที่จะสับสนระหว่างปัญหาฮามิลตันและออยเลอร์ — พวกมันฟังดูคล้ายกันแต่แตกต่างกันโดยพื้นฐาน:

รูปแบบการนำเข้าที่รองรับ

รายการขอบ (Edge list)

หนึ่งขอบต่อหนึ่งบรรทัด หรือคั่นด้วยจุลภาค ตัวคั่นที่รองรับ: A-B, A B, A,B, A--B, A->B, A<-B ใช้ -> เพื่อบังคับให้ตีความแบบมีทิศทาง

เมทริกซ์ประชิด (Adjacency matrix)

เมทริกซ์จัตุรัสที่มีค่า 0/1 หนึ่งแถวต่อหนึ่งบรรทัด คั่นด้วยช่องว่างหรือจุลภาค สามารถใส่ชื่อโหนดในช่อง "ชื่อจุดยอดของเมทริกซ์" ได้ มิเช่นนั้นจะใช้ A, B, C… โดยอัตโนมัติ

วิธีใช้งานเครื่องตรวจสอบนี้

1. เลือกรูปแบบการนำเข้า — รายการขอบสำหรับกราฟขนาดเล็กที่เขียนเอง, เมทริกซ์ประชิดสำหรับการวางข้อมูลจากโค้ดหรือตำราเรียน
2. วางกราฟของคุณ ในพื้นที่ข้อความ สำหรับการนำเข้าแบบเมทริกซ์ สามารถระบุชื่อจุดยอดได้ตามต้องการ
3. เลือกสิ่งที่ต้องการตรวจสอบ: เฉพาะเส้นทาง, เฉพาะวัฏจักร หรือทั้งคู่ในการรันครั้งเดียว
4. เลือกประเภทกราฟ — การตรวจจับอัตโนมัติจะประเมินทิศทางจากรูปแบบลูกศร (->) หรือความสมมาตรของเมทริกซ์
5. คลิก ตรวจสอบฮามิลตัน หน้าผลลัพธ์จะแสดงคำตัดสิน, การตรวจสอบเงื่อนไขที่จำเป็น, การทดสอบเงื่อนไขของ Dirac / Ore, เส้นทางพยาน (หากมี) และการแสดงภาพแบบโต้ตอบ
6. เล่นซ้ำพยาน โดยใช้ปุ่ม เล่น / เลื่อน สังเกตเส้นทางที่จะสว่างขึ้นทีละขอบบนกราฟ

ตัวอย่างที่ใช้งานจริง — กราฟปีเตอร์เซน

กราฟปีเตอร์เซน (Petersen graph) ที่มีชื่อเสียง (10 จุดยอด, 15 ขอบ, ระดับขั้นเป็น 3 ทุกจุด) เป็นตัวอย่างในตำราเรียนของกราฟที่มีเส้นทางฮามิลตันแต่ ไม่มี วัฏจักรฮามิลตัน วางข้อมูลนี้ลงในช่องรายการขอบแล้วคลิกตรวจสอบ:

เครื่องตรวจสอบจะยืนยันว่า: พบเส้นทางฮามิลตัน (เช่น 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3) แต่การค้นหาอย่างละเอียดไม่พบวิธีปิดวงกลับไปยังจุดเริ่มต้น ซึ่งเป็นผลลัพธ์ที่พิสูจน์ครั้งแรกในช่วงทศวรรษที่ 1890

การประยุกต์ใช้ทั่วไป

• การจัดเส้นทางและปัญหาพนักงานขายเดินทาง — ทุกเส้นทาง TSP คือวัฏจักรฮามิลตันในกราฟถ่วงน้ำหนักแบบสมบูรณ์
• การประกอบจีโนม — การสร้างลำดับ DNA ใหม่จากการอ่านที่ซ้อนทับกันสามารถจำลองเป็นเส้นทางฮามิลตันในกราฟการซ้อนทับ
• การวางผังวงจร — การจัดลำดับพินบน PCB เพื่อให้มีการเดินสายที่สั้นที่สุด
• AI ของเกมและการแก้ปริศนา — การเดินของอัศวินบนกระดานหมากรุก, เกม Icosian
• การจัดตารางเวลา — การจัดลำดับงานเพื่อให้การเปลี่ยนผ่านจากงานหนึ่งไปอีกงานหนึ่งเป็นไปได้อย่างราบรื่น
• การสอนคณิตศาสตร์เชิงจัดกลุ่ม — การแสดงตัวอย่าง NP-completeness ด้วยกรณีศึกษาขนาดเล็กที่แก้ได้ด้วยมือ

คำถามที่พบบ่อย

เส้นทางฮามิลตันคืออะไร?

เส้นทางฮามิลตันคือการเดินผ่านกราฟที่ไปเยือนทุกจุดยอดเพียงครั้งเดียวเท่านั้น ตั้งชื่อตาม William Rowan Hamilton ผู้ศึกษาปัญหานี้บนกราฟทรงสิบสองหน้าในปี 1857 การตัดสินว่ามีเส้นทางดังกล่าวหรือไม่เป็นปัญหา NP-complete ดังนั้นจึงไม่มีอัลกอริทึมที่รู้จักซึ่งสามารถแก้ปัญหานี้ได้ในเวลาพหุนามสำหรับกราฟทั้งหมด

วัฏจักรฮามิลตันต่างจากเส้นทางฮามิลตันอย่างไร?

วัฏจักรฮามิลตันคือเส้นทางฮามิลตันที่ย้อนกลับไปยังจุดยอดเริ่มต้น เกิดเป็นวงปิดที่ไปเยือนทุกจุดยอดเพียงครั้งเดียว ทุกวัฏจักรฮามิลตันประกอบด้วยเส้นทางฮามิลตัน (เพียงแค่ตัดขอบปิดทิ้ง) แต่ในทางกลับกันไม่เสมอไป: กราฟจำนวนมากมีเส้นทางฮามิลตันแต่ไม่มีวัฏจักรฮามิลตัน

ทฤษฎีบทของ Dirac กล่าวว่าอย่างไร?

ทฤษฎีบทของ Dirac (1952) ระบุว่ากราฟไม่มีทิศทางเชิงเดี่ยวใดๆ ที่มีจุดยอด n ≥ 3 ซึ่งทุกจุดยอดมีระดับขั้นอย่างน้อย n/2 จะมีวัฏจักรฮามิลตัน มันเป็นเงื่อนไขที่เพียงพอแต่ไม่จำเป็น: กราฟหลายอันที่ไม่ผ่านเกณฑ์ของ Dirac ยังคงมีวัฏจักรฮามิลตันได้

ทฤษฎีบทของ Ore กล่าวว่าอย่างไร?

ทฤษฎีบทของ Ore (1960) ระบุว่าหากทุกคู่ของจุดยอดที่ไม่ประชิดกัน u และ v ในกราฟเชิงเดี่ยวที่มีจุดยอด n ≥ 3 ผลรวมของระดับขั้นของพวกมันมีค่าอย่างน้อย n กราฟนั้นจะมีวัฏจักรฮามิลตัน เงื่อนไขของ Ore นั้นกว้างกว่าของ Dirac ดังนั้นทฤษฎีบทของ Ore จึงใช้ได้เสมอเมื่อทฤษฎีบทของ Dirac ใช้ได้

ทำไมการค้นหาจึงจำกัดอยู่ที่ 20 จุดยอด?

ปัญหาการตัดสินใจเรื่องเส้นทางและวัฏจักรฮามิลตันเป็นปัญหา NP-complete เวลาในการรันกรณีแย่ที่สุดจะเพิ่มขึ้นแบบเอกซ์โพเนนเชียลตามจำนวนจุดยอด ด้วยการตัดกิ่งและฮิวริสติก Warnsdorff เครื่องคิดเลขสามารถจัดการกราฟขนาดเล็กจำนวนมากได้ถึง 20 จุดยอดอย่างรวดเร็ว แต่อินสแตนซ์ที่ยากกว่าอาจหมดเวลา เกินกว่า 20 จุดยอด คุณควรใช้โปรแกรมแก้ปัญหาเฉพาะทาง เช่น Concorde หรือการกำหนดปัญหาแบบจำนวนเต็ม

ฮิวริสติกของ Warnsdorff คืออะไร?

กฎของ Warnsdorff เสนอขึ้นในปี 1823 สำหรับปัญหาการเดินของอัศวิน กล่าวว่าในแต่ละขั้นตอนคุณควรไปเยือนจุดยอดถัดไปที่มีเพื่อนบ้านที่ยังไม่ได้เยี่ยมชมน้อยที่สุด กฎที่ดูเหมือนแบบละโมบนี้ช่วยตัดกิ่งต้นไม้การย้อนรอยได้อย่างมหาศาลในทางปฏิบัติ และมักจะพบเส้นทางฮามิลตันโดยไม่ต้องย้อนรอยเลยในกราฟปกติ

เครื่องมือนี้สามารถหาเส้นทางฮามิลตันทั้งหมดได้หรือไม่?

ไม่ — เครื่องมือนี้จะค้นหาเส้นทางหรือวัฏจักรพยานเพียงหนึ่งเส้นทางเมื่อมีอยู่จริง การนับจำนวนเส้นทางฮามิลตันทั้งหมดเป็นปัญหาแบบ #P-complete ซึ่งยากกว่าปัญหาการตัดสินใจมาก สำหรับการแจกแจงจำนวนเส้นทาง ควรใช้เครื่องมือเฉพาะทางหรือโปรแกรมแก้ปัญหาการโปรแกรมเชิงจำนวนเต็ม

อ่านเพิ่มเติม

• Hamiltonian path — Wikipedia
• Hamiltonian path problem — Wikipedia
• Dirac's theorem on Hamiltonian cycles — Wikipedia
• Ore's theorem — Wikipedia
• Warnsdorff's rule — Wikipedia

การดำเนินการทางคณิตศาสตร์ขั้นสูง:

• เครื่องคิดเลข Antilog
• เครื่องคิดเลขฟังก์ชันเบต้า
• เครื่องคิดเลขสัมประสิทธิ์ทวินาม
• เครื่องคำนวณการแจกแจงแบบทวินาม
• เครื่องคิดเลขบิต
• เครื่องคำนวณทฤษฎีบทขีดจำกัดกลาง
• เครื่องคิดเลขรวม
• เครื่องคิดเลขฟังก์ชันข้อผิดพลาดเสริม
• เครื่องคิดเลขจำนวนเชิงซ้อน
• เครื่องคำนวณเอนโทรปี
• เครื่องคิดเลขฟังก์ชันผิดพลาด
• เครื่องคำนวณการสลายตัวแบบเอกซ์โพเนนเชียล
• เครื่องคำนวณการเติบโตแบบทวีคูณ ความแม่นยำสูง
• เครื่องคิดเลขเอกซ์โพเนนเชียลอินทิกรัล
• เครื่องคำนวณเลขยกกำลัง-ความแม่นยำสูง แนะนำ
• เครื่องคำนวณแฟกทอเรียล
• เครื่องคิดเลขฟังก์ชันแกมมา
• เครื่องคำนวณอัตราส่วนทองคำ
• เครื่องคิดเลขครึ่งชีวิต
• เครื่องคำนวณอัตราการเติบโตเป็นเปอร์เซ็นต์
• เครื่องคิดเลขเรียงสับเปลี่ยน
• เครื่องคิดเลขการแจกแจงแบบปัวซง
• เครื่องคำนวณรากของพหุนามพร้อมขั้นตอนละเอียด
• เครื่องคิดเลขความน่าจะเป็น
• เครื่องคิดเลขการแจกแจงความน่าจะเป็น
• เครื่องคำนวณสัดส่วน
• เครื่องคิดเลขสูตรกำลังสอง
• เครื่องคำนวณวิทยาศาสตร์
• เครื่องคิดเลขสัญกรณ์วิทยาศาสตร์
• เครื่องคำนวณเลขนัยสำคัญ ใหม่
• เครื่องคำนวณผลรวมของลูกบาศก์
• เครื่องคิดเลขหาผลรวมของจำนวนเต็มบวก
• ผลรวมของเครองคดเลขกำลงสอง
• เครื่องสร้างตารางค่าความจริง
• เครื่องคิดเลขทฤษฎีเซต
• เครื่องสร้างแผนภาพเวนน์3เซต
• เครื่องคิดเลขทฤษฎีเศษเหลือจีน
• เครื่องคิดเลขฟังก์ชันโทเชียนต์ออยเลอร์
• เครื่องคำนวณอัลกอริทึมยูคลิดขยาย
• เครื่องคำนวณอินเวอร์สการคูณแบบโมดูลาร์
• เครื่องคำนวณเศษส่วนต่อเนื่อง
• เครื่องคำนวณเส้นทางสั้นสุดของไดค์สตรา
• เครื่องคำนวณต้นไม้แผ่ทั่วน้อยสุด
• เครื่องตรวจสอบลำดับดีกรีของกราฟ
• เครื่องคำนวณดีเรนจ์เมนต์ ซับแฟกทอเรียล
• เครื่องคำนวณจำนวนสเตอร์ลิง
• เครื่องคำนวณหลักรังนกพิราบ
• เครื่องคำนวณการแจกแจงนิ่งโซ่มาร์คอฟ
• เครื่องคำนวณการปัดเศษ ใหม่
• เครื่องคำนวณการแจกแจงทวินามลบ ใหม่
• เครื่องคำนวณการเรียงสับเปลี่ยนแบบซ้ำได้ ใหม่
• เครื่องคำนวณเลขชี้กำลังมอดุลาร์ ใหม่
• เครื่องคำนวณรากดั้งเดิม
• ตัวลดรูปพีชคณิตบูลีน ใหม่
• ตัวแก้แผนผังคาร์นอฟ (K-Map Solver) ใหม่
• เครื่องคำนวณการระบายสีกราฟ ใหม่
• เครื่องคำนวณการเรียงลำดับทอพอโลยี ใหม่
• เครื่องคำนวณเมทริกซ์ประชิด ใหม่
• เครื่องคำนวณหลักการรวม-แยก ใหม่
• ตัวแก้ปัญหาโปรแกรมเชิงเส้น ใหม่
• เครื่องแก้ปัญหาพนักงานขายเดินทาง (TSP) ใหม่
• เครื่องตรวจสอบเส้นทางฮามิลตัน ใหม่
• เครื่องตรวจสอบกราฟระนาบ ใหม่
• เครื่องคำนวณการไหลในเครือข่าย (การไหลสูงสุด) ใหม่
• ตัวแก้ปัญหาการจับคู่แต่งงานที่เสถียร ใหม่
• เครื่องคำนวณลำดับทฤษฎีกรุป ใหม่
• เครื่องคำนวณริงและฟิลด์ ใหม่