อัลกอริทึมของหอคอยแห่งฮานอย: Python, C++ Code
ทีมบรรณาธิการ
⚡ สรุปอย่างชาญฉลาด
อัลกอริทึมหอคอยฮานอยเป็นปริศนาแบบเรียกซ้ำคลาสสิกที่เคลื่อนย้ายกองแผ่นดิสก์ระหว่างหมุดสามตัวโดยไม่วางแผ่นดิสก์ขนาดใหญ่ไว้บนแผ่นดิสก์ขนาดเล็ก ซึ่งแสดงให้เห็นถึงหลักการแบ่งและพิชิตได้อย่างชัดเจน
หอคอยแห่งฮานอยคืออะไร?
หอคอยฮานอยเป็นปริศนาทางคณิตศาสตร์ที่ประกอบด้วยแท่งสามแท่งและแผ่นดิสก์ที่มีขนาดลดลงเรียงซ้อนกัน เรียกอีกชื่อหนึ่งว่า หอคอยแห่งพระพรหม หรือ หอคอยลูคัส เนื่องจากนักคณิตศาสตร์ชาวฝรั่งเศส เอ็ดวาร์ด ลูคัส ได้คิดค้นขึ้นในปี 1883 ปริศนานี้มีพื้นฐานมาจากตำนานเกี่ยวกับการเคลื่อนย้ายแผ่นดิสก์ทองคำระหว่างแท่งสามแท่ง
ปริศนานี้ประกอบด้วยแท่งสามแท่งและแผ่นดิสก์ที่ซ้อนกันจำนวนหนึ่ง แท่งเหล่านี้ถูกจัดเรียงเป็นหอคอยแบบวงจร โดยแผ่นดิสก์ขนาดใหญ่จะอยู่ด้านล่างและแผ่นดิสก์ขนาดเล็กจะอยู่ด้านบน
ในตอนเริ่มต้น เรามีแท่งหรือแกนสามอัน อันหนึ่ง (แท่ง A ในตัวอย่าง) มีแผ่นดิสก์วางซ้อนกันอยู่ทั้งหมด เป้าหมายคือการย้ายแผ่นดิสก์ทั้งหมดจากแท่งหนึ่ง (A) ไปยังอีกแท่งหนึ่ง (C) โดยต้องปฏิบัติตามกฎเฉพาะบางข้อ
นี่คือการตั้งค่าเริ่มต้นของปริศนา:
ปัญหาหอคอยแห่งฮานอย
และนี่คือเป้าหมายสุดท้าย:
กฎของหอคอยฮานอย
ต่อไปนี้คือหลักเกณฑ์สำคัญสำหรับการเล่นเกมหอคอยฮานอย:
- ในขั้นเริ่มต้นของปริศนา แผ่นดิสก์ทั้งหมดจะวางซ้อนกันอยู่บนแท่งที่หนึ่ง
- ในขั้นตอนสุดท้าย แผ่นดิสก์ทั้งหมดจากแท่งที่หนึ่งจะถูกวางซ้อนบนแท่งที่สองหรือแท่งที่สาม
- ในแต่ละครั้งจะมีเพียงแผ่นดิสก์เดียวเท่านั้นที่สามารถเคลื่อนที่จากแท่งหนึ่งไปยังอีกแท่งหนึ่งได้
- เฉพาะแผ่นดิสก์บนสุดบนแกนเท่านั้นที่สามารถขยับได้
- ไม่สามารถวางแผ่นดิสก์ขนาดใหญ่ทับแผ่นดิสก์ขนาดเล็กกว่าได้
ตำนานดั้งเดิมกล่าวถึงการเคลื่อนย้ายแผ่นดิสก์ 64 แผ่น โดยนักบวชสามารถเคลื่อนย้ายแผ่นดิสก์ได้ทีละแผ่นตามกฎ ตามตำนานกล่าวว่ามีคำทำนายว่าโลกจะถึงจุดจบหากพวกเขาสามารถทำภารกิจนี้สำเร็จ ในส่วนของความซับซ้อนของเวลา เราจะแสดงให้เห็นว่าการจัดเรียงหอคอยฮานอยที่มีแผ่นดิสก์ n แผ่นนั้นต้องใช้การเคลื่อนย้าย 2^n – 1 ครั้ง
ดังนั้น หากนักบวชต้องใช้เวลา 1 วินาทีในการเคลื่อนแผ่นดิสก์หนึ่งแผ่น เวลาทั้งหมดที่ใช้ในการแก้ปริศนาจะเท่ากับ 2^64 – 1 วินาที หรือประมาณ 584,942,417,356 ปี 26 วัน 7 ชั่วโมง และ 15 วินาที
อัลกอริทึมสำหรับหอคอยแห่งฮานอย
วิธีที่พบได้บ่อยที่สุดในการแก้ปัญหาหอคอยฮานอยคือการใช้อัลกอริธึมแบบเรียกซ้ำ ขั้นแรก เราเลือกแท่งสองแท่งเป็นจุดเริ่มต้นและจุดปลายทาง ส่วนแท่งที่เหลือจะทำหน้าที่เป็นตัวช่วยหรือตัวเสริม
ต่อไปนี้เป็นขั้นตอนในการไขปริศนาหอคอยแห่งฮานอย:
- ย้ายดิสก์ n-1 ด้านบนจากหมุดต้นทางไปยังหมุดตัวช่วย
- ย้ายแผ่นดิสก์ที่ n จากหลักต้นทางไปยังหลักปลายทาง
- ย้ายแผ่นดิสก์ที่เหลือ n-1 แผ่นจากหมุดช่วยไปยังหมุดปลายทาง
หมายเหตุ ถ้าเรามีดิสก์เพียงตัวเดียว เราสามารถย้ายข้อมูลจากต้นทางไปยังปลายทางได้โดยตรง
วิธีแก้ปริศนาหอคอยแห่งฮานอย
เรามาลองยกตัวอย่างอัลกอริธึมนี้สำหรับแผ่นดิสก์สามแผ่นกัน โดยให้หมุด A เป็นแหล่งกำเนิด หมุด B เป็นตัวช่วย และหมุด C เป็นปลายทาง
ขั้นตอน 1) ในขั้นต้น แผ่นดิสก์ทั้งหมดจะถูกวางซ้อนกันบนหมุด A
ในขั้นตอนนี้: ต้นทาง = หมุด A, ปลายทาง = หมุด C, ตัวช่วย = หมุด B
ตอนนี้ เราต้องย้ายดิสก์ n-1 อันดับแรกจากแหล่งที่มาไปยังตัวช่วยเหลือ
หมายเหตุ แม้ว่าเราจะสามารถเคลื่อนย้ายดิสก์ได้ครั้งละหนึ่งแผ่นเท่านั้น แต่ขั้นตอนนี้จะลดปัญหาที่มี 3 ดิสก์ให้เหลือเพียงปัญหาที่มี 2 ดิสก์ ซึ่งสามารถจัดการได้ด้วยการเรียกซ้ำ
ขั้นตอน 2) เนื่องจากเราเรียกฟังก์ชันแบบเรียกซ้ำจากจุด A โดยมีจุด B เป็นปลายทาง เราจึงใช้จุด C เป็นตัวช่วย
โปรดสังเกตว่าเรากลับมาที่ขั้นตอนแรกของปัญหาหอคอยฮานอยอีกครั้ง แต่คราวนี้สำหรับแผ่นดิสก์สองแผ่น เราย้ายแผ่นดิสก์ n-1 (นั่นคือ หนึ่งแผ่น) จากต้นทางไปยังตัวช่วย ซึ่งจะย้ายแผ่นดิสก์ที่เล็กที่สุดจากหลัก A ไปยังหลัก C
ในขั้นตอนนี้: ต้นทาง = หมุด A, ปลายทาง = หมุด B, ตัวช่วย = หมุด C
ขั้นตอน 3) ตามอัลกอริทึม แผ่นดิสก์ที่ n (แผ่นที่ 2) จะถูกย้ายไปยังปลายทางที่หมุด B แล้ว
ในขั้นตอนนี้: ต้นทาง = หมุด A, ปลายทาง = หมุด B, ตัวช่วย = หมุด C
ขั้นตอน 4) ต่อไป เราจะย้ายแผ่นดิสก์ n-1 (แผ่นดิสก์ที่หนึ่ง) จากหลักช่วย C ไปยังหลักปลายทาง B ตามขั้นตอนที่สามของอัลกอริทึม
ในขั้นตอนนี้: ต้นทาง = หมุด A, ปลายทาง = หมุด B, ตัวช่วย = หมุด C
ขั้นตอน 5) หลังจากเสร็จสิ้นการเรียกซ้ำ เราจะกลับไปสู่การตั้งค่าก่อนหน้าในขั้นตอนแรกของอัลกอริธึม
ขั้นตอน 6) ในขั้นตอนที่สอง เราจะย้ายแผ่นดิสก์ 3 จากจุดเชื่อมต่อต้นทาง A ไปยังจุดเชื่อมต่อปลายทาง C
ในขั้นตอนนี้: ต้นทาง = หมุด A, ปลายทาง = หมุด C, ตัวช่วย = หมุด B
ขั้นตอน 7) ขั้นตอนต่อไปคือการย้ายดิสก์ที่เหลือจากตัวช่วย (หมุด B) ไปยังปลายทาง (หมุด C) ครั้งนี้เราจะใช้แหล่งที่มาเดิม (หมุด A) เป็นตัวช่วย
ขั้นตอน 8) เนื่องจากเราไม่สามารถเคลื่อนย้ายดิสก์สองแผ่นพร้อมกันได้ เราจึงเรียกฟังก์ชันแบบเรียกซ้ำสำหรับดิสก์แผ่นที่ 1 ตามที่เรากำหนด ขั้นตอนวิธีจุดหมายปลายทางในขั้นตอนนี้คือหมุด A
ในขั้นตอนนี้: ต้นทาง = หมุด B, ปลายทาง = หมุด A, ตัวช่วย = หมุด C
ขั้นตอน 9) การเรียกซ้ำของเราเสร็จสมบูรณ์แล้ว ตอนนี้เราจะย้ายดิสก์ 2 จากต้นทางไปยังปลายทาง
ในขั้นตอนนี้: ต้นทาง = หมุด B, ปลายทาง = หมุด C, ตัวช่วย = หมุด A
ขั้นตอน 10) ขั้นตอนสุดท้ายคือการย้ายดิสก์ที่เหลืออีก n-1 แผ่น (ดิสก์ 1) จากตัวช่วยไปยังปลายทาง
ในขั้นตอนนี้: ต้นทาง = หมุด A, ปลายทาง = หมุด C, ตัวช่วย = หมุด B
ชื่อเล่น Code สำหรับหอคอยฮานอย
START
Procedure Tower_Of_Hanoi(disk, source, dest, helper)
IF disk == 1 THEN
move disk from source to dest
ELSE
Tower_Of_Hanoi(disk - 1, source, helper, dest)
move disk from source to dest
Tower_Of_Hanoi(disk - 1, helper, dest, source)
END IF
END Procedure
รหัสโปรแกรมเข้า C++
#include <bits/stdc++.h> using namespace std; void tower_of_hanoi(int num, string source, string dest, string helper) { if (num == 1) { cout << " Move disk 1 from tower " << source << " to tower " << dest << endl; return; } tower_of_hanoi(num - 1, source, helper, dest); cout << " Move disk " << num << " from tower " << source << " to tower " << dest << endl; tower_of_hanoi(num - 1, helper, dest, source); } int main() { int num; cin >> num; printf("The sequence of moves :\n"); tower_of_hanoi(num, "I", "III", "II"); return 0; }
Output:
3 The sequence of moves : Move disk 1 from tower I to tower III Move disk 2 from tower I to tower II Move disk 1 from tower III to tower II Move disk 3 from tower I to tower III Move disk 1 from tower II to tower I Move disk 2 from tower II to tower III Move disk 1 from tower I to tower III
รหัสโปรแกรมเข้า Python
def tower_of_hanoi(n, source, destination, helper): if n == 1: print("Move disk 1 from peg", source, "to peg", destination) return tower_of_hanoi(n - 1, source, helper, destination) print("Move disk", n, "from peg", source, "to peg", destination) tower_of_hanoi(n - 1, helper, destination, source) # n = number of disks n = 3 tower_of_hanoi(n, 'A', 'B', 'C')
Output:
Move disk 1 from peg A to peg B Move disk 2 from peg A to peg C Move disk 1 from peg B to peg C Move disk 3 from peg A to peg B Move disk 1 from peg C to peg A Move disk 2 from peg C to peg B Move disk 1 from peg A to peg B
ความซับซ้อนของหอคอยแห่งฮานอย
ต่อไปนี้คือความซับซ้อนด้านเวลาและพื้นที่ของหอคอยฮานอย:
1) ความซับซ้อนของเวลา:
เมื่อมองย้อนกลับไปที่อัลกอริทึม เราจะเรียกฟังก์ชันแบบเรียกซ้ำสำหรับดิสก์ (n-1) สองครั้งต่อการเรียกแต่ละครั้ง การเรียกซ้ำ (n-1) ครั้งจะแตกออกเป็น ((n-1)-1) ครั้ง และเป็นเช่นนี้ไปเรื่อยๆ จนกว่าเราจะถึงกรณีพื้นฐานที่มีดิสก์เพียงตัวเดียว
สำหรับแผ่นดิสก์สามแผ่น:
- ดิสก์ 3 เรียกฟังก์ชันแบบเรียกซ้ำของดิสก์ 2 สองครั้ง
- ดิสก์ 2 เรียกฟังก์ชันแบบเรียกซ้ำของดิสก์ 1 สองครั้ง
- แผ่นดิสก์ที่ 1 เคลื่อนที่ด้วยเวลาคงที่ ทำให้มีเวลาในการหาคำตอบสำหรับแผ่นดิสก์ทั้งสามแผ่น
แสดงออกมาในรูปของการเกิดซ้ำ:
= 2 × (เวลาที่ใช้ในการแก้ปัญหาสำหรับแผ่นดิสก์สองแผ่น) + เวลาคงที่ในการเคลื่อนย้ายแผ่นดิสก์แผ่นที่ 3
= 2 × (2 × เวลาที่ใช้ในการแก้ปัญหาสำหรับแผ่นดิสก์แผ่นแรก + เวลาคงที่ในการเคลื่อนย้ายแผ่นดิสก์แผ่นที่ 2) + เวลาคงที่ในการเคลื่อนย้ายแผ่นดิสก์แผ่นที่ 3
= (2 × 2) × เวลาคงที่ในการเคลื่อนแผ่นดิสก์ 1 + 2 × เวลาคงที่ในการเคลื่อนแผ่นดิสก์ 2 + เวลาคงที่ในการเคลื่อนแผ่นดิสก์ 3
สำหรับดิสก์ n แผ่น จะได้ดังนี้:
2n-1 เวลาคงที่ในการเคลื่อนแผ่นดิสก์ 1 + 2n-2 × เวลาคงที่ในการเคลื่อนแผ่นดิสก์ 2 + ….
ลำดับเรขาคณิตนี้มีผลรวมเป็น O(2n – 1) ซึ่งทำให้ง่ายขึ้นเป็น โอ(2n)ซึ่งมีความซับซ้อนเชิงเวลาแบบเลขชี้กำลัง
2) ความซับซ้อนของพื้นที่:
ความซับซ้อนของพื้นที่จัดเก็บข้อมูลของ Tower of Hanoi คือ O(n) เนื่องจากการเรียกซ้ำใช้สแต็กการเรียก และความลึกสูงสุดของสแต็กเท่ากับ n ซึ่งเป็นจำนวนของดิสก์ ดังนั้นความซับซ้อนของพื้นที่จัดเก็บข้อมูลจึงเป็น O(n)
