ผลต่างระหว่างรุ่นของ "ปัญหาทางเดินม้าหมากรุก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
KamikazeBot (คุย | ส่วนร่วม) ล r2.7.1) (โรบอต เพิ่ม: fy:Hynstesprong, nl:Paardensprong |
ไม่มีความย่อการแก้ไข |
||
บรรทัด 1:
[[
[[Image:Knight%27s_tour.svg|right|thumb|250px|ทางเดินม้าหมากรุกเปิด]]
'''ปัญหาทางเดินม้าหมากรุก''' เป็นปัญหาทาง[[คณิตศาสตร์]]เกี่ยวกับการเดิน[[ม้า_(หมากรุก)|ม้า]]ในกระดาน[[หมากรุก]] โดยม้าจะต้องเดินผ่านช่องทุกช่องบนกระดานหมากรุกเพียงช่องละหนึ่งครั้งเท่านั้นและเป็นไปตามกฎกติกาของเกมหมากรุก ถ้าการเดินม้ามีจุดเริ่มต้นเป็นช่องเดียวกับจุดสิ้นสุดจะเรียกการเดินม้านั้นว่า ”การเดินม้าแบบปิด” แต่ถ้าหากเป็นคนละช่องกันจะเรียกการเดินม้านั้นว่า “การเดินม้าแบบเปิด” ซึ่งในปัจจุบันยังไม่ทราบจำนวนวิธีในการเดินม้าแบบเปิดที่แน่ชัด ขนาดของตารางหมากรุกที่ใช้ในปัญหานี้มีหลายขนาด โดยขนาดที่ใช้โดยทั่วไปจะเป็นขนาด 8 x 8 ช่อง
==ทฤษฎีบท==
ปัญหาทางเดินหมากรุกเป็นตัวอย่างหนึ่งของ ปัญหาทางเดินแบบแฮมิลตันในเรื่อง[[ทฤษฎีกราฟ]] และปัญหาในการหาการเดินม้าหมากรุกแบบปิดนับเป็นตัวอย่างที่คล้ายคลึงกับปัญหาวัฏจักรแบบแฮมิลตัน โดยจะมีความแตกต่างจากปัญหาทางเดินแบบแฮมิลตัน คือ ปัญหาการเดินม้าหมากรุกแบบปิดนั้นมี[[ฟังก์ชัน (คณิตศาสตร์)|ฟังก์ชัน]]ของเวลาการทำงานเป็นเชิงเส้น หรือ สามารถบรรยายความสัมพันธ์ของฟังก์ชันในแง่ของอัตราการเติบโตได้ด้วยสัญกรณ์เชิงเส้นกำกับ [[สัญกรณ์โอใหญ่|O(n)]]
==ประวัติความเป็นมา==
ปัญหาทางเดินม้าหมากรุกได้ถูกค้นพบในศตวรรษที่ 9 โดยกวีชาวอินเดียชื่อว่า รุถถะ เขาได้เขียนบทกวีเกี่ยวกับศิลปะ แบบแผนในการเล่นม้าหมากรุกแบบครึ่งกระดานในภาษาสันสกฤต ซึ่งแตกต่างจากกวีอื่นๆที่เขียนไว้ <br />
: ลีออนฮาร์ด ออยเลอร์ เป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่สามารถจับเทคนิคปัญหาทางเดินม้าหมากรุกได้ ซึ่งกล่าวได้ว่าเป็นเทคนิคแรกที่สมบูรณ์แบบ เทคนิคนี้ได้ถูกเขียนเป็นกฏของวานดรอฟและได้รับการเผยแพร่ครั้งแรกในปี ค.ศ.1823 <br />
: ในศตวรรษที่ 20 กลุ่มของนักเขียน นามว่า อูลิโป ได้ใช้กฏนี้ในหลายๆรูปแบบ หนึ่งในบทความที่มีชื่อเสียงคือการเดินม้าหมากรุกบนขนาดตาราง 10x10 ช่อง ซึ่งอยู่ในหนังสือรางวัลโนเวลจอเจิส เพรก และในเกมการแข่งขันหมากรุก ระหว่าง วิสวันทาน เอนาน กับ วีสลิน โทเพลอฟ ในปี ค.ศ.2010 ซึ่งในเกมนี้ วิสวันทาน เอนาน ได้ทำการเดินม้าหมากรุกทั้ง 2 ตัว 13 ครั้งติดต่อกัน ซึ่งผู้บรรยายคิดว่า วิสวันทาน เอนาน นั้นพยายามจะพิสูจน์หรือค้นหาเทคนิคการเดินม้าหมากรุก <br />
==ทางเดินม้าหมากรุกปิด==
ในตารางหมากรุกขนาด 8 × 8 ช่อง มีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ระบุทิศทาง แน่นอน จำนวน 26,534,728,821,064 วิธี <ref>Wegener, I. (January 1, 1987). Branching Programs and Binary Decision Diagrams. Society for Industrial & Applied Mathematics. ISBN 0-89871-458-3</ref> และมีจำนวนวิธีการเดินม้าหมากรุกแบบปิด ไม่ระบุทิศทาง จำนวน 13,267,364,410,532 วิธี <ref>http://books.google.com/books?id=-DZjVz9E4f8C&pg=PA369&dq=532&hl=en#v=onepage&q=532&f=false</ref> ซึ่งมีจำนวนเป็นครึ่งหนึ่งของแบบระบุทิศทาง
และในตารางหมากรุกขนาด 6x6 มี วิธีการเดินม้าหมากรุกแบบปิดซึ่งไม่ระบุทิศทางจำนวน 9,862 วิธี การเดินม้าหมากรุแบบปิดมีกรณีที่เล็กที่สุดคือ กรณี 1 × 1 (เป็นทฤษฎีบทแทรกของทฤษฎีนี้)
=== ทฤษฎีบทของชเวงค์ ===
สำหรับทุกตารางหมากรุกขนาด m × n โดยที่ m น้อยกว่า n แล้วเราจะสามารถหาวิธีการเดินม้าหมากรุกแบบปิดได้ ยกเว้นตารางหมากรุกดังกล่าวจะสอดคล้องกับเงื่อนไขต่อไปนี้อย่างน้อย 1 เงื่อนไข <br />
:# m และ n เป็นจำนวนคี่ทั้งคู่ โดยที่ m≠1 และ n≠1
:# m = 1, 2, หรือ 4 โดยที่ m≠1 และ n≠1
:# m = 3 และ n = 4, 6, หรือ 8<br />
<br />เงื่อนไขที่1
:สาเหตุที่เงื่อนไขนี้ไม่สามารถทำการเดินแบบปิดได้ เนื่องจากจำนวนช่องของสีบนตารางที่ไม่เท่ากัน กล่าวคือ ตารางหมากรุปแบบมาตรฐานจะมีสี 2 สี ได้แก่สีดำและสีขาว ซึ่งม้าหมากรุกสามารถเดินได้ทั้ง 2 สี คือ จากช่องสีดำไปช่องสีขาวและจากช่องสีขาวไปช่องสีดำ แต่ในการเดินแบบปิด ม้าจะต้องเดินบนช่องขาวและช่องดำเป็นจำนวนเท่ากัน และถ้าจำนวน m และ n เป็นจำนานคี่ทั้งคู่ จำนวนช่องทั้งหมดบนตารางหมากรุกจะเป็นเลขคี่ ซึ่งจะมีช่องขาวและช่องดำไม่เท่ากัน ตัวอย่างเช่น ในตารางหมากรุกขนาด 5x5 จะมีสีหนึ่ง 13ช่อง และอีกสีหนึ่ง 12ช่อง สีที่ต่างกันมีจำนวนช่องไม่เท่ากัน ดังนั้นไม่มีวิธีที่จะเดินม้าหมากรุกแบบปิด กรณีนี้จะมีเพียงการเดินม้าแบบเปิดได้เท่านั้น<br />
<br />เงื่อนไขที่ 2
:เมื่อกระดานข้างที่สั้นกว่ามีความกว้างเป็น 1,2 หรือ 4 จะไม่สามารถการเดินแบบปิดได้ และเมื่อ m=1 หรือ 2 จะไม่สามารถเดินแบบปิดได้ เนื่องจากม้าจะไม่สามารถเดินไปในทุกๆช่องได้ (ยกเว้นตารางหมากรุกขนาด 1x1) และเมื่อ m=4 ก็ไม่สามารถเกิดการเดินแบบปิดได้เช่นกัน โดยการพิสูจน์จากสีในตารางหมากรุก<br />
:เริ่มพิสูจน์โดยการสมมุติให้ตาราง 4xn สามารถเดินม้าแบบปิดได้ และให้ A1 เป็นเช็ตของช่องสีดำและ A2 เป็นเช็ตของช่องสีขาว แล้วถ้ามีช่องสีขาวและช่องสีดำ สลับกันบนกระดานหมากรุก พิจารณาจากรูปทางด้านขวา กำหนดให้ B1 เป็นเช็ตของช่องสีเขียวและ B2 เป็นเช็ตของช่องสีแดง จากรูปทางด้านขวาจะสังเกตุได้ว่าจำนวนของช่องสีเขียวและสีแดงมีจำนวนเท่ากัน และสมมุติให้ม้าเดินจากช่องใน B1 ม้าจะต้องเดินไปช่องใน B2 และม้าจะต้องเดินบนทุกๆช่อง โดยจะเดินไม่ซ้ำช่องกัน และเมื่อม้าอยู่บนช่อง B2 ม้าจะต้องเดินไปในช่องของ B1 ต่อไป (ในทางกลับกัน ม้าต้องเดินไปบนช่อง B1 สองครั้งในภายหลัง)
:ถ้าเราปฏิบัติตามการสมมุติข้างต้นเราจะพบข้อขัดแย้งดังนี้
:
:# การเดินครั้งแรก ม้าจะเดินไปในช่องของ A1 และ B1 ถ้าไม่ได้เดินแบบนี้ เราสามารถเปลี่ยนเป็น B1 และ B2 ก็จะถูกเช่นเดียวกัน
:# การเดินครั้งที่ 2 จะเป็นสมาชิกในเช็ตของ A2 และ B2.
:# การเดินครั้งที่ 3 จะเป็นสมาชิกในเช็ตของ A1 และ B1.
:# การเดินครั้งที่ 4 จะเป็นสมาชิกในเช็ตของ A2 และ B2.
:# และอีกมากมาย<br />
:ดังนั้นเช็ต A1 จะมี สมาชิกเหมือนเช็ต B1 และเช็ต A2 มีสมาชิกเหมือนเช็ต B2 แต่ว่า การสรุปข้างต้นนั้นไม่ถูกต้องเสมอไป ถ้าสีแดงและสีเขียวจากรูปด้านบน ไม่เหมือนกระดานหมากรุก เช็ตของสีแดงจะไม่เหมือนเช็ตของสีดำ<br />
ดังนั้นเราสามารถสรุปได้ว่าไม่สามารถเดินม้าแบบปิดในตาราง 4xn ได้ สำหรับ ทุกๆค่าของ n<br />
<br />เงื่อนไขที่ 3
:เงื่อนไขนี้สามารถพิสูจน์ได้จากการแตกเป็นหลายๆวิธี และการสร้างการเดินแบบแบบปิด โดยใช้ตารางแบบ 3xn (n=4,6,8) จะไม่สามารถทำได้ ตารางหมากรุกแบบ 3xn โดย n เป็นจำนวนคู่และมีค่ามากกว่า 8 จะสามารถเกิดการเดินแบบปิดได้โดยอุปนัย<br />
<br />เงื่อนไขอื่นๆ
:การพิสูจน์อย่างง่ายจากเงื่อนไข 3 ทั้งข้อที่กล่าวข้างต้น ไม่สามารถพิสูจน์ทฤษฎีทั้งหมดได้ การพิสูจน์ทฤษฎีนี้ยังคง ต้องการกระดานแบบสี่เหลี่ยมผืนผ้า ที่ไม่ได้ซ้ำในเงื่อนไข 3 ข้อด้านบน จึงจะทำให้เกิดการเดินแบบปิดได้<br />
== ขั้นตอนวิธีทางคอมพิวเตอร์ ==
ในการหาวิธีการเดินม้าหมากรุกนั้นนอกจากขั้นตอนวิธีแบบลุยทุกรูปแบบ (ซึ่งจะใช้เวลาในการทำงานนานมาก ไม่เหมาะสมอย่างยิ่งหากจะนำมาใช้กับตารางขนาดใหญ่) ยังมีขั้นตอนวิธีอื่นๆอีก ดังนี้
=== วิธีการแก้ปัญหาโดยการแบ่งแยกและเอาชนะ ===
เริ่มจากการแบ่งส่วนของตารางหมากรุกเป็นส่วนย่อยๆ พิจารณาหาวิธีในแต่ละส่วนย่อย แล้วจึงนำแต่ละส่วนย่อยมาประกอบกัน ซึ่งวิธีการนี้สามารถบรรยายความสัมพันธ์ของฟังก์ชันในแง่ของอัตราการเติบโตได้ด้วยสัญกรณ์เชิงเส้นกำกับ O(n<sup>2</sup>)
=== กฎของวานดอล์ฟ ===
[[Image:Warnsdorff.gif|left|thumb|240px|รูปภาพตาราง แสดงวิธีการเดินม้าหมากรุกตามกฎของวานส์ดอล์ฟ]]
กฎของวานดอล์ฟเป็นวิธีการแบบ[[ฮิวริสติก]]สำหรับการหาวิธีการเดินม้าหมากรุก กล่าวโดยสรุปคือในการเดินม้าแต่ละครั้งนั้นจะต้องเป็นไปตามกฎ กล่าวคือ
กำหนดให้ ในทุกช่องที่สามารถเดินไปจากช่องปัจจุบัน(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว) จะมีค่าเท่ากับจำนวนช่องที่ช่องดังกล่าวสามารถเดินต่อไปได้ตามกฏของการเดินม้าหมากรุก(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว)
การเลือกช่องต่อไปสำหรับการเดินม้าจะพิจารณาเลือกช่องที่มีค่าน้อยที่สุด ซึ่งหากมีหลายช่องที่มีค่าน้อยที่สุดเท่ากันก็อาจมีทางเลือกได้หลายทาง
นอกจากกลวิธีดังกล่าวในการแก้ปัญหานี้ยังมีกลวิธีอื่นๆอีกหลายหลายวิธี เช่น กลวิธีของโพ และกลวิธีของสไควเออร์และคูล
โดยทั่วไปกฎของวานส์ดอล์ฟ จะนำไปประยุกต์ใช้กับเรื่องกราฟได้ ในเรื่องของทฤษฎีกราฟ การเดินม้าหมากรุกแต่ละครั้ง จะเดินไปยังปมที่อยู่ติดกันด้วยดีกรีที่น้อยที่สุด
ถึงแม้ว่าปัญหาทางเดินของแฮมิลตันจะจัดอยู่ในเรื่องของกลุ่มปัญหาเอ็นพีแบบยาก โดยปกติแล้วในการใช้วิธีการแบบฮิวริสติกในหลายๆกราฟสามารถแก้ปัญหาได้ด้วยอัตราการเติบโตแบบเชิงเส้น แต่สำหรับปัญหาทางเดินม้าหมากรุกนี้จัดเปนกรณีพิเศษ
====วิธีดำเนินการเพื่อประยุกต์กับกฎดังกล่าว====
กฏของวานดอล์ฟสามารถใช้ได้กับจุดเริ่มต้นที่ช่องใดก็ได้ของตารางหมากรุก จำนวนครั้งที่เดินได้ก็คือจำนวนตัวเลขที่บรรจุในแต่ละช่อง ซึ่งตามกฎแล้ว จะต้องเดินไปยังช่องที่มีตัวเลขน้อยที่สุดนั่นเอง จากนั้นก็เลือกเดินตามกฎต่อไปจนกว่าจะเดินได้ครบทุกช่อง
<br />
ข้อตกลง :
* ตำแหน่ง Q จะเข้าถึงจากตัวแหน่ง P ได้ ถ้าหากว่า P สามารถเคลื่อนที่ไปยัง Q ได้ด้วยการเคลื่อนที่เพียงครั้งเดียว และ Q ยังเป็นตำแหน่งที่ยังไม่ได้เยี่ยม
* ความสามารถในการเข้าถึงตำแหน่ง P เท่ากับ จำนวนของตำแหน่งที่สามารถเข้าถึงได้จากตำแหน่ง P
<br />
ขั้นตอนวิธี :<br />
:1. กำหนดให้ P เป็นจำแหน่งเริ่มต้นของการเดินม้าหมากรุก โดยเลือกจุดเริ่มต้นนี้แบบสุ่ม
:2. กำหนดให้จุดเริ่มต้นมีเลขกำกับการเคลื่อนที่เป็น 1
:3. สำหรับทุกการเคลื่อนที่ที่มีเลขกำกับการเคลื่อนที่เป็น 2 ขึ้นไป
:3.1 กำหนดให้ S เป็นตำแหน่งที่เข้าถึงได้จากตำแหน่งที่ส่งเข้าไป
:3.2 กำหนดตำแหน่ง P ให้เป็นตำแหน่ง ที่ตำแหน่ง S มีความสามารถที่จะการเข้าถึงได้น้อยที่สุด
:3.3 ทำเครื่องหมายแสดงเลขกำกับการเคลื่อนที่บนตำแหน่ง P</nowiki><br />
:4. คืนค่าตารางหมากรุกที่ได้รับการทำเครื่องหมายแล้ว โดยแต่ละช่องจะถูกทำเครื่องหมายด้วยเลขกำกับการเคลื่อนที่ที่มันถูกเยี่ยม
==ตัวอย่างโปรแกรมในภาษาซี==
* http://chinmaylokesh.wordpress.com/2011/06/20/knights-tour-using-warnsdorffs-algorithm-a-heuristic-approach/
==อ้างอิง==
{{รายการอ้างอิง}}
[[หมวดหมู่:หมากรุก]]
[[หมวดหมู่:ทฤษฎีกราฟ]]
==เพิ่มเติม==
* http://www.wou.edu/~broegb/Cs345/KnightTour.pdf
| |||