Phạm Tuấn Anh – Tin học 5A
Artificial Intelligence
Giáo viên hướng dẫn: Thầy Ngô Hữu Phúc
I. Yêu cầu bài tập
Không gian trạng thái được mô tả là trò chơi Lines, kích thước là tùy ý(Các cạnh lớn hơn
hoặc bằng 7). Các quân trong trò chơi có 4 màu. 5 quân cùng mầu trên đường thẳng sẽ ăn được.
Hãy xây dựng chương trình cho phép tạo không gian bài toán trên. Việc di chuyển các quân theo
giải thuật tìm kiếm theo chiều sâu(Depth first search). Chương trình cho phép mô tả các bước đã
chọn và đường đi của quân trong trò chơi. Cho phép tính điểm với người chơi.
II. Môi trường phát triển
- .Net Framework
- Ngôn ngữ lập trình: C#
III. Các chức năng của chương trình
1. Cho phép khởi tạo trò chơi mới với 6 quân ngẫu nhiên trên bảng
2. Cho phép người chơi lựa chọn cấp độ chơi
3. Chức năng cho phép người chơi quay lại bước đi trước
4. Chức năng tính toán điểm
5. Chức năng Save/Load
IV. Thuật toán tìm kiếm theo chiều sâu(Depth first search)
Ý tưởng chính của thuật toán có thể trình bày như sau. Ta sẽ bắt đầu tìm kiếm từ một đỉnh
v
0
nào đó của đồ thị. Sau đó chọn u là một đỉnh tuỳ ý kề với v
0
và lặp lại quá trình đối với u. Ở
bước tổng quát, giả sử ta đang xét đỉnh v. Nếu như trong số các đỉnh kề với v tìm được đỉnh w là
chưa được xét thì ta sẽ xét đỉnh này (nó sẽ trở thành đã xét) và bắt đầu từ nó ta sẽ bắt đầu quá
trình tìm kiếm còn nếu như không còn đỉnh nào kề với v là chưa xét thì ta nói rằng đỉnh này đã
duyệt xong và quay trở lại tiếp tục tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v (nếu v=v
0
,

phức tạp tính toán của thuật toán là O(n+m).
Ví dụ. Xét đồ thị cho trong hình 1 gồm 13 đỉnh, các đỉnh được đánh số từ 1 đến 13 như sau:
Hình 1
Phạm Tuấn Anh – Tin học 5A
Khi đó các đỉnh của đồ thị được đánh số lại theo thứ tự chúng được thăm theo thủ tục tìm
kiếm theo chiều sâu mô tả ở trên như hình 2. Giả thiết rằng các đỉnh trong danh sách kề của đỉnh
v (Ke(v)) được sắp xếp theo thứ tự tăng dần của chỉ số.
Hình 2. Chỉ số mới (trong ngoặc) của các đỉnh được đánh lại theo thứ tự chúng được thăm trong
thuật toán tìm kiếm theo chiều sâu.
Thuật toán tìm kiếm theo chiều sâu trên đồ thị vô hướng trình bày ở trên dễ dàng có thể
mô tả lại cho đồ thị có hướng. Trong trường hợp đồ thị có hướng, thủ tcụ DFS(v) sẽ cho phép
thăm tất cả các đỉnh u nào mà từ v có đường đi đến u. Độ phức tạp tính toán của htuật toán là
O(n+m).
V. Mô tả chương trình
Phạm Tuấn Anh – Tin học 5A
Phạm Tuấn Anh – Tin học 5A
VI. Tài liệu tham khảo
- CÁC GIẢI PHÁP LẬP TRÌNH C# - Nguyễn Ngọc Bình Phương – Thái Thanh Phong
- Toán rời rạc – Nguyễn Đức Nghĩa – Đại học BKHN
- Lý thuyết đồ thị và ứng dụng - Đặng Huy Ruận, Nxb KHKT