Hamiltonian Path Checker คืออะไร?

คือเครื่องตรวจสอบเส้นทางฮามิลตัน ซึ่งเป็นเครื่องมือออนไลน์สำหรับวิเคราะห์กราฟและค้นหาเส้นทางหรือวัฏจักรที่ครอบคลุมทุกจุดยอด

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

ตรวจสอบว่ากราฟมีเส้นทางฮามิลตัน (Hamiltonian path) หรือรอบฮามิลตัน (Hamiltonian cycle) หรือไม่ โดยใช้การย้อนรอย (Backtracking) ร่วมกับการตัดกิ่งแบบ Warnsdorff, ตรวจสอบเงื่อนไขเบื้องต้นของการเชื่อมต่อและดีกรี, ทดสอบเงื่อนไขที่เพียงพอของ Dirac และ Ore และแสดงเส้นทางตัวอย่างด้วยภาพ SVG แบบเคลื่อนไหว

ตัวอย่างด่วน:

K4 ลบหนึ่งขอบ 5-วัฏจักร เส้นทางเชิงเส้น กราฟปีเตอร์เซน วัฏจักรมีทิศทาง เมทริกซ์ 4×4

↔ รายการขอบ ▦ เมทริกซ์ประชิด

ข้อมูลกราฟ

รองรับ A-B, A->B, A B, A,B, หรือแถวเมทริกซ์เช่น 0 1 1 0 ใช้ตัวอักษร, ตัวเลข, หรือเครื่องหมายขีดล่างสำหรับชื่อโหนด

ชื่อจุดยอดของเมทริกซ์ (ไม่บังคับ)

คั่นชื่อด้วยจุลภาคหรือเว้นวรรค หนึ่งชื่อต่อหนึ่งแถว หากละไว้จะใช้ A, B, C… โดยอัตโนมัติ

สิ่งที่ต้องการตรวจสอบ

ประเภทกราฟ

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

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

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

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

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

เส้นทางฮามิลตัน: v1 — v2 — v3 — … — vn (ทุกจุดแตกต่างกัน, แต่ละคู่ที่ติดกันเป็นขอบ) วัฏจักรฮามิลตัน: v1 — v2 — v3 — … — vn — v1 (ปิดวงกลับไปที่จุดเริ่มต้น)

ปัญหานี้ตั้งชื่อตาม 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 จะมีวัฏจักรฮามิลตัน

δ(G) ≥ n / 2 ⟹ G มีวัฏจักรฮามิลตัน

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

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

∀ u, v ที่ไม่ประชิดกัน: deg(u) + deg(v) ≥ n ⟹ G มีวัฏจักรฮามิลตัน

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

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

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

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

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

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

คุณสมบัติ	เส้นทาง / วัฏจักรฮามิลตัน	รอยเดิน / วงจรออยเลอร์
ไปเยือนแต่ละ…	จุดยอดเพียงครั้งเดียวพอดี	ขอบเพียงครั้งเดียวพอดี
ความซับซ้อน	NP-complete	พหุนาม (O(n+m))
เงื่อนไข	ไม่มีลักษณะเฉพาะที่เรียบง่าย	เชื่อมต่อกัน + ทุกจุดยอดมีระดับขั้นเป็นคู่ (สำหรับวงจร)
ตั้งชื่อตาม	W. R. Hamilton (1857)	L. Euler (1736, สะพานเคอนิชส์แบร์ค)
ตัวอย่างคลาสสิก	ปัญหาพนักงานขายเดินทาง, เกม Icosian	การตรวจตราเส้นทาง, ปัญหาบุรุษไปรษณีย์

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

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

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

A-B, B-C, C-D, D-A, A-C (กราฟไม่มีทิศทางที่มี 5 ขอบ) A->B, B->C, C->D, D->A (4-วัฏจักรแบบมีทิศทาง)

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

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

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

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

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

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

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

1-2, 2-3, 3-4, 4-5, 5-1, 6-8, 8-10, 10-7, 7-9, 9-6, 1-6, 2-7, 3-8, 4-9, 5-10

เครื่องตรวจสอบจะยืนยันว่า: พบเส้นทางฮามิลตัน (เช่น 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 ซึ่งยากกว่าปัญหาการตัดสินใจมาก สำหรับการแจกแจงจำนวนเส้นทาง ควรใช้เครื่องมือเฉพาะทางหรือโปรแกรมแก้ปัญหาการโปรแกรมเชิงจำนวนเต็ม