ปัญหาทาวเวอร์ของฮานอย

ปัญหาทาวเวอร์ของฮานอย (The Towers of Hanoi Problem)

                ที่ผ่านมา ปัญหาที่ต้องแก้แบบรีเคอร์ซีฟ มักอยู่ในรูปของสมการ เช่น หากต้องการหาค่าของ n ต้องการค่าของ n-1 ก่อน และหากต้องการหาค่าของ n-1 ต้องหาค่าของ n-2 ทำเช่นนี้เรื่อยไปจนกระทั่ง เมื่อ n มีค่า 1 หรือที่เรียกว่า จุดวกกลับ เห็นได้ชัดเจนว่าปัญหามีลักษณะของการเรียกซ้ำหรือรีเคอร์ซีฟ

แนวทางการแก้ปัญหา

                จากวิธีการแก้ปัญหาแบบรีเคอร์ซีฟที่ว่า การหาค่าของ n ต้องหาผลลัพธ์ของ n-1 ก่อน และหากต้องการหาค่าของ n-1 ต้องหาผลลัพธ์ของ n-2 ก่อน ทำเช่นนี้เรื่อยไปจนถึงค่า 1 ซึ่งค่า 1 ที่ได้คือคำตอบสุดท้าย (จุดวกกลับ)โดยไม่ต้องย้อนกลับไปหาค่าก่อนหน้านั้นอีก

อัลกอริทึม (Algorithm)

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

1.       หากมีแหวน 1 วง ที่เสา A ให้ย้ายแหวนจากเสา A ไปยังเสา C

2.       ย้ายแหวนด้านบน 4 วง จากเสา A ไปยังเสา B โดยใช้เสา C เป็นที่พักชั่วคราว

3.       ย้ายแหวน 4 วงจากเสา B ไปยังเสา C โดยใช้เสา A เป็นที่พักชั่วคราว

เพื่อให้วิธีการนี้ สามารถแก้ปัญหาทั่วไปได้ จึงเปลี่ยนจำนวนแหวนจาก 5 วง เป็น n วง และ

ขั้นตอนการแก้ปัญหาเปลี่ยนไปได้ดังนี้

1.       หาก  n = = 1 ย้ายแหวนจากเสา A ไปยังเสา C

2.       ย้ายแหวนด้านบน n-1 วง จากเสา A ไปยังเสา B โดยใช้เสา C เป็นที่พักชั่วคราว

3.       ย้ายแหวน n-1 วง จากเสา B ไปยังเสา C โดยใช้เสา A เป็นที่พักชั่วคราว

..................................................................................................................................

ปัญหาหอคอยฮานอย (The Tower of Hanoi ) เป็นเกมในการเคลื่อนย้าย

วงกลม 3 วงที่มีขนาดต่างกันที่อยู่ในเสาต้นที่1 ไปยังต้นที่ 2 โดยมีเงื่อนไขว่า มีเสา 3 ต้น

(เสาต้นที่1 มีวงกลมซ้อนกัน 3 วง วงใหญ่สุดอยู่ด้านล่างสุด และวงเล็กสุดอยู่บนสุด

เสาต้นที่2 และต้นที่ 3 ว่างเปล่า ) และในการเคลื่อนย้ายวงกลมสามารถเคลื่อนย้าย

วงกลมทีละวงไปยังเสาทั้ง 3 ต้น แต่ห้ามวงกลมขนาดใหญ่ซ้อนทับวงกลมขนาดเล็ก

ถามว่าจำนวนครั้งที่น้อยที่สุดที่ทำได้จะเป็นเท่าไร

วิธีทำ จากปัญหานี้สามารถสร้างเป็นลำดับที่เป็นความสัมพันธ์เวียนเกิดได้ว่า

ให้ ลำดับ {Hn} เป็นลำดับของจำนวนครั้งในการทำสำเร็จเมื่อมีวงกลมอยู่ n วง ด้วยกัน

จะได้ว่า H1 = 1และ Hn = Hn-1 + 1 + Hn-1

 ( ย้ายวงกลม n-1 วง จากเสาต้นที่ 1 ไปยังต้นที่3 ต้องใช้จำนวน Hn-1 ครั้ง

 จากนั้นย้ายวงกลมที่ใหญ่ที่สุดในเสาที่ 1 ไปยังเสาที่ 2 ซึ่งใช้จำนวน 1 ครั้ง

 หลังจากนั้นย้ายวงกลม n-1 วง จากเสาต้นที่ 3 ไปยังต้นที่ 2 ต้องใช้จำนวน Hn-1 ครั้ง )

จึงได้ว่า Hn = 2 Hn-1 + 1

เมื่อ Hn = 2 Hn-1 + 1 , H1 = 1

วิธีการแก้ปัญหา  จาก Hn = 2Hn-1 + 1

= 2(2Hn-2 +1) +1 = 22 Hn-2 + 2 +1

= 22 (2Hn-3 + 1) +2+1 = 23 Hn-3 + 22 + 2 + 1

= 23 (2Hn-4 +1) + 22 + 2 +1 = 24 Hn-4 + 23 + 22 +2+1

……

= 2n-1 H1 + 2n-2 + 2n-3 +…+2 + 1

= 2n-1 + 2n-2 +…+ 2 + 1

= 2n - 1

cr. http://www.l3nr.org/posts/156202

cr.http://suanpalm3.kmutnb.ac.th/teache...2255516420.pdf