เมนูนำทาง
หอคอยฮานอย คำตอบของเล่นส่วนใหญ่จะมีจาน 8 ใบ เกมนี้จะดูเหมือนยากสำหรับผู้เริ่มเล่น แต่สามารถแก้ได้ด้วยขั้นตอนวิธีที่ไม่ซับซ้อน ดังนี้
ต้องการย้ายจานทั้งหมด n ใบ จากหมุด A ไปยังหมุด B:
ขั้นตอนวิธีด้านบนนั้นเรียกว่า ขั้นตอนวิธีเวียนเกิด (recursive algorithm): ในการแก้ปัญหาด้านบน จะเห็นได้ว่าจะเหลือปัญหาการย้ายจานจำนวน n-1 ใบ ซึ่งใช้ขั้นตอนวิธีเดียวกันแก้จะลดเหลือปัญหา n-2 ใบ ไปจนเหลือเพียงการย้ายจานเพียง 1 ใบ
ปัญหาทาวเวอร์ออฟฮานอยนี้ เป็นปัญหาที่นิยมใช้ในการสอนการเขียนโปรแกรมเบื้องต้น ใช้เป็นตัวอย่างสำหรับการเขียนโปรแกรมขั้นตอนวิธีเวียนเกิด นอกจากนั้นแล้วยังใช้เป็นตัวอย่างของขั้นตอนวิธีเวลาแบบเลขชี้กำลัง (exponential time) คือ ยกเว้นในกรณีจานจำนวนน้อยมากๆ เท่านั้น ที่ปัญหานี้จะสามารถแก้ได้ ในกรณีทั่วไปการแก้ปัญหานี้จะต้องใช้เวลามหาศาล ถึงแม้ว่าจะใช้คอมพิวเตอร์ที่เร็วที่สุดในโลกในการแก้ปัญหาก็ตาม และไม่มีวิธีที่จะแก้ปัญหาให้เร็วขึ้นอีกได้ เนื่องจากจำนวนครั้งของการย้ายจานเพื่อแก้ปัญหานั้น มีค่าเพิ่มขึ้นในระดับเลขยกกำลังตามจำนวนจาน
เราสามารถคำนวณหาจำนวนครั้งของการเคลื่อนย้ายจาน ที่จำเป็นในการแก้ปัญหานี้ จากความสัมพันธ์เวียนเกิด (recurrence relation) ได้เท่ากับ 2 n − 1 {\displaystyle 2^{n}-1} โดย n {\displaystyle n} คือ จำนวนจานทั้งหมด ผลลัพธ์นี้ได้จากข้อสังเกตที่ว่า ในขั้นตอนที่ 1 และ 3 ใช้เวลาในการแก้ปัญหา T n − 1 {\displaystyle T_{n-1}} และ ขั้นที่ 2 ใช้เวลาคงที่ ซึ่งให้ความสัมพันธ์ T n = 2 T n − 1 + 1 {\displaystyle T_{n}=2T_{n-1}+1}
โปรแกรมในการแก้ปัญหา ในภาษาแฮสเคล :
hanoi n = hanoi' n 1 2 3hanoi' 0 _ _ _ = []hanoi' n f i t = (hanoi' (n-1) f t i) ++ (f, t) : (hanoi' (n-1) i f t)
โดย n คือ จำนวนจานทั้งหมด โปรแกรมจะส่งคืนผล ในรูปของรายการของการเคลื่อนย้ายทั้งหมดที่ต้องกระทำ
ขั้นตอนวิธีด้านบน สามารถอธิบายด้วยภาษาชาวบ้าน ได้ดังนี้
ตอนนี้ เรามีจาน 2 ใบวางตามลำดับถูกต้องที่หมุด B และ หมุด C ไม่มีจาน
ในแต่ละขั้นจะเห็นได้ว่า เราสร้างหอคอยจาก จาน #i ขึ้นไปจนถึง #1 แล้ว เราก็เริ่มย้ายจาน #i+1 จากหมุด A (ซึ่งเป็นหมุดเริ่มต้น) ไปยังหมุดที่ว่างอยู่ เพิ่มเริ่มต้นด้านล่างหอคอยใหม่ (สังเกตว่า การย้ายกองจาน #1 ถึง #i-1 ไปไว้บนหมุดที่ต้องการ คือ บนหมุดที่มี จาน #i อยู่นั้น จะสามารถใช้หมุดที่เหลืออยู่ได้อย่างอิสระ เนื่องจากจานที่เหลืออยู่บนหมุดนั้น คือ ที่หมายเลขมากกว่า #i+1 ไม่มีผลกระทบในการย้ายกองเนื่องจาก จานเหล่านี้มีขนาดใหญ่กว่าจานในกอง #1 ถึง #i-1 ทุกใบ จึงทำให้การย้ายไม่เกิดการผิดกติกา)
จำนวนครั้งในการเคลื่อนย้ายจาน n ใบ เพื่อแก้ปัญหา มีจำนวนครั้งเท่ากับ 2n-1
ทำการเคลื่อนย้ายจาน #1 และจานอื่นที่ใหญ่กว่า สลับกัน โดยที่หากมีจานใหญ่ 2 ใบที่สามารถย้ายได้ ให้ย้ายใบที่เล็กกว่าไปไว้บนใบที่ใหญ่กว่า ในการเคลื่อนย้าย ให้เคลื่อนจานที่มี หมายเลขคี่ ไปทางซ้ายทีละ 1 หมุด(จนสุดแล้ววนกลับมาเริ่มที่หมุดด้านขวา) และ จานที่มี หมายเลขคู่ ไปทางขวาทีละ 1 หมุด(จนสุดแล้ววนกลับมาเริ่มที่หมุดที่หมุดด้านซ้าย)
หรือที่ง่ายกว่านั้น คือ จะต้องย้ายจานใบเล็กที่สุด 1 ครั้ง หลังจากที่มีการย้ายจานอื่นทุกครั้ง โดยที่การย้ายจานใบเล็กนั้นจะย้ายไปในทิศทางเดียวกันตลอด หลังจากเคลื่อนย้ายจานใบเล็กแล้ว จะมีการเคลื่อนย้ายจานอื่น ที่ไม่ผิดกติกาให้ทำได้เพียงลักษณะเดียวเท่านั้น
ถึงแม้ว่า ขั้นตอนวิธีในการแก้ปัญหานั้นไม่ซับซ้อน แต่การแก้ปัญหาที่เร็วที่สุด สำหรับจาน n ใบนั้น ต้องใช้การย้ายถึง 2n−1 ครั้ง โดยทั่วไปแล้วในกรณีที่มีหมุดมากกว่า 3 หลักนั้น ไม่มีวิธีคำนวณหาจำนวนครั้งที่จำเป็นต้องใช้ในการแก้ปัญหา และวิธีการนับจำนวนครั้งสำหรับกรณีที่มีจานจำนวนมากก็ไม่สามารถทำได้ในทางปฏิบัติ
เราอาจใช้เลขฐานสอง ในการระบุการเคลื่อนย้ายตำแหน่งของจาน (โดยสภาวะเริ่มต้นเป็นการเคลื่อนที่ #0 มีเลขฐานสองทุกตำแหน่งเป็น 0 และ สภาวะสุดท้ายเป็นการเคลื่อนที่ #2n−1 มีเลขฐานสองทุกตำแหน่งเป็น 1) โดยใช้วิธีการดังนี้
ตัวอย่าง จาน 8 ใบ:
ตามรูปแบบเลขฐานสองนี้ เราสามารถหาตำแหน่งของจานต่างๆ ได้ไม่ยาก ถึงแม้จะมีจานเป็นจำนวนมากก็ตาม ส่วนหาการย้ายจาน ครั้งที่ n ว่าย้ายจากหมุดไหนไปยังหมุดไหนนั้น สามารถหาได้จากเลขฐานสอง n โดยใช้ การดำเนินการเป็นบิต (bitwise operation) กรณีที่ใช้วากยสัมพันธ์ของภาษาซี การย้ายครั้งที่ n จะย้ายจากหมุด (n&n-1)%3
ไปยังหมุด ((n|n-1)+1)%3
โดยที่ตำแหน่งเริ่มของจานอยู่ที่หมุด 0 และจบการย้ายที่หมุด 1 หรือ หมุด 2 ขึ้นอยู่กับจำนวนจานว่าเป็นจำนวนคู่ หรือ จำนวนคี่ ซึ่งวิธีการนี้ ช่วยให้สร้างโปรแกรมสำหรับแก้ปัญหาด้วยคอมพิวเตอร์เป็นแบบไม่เวียนเกิด และสามารถแก้ปัญหาได้รวดเร็ว
รหัสเกรย์ (Gray code) ซึ่งเป็นระบบตัวเลขฐานสองแบบหนึ่ง เป็นรูปแบบจำลองอีกแบบหนึ่งซึ่งสามารถใช้ในการแก้ปัญหา ในระบบรหัสเกรย์นั้น ตัวเลขจะเขียนอยู่ในรูปผสมของตัวเลข 0 และ 1 แต่จะแตกต่างเลขฐานสองมาตรฐาน โดยรหัสเกรย์ สำหรับแทนตัวเลขที่อยู่ถัดกัน จะต่างกันเพียง 1 บิตเท่านั้น จำนวนบิตที่ใช้ในรหัสเกรย์นั้นมีความสำคัญ รวมทั้งเลขศูนย์ที่อยู่นำหน้าก็ม่ความสำคัญ (ซึ่งต่างจากเลขฐานสองมาตรฐานที่เลขศูนย์ที่อยู่นำหน้านั้นไม่มีความสำคัญ)
หากจำนวนบิตของรหัสเกรย์ เท่ากับจำนวนจานในเกม และเริ่มนับจากศูนย์ เพิ่มขึ้นเรื่อยๆ บิตที่เปลี่ยนไปในการนับแต่ละขั้น ก็คือการย้ายจาน โดยบิตที่ค่าความสำคัญน้อยที่สุด คือจานใบเล็กที่สุด และ บิตที่มีค่าความสำคัญมากที่สุดคือ จานใบใหญ่ที่สุด
วิธีนี้บอกว่าจานใบไหนถูกย้าย แต่ไม่ได้บอกว่าย้ายไปที่ไหน กฎของการย้ายจะเป็นตัวบอกการย้าย โดยการย้ายจานนั้น จานที่มีภาวะคู่หรือคี่ (parity) เหมือนกันจะไม่วางซ้อนทับกัน (คือ จานเลขคู่ จะไม่ย้ายไปวางบนหมุดที่มีจานเลขคู่อยู่ด้านบนสุด จานเลขคี่ ก็จะไม่ย้ายไปวางบนจานเลขคี่) หากเราทำการย้ายตากกฎนี้ก็จะไม่เกิดความสับสนของตำแหน่งที่จะต้องย้ายจานไปวาง
เมนูนำทาง
หอคอยฮานอย คำตอบใกล้เคียง
หอคอยฮานอยแหล่งที่มา
WikiPedia: หอคอยฮานอย http://www.farfarfar.com/games/towers_of_hanoi/ http://www.goobix.com/games/hanoi/ http://www.kernelthread.com/hanoi/ http://occawlonline.pearsoned.com/bookbind/pubbook... http://math.bu.edu/DYSYS/applets/hanoi.html http://www.cs.wm.edu/~pkstoc/toh.html http://www.cut-the-knot.org/Curriculum/Combinatori... http://www.cut-the-knot.org/Curriculum/Combinatori... http://www.lawrencehallofscience.org/Java/Tower/to... https://commons.wikimedia.org/wiki/Tower_of_Hanoi?...