หอคอยฮานอย

จากวิกิพีเดีย สารานุกรมเสรี

ปัญหาหอคอยฮานอย (Tower of Hanoi Puzzle) เป็นปัญหาทางคณิตศาสตร์ ประกอบด้วยเสาสามหลักและวัตถุต่างขนาดซึ่งเจาะรูตรงกลางคล้องกับเสาตามรูป

ชุดของเล่นหอคอยแห่งฮานอย

ประวัติ[แก้]

 ในปี พ.ศ. ๒๔๕๖ มีนักคณิตศาสตร์ชาวฝรั่งเศสชื่อว่า François Édouard Anatole Lucas ให้กำเนิดปัญหาหอคอยฮานอยซึ่งได้รับแรงบันดาลใจจากคำบอกกล่าวพราหมณ์ในวัดกาสี วิศวนาถ ณ.เมืองพาราณาสี ปัจจุบันตั้งอยู่ที่รัฐอุตตรประเทศ สาธารณรัฐอินเดีย ซึ่งภายในวัดมีเสา 3 หลักและมีจานสีทองจำนวน 64 ชิ้นคล้องกับเสา ตามคำทำนายของพราหมณ์ว่า "ถ้าปัญหาถูกแก้แล้ววาระสุดท้ายของโลกมาถึง" หมายความว่า พราหมณ์สามารถสับเปลี่ยนจานสีทองจากเสาเริ่มต้นไปยังเสาใดเสาหนึ่งที่ไม่ใช่เสาเริ่มต้น จึงเรียกปัญหาอีกชื่อหนึ่งว่า "ปัญหาหอแห่งพรหม" 
 ต่อมาในปี พ.ศ. ๒๔๒๗ มีนักคณิตศาสตร์ชาวสกอตแลนด์ 2 คนคือ Robert Edgar Allardice กับ Alexander Yule Fraser ได้ร่วมกันหาสมการทางคณิตศาสตร์สำหรับการย้ายวัตถุจากเสาเริ่มต้นไปยังเสาใดเสาหนึ่งที่ไม่ใช่เสาเริ่มต้น
 จากนั้นในปี พ.ศ. ๒๕๒๔ Derick Wood นักคณิตศาสตร์ชาวอังกฤษได้พิสูจน์สมการทางคณิตศาสตร์สำหรับการย้ายวัตถุจากเสาเริ่มต้นไปยังเสาใดเสาหนึ่งที่ไม่ใช่เสาเริ่มต้นเป็นจำนวนครั้งน้อยที่สุดที่เป็นไปได้เท่านั้น

เริ่มต้นและเป้าหมาย[แก้]

ปัญหาหอคอยฮานอยเริ่มต้นจากวัตถุเรียงตามขนาดวัตถุจากใหญ่ที่สุดอยู่ทางด้านล่างไปหาวัตถุที่ขนาดเล็กที่สุดอยู่ด้านบนสุดไปยังเสาใดเสาหนึ่งที่ไม่ใช่เสาเริ่มต้น

กติกา[แก้]

  • วัตถุ 1 ชิ้นสามารถสับเปลี่ยนได้ 1 ครั้งเท่านั้น
  • ห้ามวางวัตถุที่ใหญ่อยู่ด้านบนวัตถุที่เล็ก

ผลลัพธ์[แก้]

จำนวนครั้งน้อยที่สุดที่เป็นไปได้สำหรับการย้ายวัตถุ n ชิ้นจากเสาเริ่มต้นไปยังเสาใดเสาหนึ่งที่ไม่ใช่เสาเริ่มต้นเป็น 2n − 1 ครั้ง สำหรับ n ทีเป็นจำนวนนับใดๆ


แหล่งข้อมูลอื่น[แก้]

ประวัติ[แก้]

ขั้นตอนวิธี[แก้]