ผลต่างระหว่างรุ่นของ "ปัญหาทางเดินม้าหมากรุก"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ล autoCategory |
Nullzerobot (คุย | ส่วนร่วม) ล โรบอต: แทนที่คำ |
||
บรรทัด 9:
==ประวัติความเป็นมา==
ปัญหาทางเดินม้าหมากรุกได้ถูกค้นพบในศตวรรษที่ 9 โดยกวีชาวอินเดียชื่อว่า รุถถะ เขาได้เขียนบทกวีเกี่ยวกับศิลปะ แบบแผนในการเล่นม้าหมากรุกแบบครึ่งกระดานในภาษาสันสกฤต ซึ่งแตกต่างจากกวีอื่นๆที่เขียนไว้ <br />
: ลีออนฮาร์ด ออยเลอร์ เป็นหนึ่งในนักคณิตศาสตร์กลุ่มแรกที่สามารถจับเทคนิคปัญหาทางเดินม้าหมากรุกได้ ซึ่งกล่าวได้ว่าเป็นเทคนิคแรกที่สมบูรณ์แบบ เทคนิคนี้ได้ถูกเขียนเป็น
: ในศตวรรษที่ 20 กลุ่มของนักเขียน นามว่า อูลิโป ได้ใช้
==ทางเดินม้าหมากรุกปิด==
บรรทัด 29:
:เมื่อกระดานข้างที่สั้นกว่ามีความกว้างเป็น 1,2 หรือ 4 จะไม่สามารถการเดินแบบปิดได้ และเมื่อ m=1 หรือ 2 จะไม่สามารถเดินแบบปิดได้ เนื่องจากม้าจะไม่สามารถเดินไปในทุกๆช่องได้ (ยกเว้นตารางหมากรุกขนาด 1x1) และเมื่อ m=4 ก็ไม่สามารถเกิดการเดินแบบปิดได้เช่นกัน โดยการพิสูจน์จากสีในตารางหมากรุก<br />
:เริ่มพิสูจน์โดยการสมมุติให้ตาราง 4xn สามารถเดินม้าแบบปิดได้ และให้ A1 เป็นเช็ตของช่องสีดำและ A2 เป็นเช็ตของช่องสีขาว แล้วถ้ามีช่องสีขาวและช่องสีดำ สลับกันบนกระดานหมากรุก พิจารณาจากรูปทางด้านขวา กำหนดให้ B1 เป็นเช็ตของช่องสีเขียวและ B2 เป็นเช็ตของช่องสีแดง จากรูปทางด้านขวาจะ
:ถ้าเราปฏิบัติตามการสมมุติข้างต้นเราจะพบข้อขัดแย้งดังนี้
:
บรรทัด 56:
[[Image:Warnsdorff.gif|left|thumb|240px|รูปภาพตาราง แสดงวิธีการเดินม้าหมากรุกตามกฎของวานส์ดอล์ฟ]]
กฎของวานดอล์ฟเป็นวิธีการแบบ[[ฮิวริสติก]]สำหรับการหาวิธีการเดินม้าหมากรุก กล่าวโดยสรุปคือในการเดินม้าแต่ละครั้งนั้นจะต้องเป็นไปตามกฎ กล่าวคือ
กำหนดให้ ในทุกช่องที่สามารถเดินไปจากช่องปัจจุบัน(ซึ่งไม่นับรวมถึงช่องที่เคยเดินผ่านไปแล้ว) จะมีค่าเท่ากับจำนวนช่องที่ช่องดังกล่าวสามารถเดินต่อไปได้ตาม
การเลือกช่องต่อไปสำหรับการเดินม้าจะพิจารณาเลือกช่องที่มีค่าน้อยที่สุด ซึ่งหากมีหลายช่องที่มีค่าน้อยที่สุดเท่ากันก็อาจมีทางเลือกได้หลายทาง
นอกจากกลวิธีดังกล่าวในการแก้ปัญหานี้ยังมีกลวิธีอื่นๆอีกหลายหลายวิธี เช่น กลวิธีของโพ และกลวิธีของสไควเออร์และคูล
บรรทัด 63:
====วิธีดำเนินการเพื่อประยุกต์กับกฎดังกล่าว====
<br />
|