timon_bumpa
New Member
Download miễn phí Luận văn Thuật toán Frame – Stewart giải bài toán tháp Hà Nội tổng quát
MỤC LỤC
Trang
MỤC LỤC
LỜI NÓI ĐẦU . 2
Chương 1 . 4
TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI . 4
§1. Lịch sử trò chơi Tháp Hà Nội . 4
§2. Sơ lược về bài toán tháp Hà Nội tổng quát, các bài toán cải biên và
các vấn đề toán học liên quan . 15
Chương 2: TRÒ CHƠI THÁP HÀ NỘI. 21
§1 Trò chơi tháp Hà Nội và thuật giải đệ qui. 21
§2 Giải bài toán tháp Hà Nội bằng biểu diễn trong hệ đếm cơ số 2 . 26
§3 Đồ thị Hà Nội. 34
§4 Giải bài toán Tháp Hà Nội trên máy tính . 38
Chương 3: BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC (Trò chơi
Reve-The Reve’s Puzzle) . 39
§1 Trò chơi Tháp Hà Nội với bốn cọc . 39
§2 Tính số bước chuyển tối ưu trong trò chơi Tháp Hà Nội với bốn cọc. 43
Chương 4: BÀI TOÁN THÁP HÀ NỘI TỔNG QUÁT. 52
§1 Tính số ()pSntrong thuật toán Frame-Stewart cho trò chơi Tháp
Hà Nội tổng quát . 52
§2 Đánh giá ()pSn. 68
§3 Sự tương đương của một số thuật toán giải bài toán Tháp Hà Nội
tổng quát. 70
KẾT LUẬN . 78
TÀI LIỆU THAM KHẢO . 79
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Đĩa thứ 7 và đĩa thứ 8 cũng là 0, do đó nó nằm trênđĩa số 6, trên cọc giữa.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
34
Bước
8
22 1 11111111
: Đĩa lớn nhất là 1, do đó nó nằm trên cọc phải
(cọc đích). Mọi đĩa khác cũng là 1, do đó chúng được đặt lên trên đĩa lớn
nhất. Vậy mọi đĩa nằm trên cọc đích và trò chơi kết thúc.
§3 Đồ thị Hà Nội
3.1 Đồ thị Hà Nội
Trò chơi Tháp Hà Nội có thể biểu diễn như một đồ thị không có hướng.
Các đỉnh biểu thị phân bố của các đĩa và các cạnh biểu thị chuyển động của
các đĩa.
Với một đĩa, đồ thị là một tam giác:
Với hai đĩa, đồ thị là ba tam giác được sắp xếp thành một tam giác lớn:
Các nút tại các đỉnh của tam giác phía ngoài cùng biểu thị các phân bố
với mọi đĩa trên cùng một cọc.
Với
1n
đĩa, ta lấy đồ thị của
n
đĩa và thay mỗi tam giác nhỏ với đồ thị
của hai đĩa.
Đồ thị cho ba đĩa có dạng:
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
35
1) Gọi các cọc là A, B, C.
2) Liệt kê các vị trí của các đĩa từ trái sang phải theo chiều tăng của kích
thước.
Các cạnh của các tam giác ngoài biên biểu thị con đường ngắn nhất để
chuyển tháp từ một cọc này sang cọc khác. Cạnh ở giữa của các biên của tam
giác lớn nhất biểu thị chuyển động của đĩa lớn nhất. Cạnh ở giữa của các biên
của mỗi tam giác nhỏ hơn tiếp theo biểu thị chuyển động của mỗi đĩa nhỏ hơn
tiếp theo. Các cạnh của tam giác nhỏ nhất biểu thị chuyển động của đĩa nhỏ
nhất.
Đồ thị của trò chơi tháp Hà Nội có liên quan mật thiết với tam giác
Sierpinski (Sierpiński Triangle) hay còn được gọi là thảm Sierpinski.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
36
Đồ thị của trò chơi với
n
đĩa sẽ có
3n
nút. Mỗi nút có ba cạnh đi tới nút
khác, ngoại trừ ba nút ở góc chỉ có hai cạnh. Luôn luôn có thể chuyển đĩa nhỏ
nhất sang một trong hai cọc khác. Và có thể chuyển một đĩa giữa hai cọc này
ngoại trừ trường hợp khi tất cả các đĩa nằm trên một cọc. Các nút góc biểu thị
ba trường hợp, khi mọi đĩa nằm trên một cọc. Biểu đồ cho
n
đĩa nhận được
từ biểu đồ cho
1n
đĩa bằng cách copy ba lần-mỗi copy biểu thị mọi trạng
thái và chuyển động của các đĩa nhỏ hơn cho một vị trí riêng của một đĩa mới
lớn hơn và cùng với chúng tại các góc với ba cạnh mới biểu thị chỉ có ba khả
năng chuyển đĩa lớn nhất. Do đó kết quả sẽ có 13n nút và vẫn có ba góc với
hai cạnh.
Khi số đĩa được thêm vào, đồ thị biểu diễn trò chơi sẽ tạo thành một hình
Fractal, thảm Sierpinski. Rõ ràng rằng phần lớn các vị trí trong trò chơi sẽ
không bao giờ đạt được nếu sử dụng lời giải ngắn nhất. Thật vậy, nếu các vị
thầy tu trong truyền thuyết sử dụng lời giải dài nhất có thể (không trở lại vị trí
cũ nào) thì cần 643 1 lần chuyển, nhiều hơn 2310 năm.
3.2 Bài toán Tháp Hà Nội và đƣờng Hamilton
Đường Hamilton khép kín cho ba đĩa là:
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
37
Đồ thị chỉ ra rằng:
• Từ mỗi phân bố bất kì của các đĩa, tồn tại một con đường ngắn nhất
chuyển mọi đĩa từ một trong ba cọc sang cọc khác.
• Giữa mỗi cặp phân bố bất kì tồn tại một hay hai đường ngắn nhất khác
nhau.
• Từ mỗi phân bố bất kì của các đĩa, tồn tại một hay hai đường dài nhất
không tự cắt chuyển mọi đĩa tới một trong ba cọc.
• Giữa mọi cặp của các phân bố bất kì của các đĩa tồn tại một hay hai
đường dài nhất không tự cắt.
• Gọi
nN
là số các đường không tự cắt để chuyển tháp
n
đĩa từ cọc này
sang cọc khác. Khi ấy:
1 2N
;
2 3
1n n nN N N
. Thí dụ,
795
8 1.5656 10N
.
Đồ thị
nH
tương ứng với các chuyển động được phép trong bài toán
tháp Hà Nội. Hình trên chỉ ra một số đồ thị Hà Nội với
1,2,3,4n
. Đồ thị
Hà Nội có thể xây dựng bằng cách chọn các đỉnh làm các hệ số nhị thức lẻ
của tam giác Pascan được tính trên các số nguyên từ 0 đến 2 1n và vẽ các
đỉnh khi các hệ số là kề nhau theo đường chéo hay theo chiều ngang (xem
Pool, 1994, [15]).
Đồ thị
nH
có
3n
đỉnh và 3 3 1
2
n cạnh. Mỗi đồ thị Hà Nội có duy nhất
một đường Hamilton (tương ứng, mỗi đồ thị Hà Nội có chính xác hai đường
tròn Hamilton có hướng khác nhau).
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
38
§4 Giải bài toán Tháp Hà Nội trên máy tính
Code (mã) thể hiện thuật giải đệ qui bài toán Tháp Hà Nội:
def Hanoi(n, A, C, B):
if n == 1:
print 'Move the plate from', A, 'to', C
else:
Hanoi(n - 1, A, B, C)
print 'Move the plate from', A, 'to', C
Hanoi(n - 1, B, C, A)
Thuật giải đệ qui bài toán Tháp Hà Nội trên ngôn ngữ Pascal:
VAR n: Integer;
Procedure chuyen(sodia: Integer; CotNguon: Char; CotDich: Char; CotTG:
Char);
Begin
If sodia>0 then begin
chuyen(sodia-1, CotNguon, CotTG, CotDich);
Writeln(CotNguon,'->',CotDich); { Dia lon nhat hien tai }
chuyen(sodia-1, CotTG, CotDich, CotNguon)
End;
End;
BEGIN
Write('Hay nhap so dia: '); Readln(n);
chuyen(n,'A','C','B');//Thực hiện chuyển từ cột A sang cột C với cột B làm
trung gian
Readln;
END.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
39
Chƣơng 3
BÀI TOÁN THÁP HÀ NỘI VỚI BỐN CỌC
(Trò chơi Reve-The Reve’s Puzzle)
§1 Trò chơi Tháp Hà Nội với bốn cọc
1.1 Trò chơi Tháp Hà Nội với bốn cọc
Trong Chương 2 chúng ta đã giải bài toán Tháp Hà Nội với ba cọc và
n
đĩa. Nó có thể giải được dễ dàng theo thuật giải đệ qui. Hơn nữa, có thể biết
chính xác số lần chuyển tối ưu cho bài toán với
n
đĩa là 2 1n . Như vậy, một
bài toán với thuật giải đơn giản và tối ưu cũng có thể có độ phức tạp tính toán
lớn (thời gian mũ), do đó có thể không giải được trong thời gian thực tế.
Một mở rộng tự nhiên của trò chơi Tháp Hà Nội là trò chơi Tháp Hà Nội
với bốn hay nhiều cọc (bài toán Tháp Hà Nội tổng quát). Như là sự tiếp nối
của chương trước và chuẩn bị cho chương sau, chương này nghiên cứu bài
toán Tháp Hà Nội cho bốn cọc. Bài toán này lần đầu tiên được Dudeney
(1902) đặt ra và gọi tên là The Reve’s Puzzle (xem [7]). Gần đây, nhiều kết
quả thú vị cũng đã được phát hiện cho bài toán này, các kết quả này là cơ sở
để phát triển nghiên cứu bài toán Tháp Hà Nội tổng quát, vì vậy nó xứng đáng
được xem xét tỉ mỉ trong một chương riêng, mặc dù, để thuận tiện, nhiều kết
quả trong chương này cũng được trình bày cho bài toán nhiều cọc .
Bài toán 2 (Bài toán Tháp
Hà Nội với bốn cọc) Có bốn
cọc được đánh số
1P
,
2P
,
3P
,
4P
. Cọc
1P
được gọi là cọc
nguồn. Ban đầu cọc nguồn
chứa
n
đĩa có lỗ ở giữa và
kích thước to
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
40
nhỏ khác nhau được xếp theo thứ tự “đĩa to ở dưới, đĩa nhỏ ở trên” . Bài toán
đặt ra là phải chuyển tất cả
n
đĩa từ cọc nguồn sang một trong các cọc
2P
,
3P
,
4P
, sắp xếp cũng theo thứ tự “đĩa to ở dưới, đĩa nhỏ ở trên”. Mỗi lần chỉ được
chuyển một đ...