Nội Dung Chính
(Trang 68)
| Sau bài này em sẽ:
|
|
Chắc em đã nghe nói nhiều bài toán tìm đường đi trong mê cung. Nếu áp dụng kĩ thuật duyệt quay lui cho bài toán này thì làm thế nào để tìm ra các bước đi tiếp theo từ một vị trí? |
NHIỆM VỤ
Giải bài toán mê cung
Giả sử có một mê cung hình chữ nhật gồm m hàng, n cột được định nghĩa bằng một tệp đang văn bản có tên maze.inp, trong đó các ô 0 là ô được đi, ô 1 tương ứng với tường và không được đi. Tại một vị trí có thể chọn một trong bốn hướng (đi tiếp lên, xuống, trái, phải). Giả sử vị trí xuất phát là ô bên trái phía trên, hãy tìm một đường đi trên bên phải phía dưới để thoát khỏi mê cung. Nếu tìm ra nghiệm thì in ra đường đi dưới dạng: bảng trong đó vết của đường đi gồm các ô 1. được thể hiện bằng số 1, các ô còn lại là số 0. Kết quả được thể hiện trên màn hình và ghi ra tệp maze.out. Ví dụ một thể hiện của dữ liệu đầu vào và ra như bảng bên.
| maze.inp | maze.out |
| 0 1 1 0 1 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 | 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 |
Hướng dẫn:
Phân tích: Ý tưởng thuật toán như sau: quá trình tìm đường được bắt đầu tại vị trí bên phải phía trên. Tại mỗi vị trí, thuật toán thử đi tiếp một bước theo một trong các hướng lên, xuống, trái, phải. Nếu không đi được hoặc ô hiện tại không hợp lệ trả lại giá trị False và quay lui về bước đi trước đó. Chúng ta sẽ thiết lập mảng maze để lưu dữ liệu đầu vào của mê cung. Thiết lập mảng sol để lưu vết đường đi trong mê cung. Ban đầu mảng sol sẽ gồm toàn số 0.
Hàm quay lui để tìm đường đi chính là solveMaze(maze, m, n, x, y, sol), mê cung có m hàng, n cột, x, y là toạ độ của ô hiện thời để tìm đường đi tiếp. Hàm sẽ trả lại True nếu từ vị trí hiện thời (x, y) tìm được đường đi thoát khỏi mê cung, ngược lại sẽ trả về False. Sau đây là một mã mô tả nhanh hàm solveMaze():
1 def solveMaze(maze, m, n, x, y, sol):
2 if <(x,y) nằm ở vị trí đích và rộng>:
3 đặt sol[x][y] = 1 # thiết lập bước đi và kết thúc
4 return True
5 if <ô (x,y) nằm trong mê cung và đang rỗng>:
6 if <ô (x,y) đã từng được đi qua trước đó>:
7 return False
8 Đặt sol[x][y] = 1 # đánh dấu đã đi qua ô này
9 Lần lượt thử đi tiếp sang các ô trái, phải, trên, dưới bằng cách gọi đệ quy hàm solveMaze()
10 Nếu thành công thì
(Trang 69)
11 return True
12 # Tới đây quay lui vì các bước đi tiếp ở trên đều thất bại
13 sol[x][y] = 0 # thiết lập trạng thái trước khi thực hiện solveMaze()
14 return False
15 else # ô (x,y) năm ngoài mê cung hoặc là tường
16 return False
Chương trình chính có dạng như sau:
1 maze = mảng được đọc từ tệp maze.inp
2 m, n = số hàng và số cột của maze
3 khởi tạo ma trận sol kính thước giống maze với các phần tử đều bằng 0 để chứa đường đi cần tìm
4 solveMaze(maze, m, n, 0, 0, solve) # gọi hàm solve tìm đường từ vị trí góc trái bên trên
5 Thông báo kết quả
Sau đây là toàn bộ chương trình:
Chương trình
Chương trình chính có dạng như sau:
1 # Hàm readmaze/writemaze để đọc/ghi mê cung
2 def readmaze():
3 file = open("maze.inp")
4 maze = []
5 for row in file:
6 h = [int(x) for x in row.split()] Đọc từng dòng từ tệp maze.inp rồi chèn vào mảng maze
7 maze.append(h)
8 file.close()
9 return maze
10 def writemaze(outmaze):
11 f = open("maze.out", "w")
12 for i in outmaze:
13 for j in i:
14 print(j, file = f, end =" ") Ghi từng dòng mê cung ra tệp
15 print(file = f)
16 f.close()
17
18 # Hàm tìm đường đi trong mê cung theo phương pháp quay lui
19 def solveMaze(maze, m, n, x, y, sol):
20 # Nếu đã đến ô bên phải phía dưới đã tìm được đường và kết thúc
21 if x == n - 1 and y == m - 1 and maze[y][x] == 0:
22 sol[y][x] = 1
23 return True
24 # Nếu ô x,y này rỗng thì tìm đường đi tiếp
25 if x >= 0 and x <n and y >= 0 and y<m and maze[y][✗] == 0:
26 if sol[y][x] == 1:
27 return False
28 sol[y][x] = 1 # Tạm đánh dấu đường ở ô này
29 if solveMaze(maze, m, n, x + 1, y, sol): Thử đi tiếp theo các hướng lên xuống trái phải bằng cách gọi đệ quy hàm solveMaze
30 return True
31 if solveMaze(maze, m, n, y + 1, y, sol):
32 return True
33 if solveMaze(maze, m, n, x, x - 1, sol):
34 return True
35 if solveMaze(maze, m, n, x, y - 1, sol):
36 return True
37 sol[y][x] = 0 # Quay lui, thiết lập trạng thái ban tại ô (x, y)
38 return False
39 else:
40 return False
41 # Chương trình chính
42 maze = readmaze()
43 m = len(maze)
44 n = len(maze)
45 print("Kích thước mê cung:",m, "hàng",n, "cột")
46 sol = [[0 for j in range(n)] for i in range(m)]
47 if solveMaze(maze, m, n, 0, 0, sol):
48 print("Không tồn tại đường đi")
49 else:
50 writemaze(sol)
51 print("Đường đi khỏi mê cung:")
52 for i in sol:
53 for j in i:
54 print(str(j) + " ", end = "")
55 print() # in kí tự xuống dòng
Giải thích:
– Hàm readmaze(outmaze) dùng để đọc dữ liệu từ tệp maze.inp, kết quả thông tin mê cung đưa vào mảng 2 chiều maze.
– Hàm writemaze(outmaze) ghi mảng kết quả outmaze ra tệp maze.out.
– Nếu ô hiện tại chưa là đích, tại dòng 25 kiểm tra xem ô này có được phép đi không, nếu có thì gán 1 tại ô hiện thời (dòng 27) và thử đi tiếp một bước theo một trong các hướng (lên, xuống, trái, phải). Nếu không đi được hoặc ô hiện tại không hợp lệ trả lại giá trị False và quay lui về bước đi trước đó. Trước khi quay lui thì gán 0 tại ô hiện thời tại dòng 37.
– Từ dòng 46, khởi tạo biến sol để lưu nghiệm và gọi hàm solveMaze để giải.
LUYỆN TẬP
1. Nếu sửa yêu cầu đề bài đặt vị trí xuất phát tại ô giữa của mê cung (ví dụ vị trí m/2, n/2), vị trí thoát của mê cung là ô trái trên hoặc phải dưới của mê cung thì cần sửa chương trình trình thế nào?
2. Trên dữ liệu đầu ra của bài toán chưa thể hiện thông tin của các ô là tường. Hãy sửa lại chương trình để trên dữ liệu đầu ra các ô là tường sẽ được đánh dấu bằng "x".
VẬN DỤNG
1. Cải tiến nhiệm vụ thực hành để chương trình in ra màn hình tất cả các đường đi để thoát ra khỏi mê cung.
2. Bài toán xếp Hậu tổng quát m hàng n cột trong đó m và n là các số tự nhiên bất kì (m ≥ n).
3. Bài toán "Mã đi tuần" được phát biểu như sau: cho vị trí ban đầu của quân mã trên bàn cờ vua 8×8, hãy tìm một hành trình của quân mã sao cho nó đi hết các ô bàn cờ mà không đi qua bất kì ô nào hai lần. Hãy dùng chiến lược quay lui để tìm lời giải cho bài toán này.
Các Bài Học Khác
Bình Luận
Để Lại Bình Luận Của Bạn