กฎของวานดอล์ฟ

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

กฎของวานดอล์ฟ[แก้]

รูปภาพตาราง แสดงวิธีการเดินม้าหมากรุกตามกฎของวานส์ดอล์ฟ

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

วิธีดำเนินการเพื่อประยุกต์กับกฎดังกล่าว[แก้]

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


ข้อตกลง :

  • ตำแหน่ง Q จะเข้าถึงจากตัวแหน่ง P ได้ ถ้าหากว่า P สามารถเคลื่อนที่ไปยัง Q ได้ด้วยการเคลื่อนที่เพียงครั้งเดียว และ Q ยังเป็นตำแหน่งที่ยังไม่ได้เยี่ยม
  • ความสามารถในการเข้าถึงตำแหน่ง P เท่ากับ จำนวนของตำแหน่งที่สามารถเข้าถึงได้จากตำแหน่ง P


ขั้นตอนวิธี :

1. กำหนดให้ P เป็นจำแหน่งเริ่มต้นของการเดินม้าหมากรุก โดยเลือกจุดเริ่มต้นนี้แบบสุ่ม
2. กำหนดให้จุดเริ่มต้นมีเลขกำกับการเคลื่อนที่เป็น 1
3. สำหรับทุกการเคลื่อนที่ที่มีเลขกำกับการเคลื่อนที่เป็น 2 ขึ้นไป
3.1 กำหนดให้ S เป็นตำแหน่งที่เข้าถึงได้จากตำแหน่งที่ส่งเข้าไป
3.2 กำหนดตำแหน่ง P ให้เป็นตำแหน่ง ที่ตำแหน่ง S มีความสามารถที่จะการเข้าถึงได้น้อยที่สุด
3.3 ทำเครื่องหมายแสดงเลขกำกับการเคลื่อนที่บนตำแหน่ง P</nowiki>
4. คืนค่าตารางหมากรุกที่ได้รับการทำเครื่องหมายแล้ว โดยแต่ละช่องจะถูกทำเครื่องหมายด้วยเลขกำกับการเคลื่อนที่ที่มันถูกเยี่ยม

ตัวอย่างโปรแกรมในภาษาซี[แก้]

เพิ่มเติม[แก้]