KHOA CƠNG NGHỆ THƠNG TIN

MƠN: TRÍ TUỆ NHÂN TẠO
Đề Tài: Bài tốn qua sơng

SINH VIÊN THỰC HIỆN

GIẢNG VIÊN HƯỚNG DẪN:

Ngành: Hệ thống thông tin

1


LỜI MỞ ĐẦU
Trí tuệ là gì? Theo từ điển Bách khoa tồn thư Webster: Trí tuệ là khả năng phản
ứng thích hợp lại những tình huống mới thơng qua điều chỉnh hành vi một cách thích
hợp. Hiểu rõ mối liên hệ giữa các sự kiện của thế giới bên ngoài nhằm đưa ra những
hành vi phù hợp để đạt được mục đích.
Vậy trí tuệ nhân tạo là gì? Thuật ngữ trí tuệ nhân tạo (Artifical Intellegence)
được Jonh Mc Carthly đưa ra trong hội thảo ở Darthouth vào mùa hè năm 1956. Đã có
rất nhiều định nghĩa khác nhau về trí tuệ nhân tạo. Với trí tuệ nhân tạo, máy tính đã
giúp con người giải quyết các vấn đề một cách thơng minh nhất. Ta sẽ tìm hiểu một số
phương pháp giải quyết vấn đề cơ bản.
Trong đề tài này sẽ thực hiện sử dụng các thuật toán để giải quyết bài tốn qua
sơng. Q trình thực hiện đề tài khơng thể tránh khỏi những sai sót. Rất mong nhận
được những ý kiến đóng góp và đánh giá của các giảng viên.

Xin chân thành cảm ơn!

2

MEN

3


LỜI MỞ ĐẦU...............................................................................................................................................2
CHƯƠNG 1: TÌM HIỂU VỀ TRÍ TUỆ NHÂN TẠO................................................................................5
I. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO...............................................................................................5
1. Mở đầu.........................................................................................................................................................5
2. Tri thức.........................................................................................................................................................6
3. Biểu diễn tri thức.........................................................................................................................................6
II. CÁC PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC TRÊN MÁY TÍNH.................................................7
1. Logic mệnh đề.............................................................................................................................................7
2. Logic vị từ...................................................................................................................................................8
3. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh).................................................................................11
4. Biểu diễn tri thức sử dụng mạng ngữ nghĩa..............................................................................................13
III.

CÁC TRƯỜNG PHÁI CỦA TRÍ TUỆ NHÂN TẠO....................................................................15

1. Trí tuệ nhân tạo truyền thống....................................................................................................................15
2. Trí tuệ nhân tạo tính tốn..........................................................................................................................15
CHƯƠNG 2: BÀI TỐN QUA SƠNG......................................................................................................17
I.

TỔNG QUAN VỀ ĐỀ TÀI............................................................................................................17
1. Giới thiệu đề tài.........................................................................................................................................17


II.

PHÂN TÍCH ĐỀ TÀI.....................................................................................................................18

III.

CÀI ĐẶT THUẬT TỐN..............................................................................................................20

1. Ý tưởng......................................................................................................................................................20
2. Xây dựng thuật toán..................................................................................................................................20
IV

KẾT QUẢ.......................................................................................................................................32

V.

KẾT LUẬN.....................................................................................................................................33
1. Hướng phát triển của đề tài.......................................................................................................................33
2. Đánh giá.....................................................................................................................................................33

4


CHƯƠNG 1: TÌM HIỂU VỀ TRÍ TUỆ NHÂN TẠO
I. TỔNG QUAN VỀ TRÍ TUỆ NHÂN TẠO
1. Mở đầu
Trí tuệ nhân tạo (hay AI: Artificial Intelligence), là nỗ lực tìm hiểu những yếu tố
trí tuệ. Lý do khác để nghiên cứu lĩnh vực này là cách để ta tự tìm hiểu bản thân chúng
ta. Không giống triết học và tâm lý học, hai khoa học liên quan đến trí tuệ, cịn AI cố
gắng thiết lập các các yếu tố trí tuệ cũng như tìm biết về chúng. Lý do khác để nghiên

cứu AI là để tạo ra các thực thể thông minh giúp ích cho chúng ta. AI có nhiều sản
phẩm quan trọng và đáng lưu ý, thậm chí ngay từ lúc sản phẩm mới được hình thành.
Mặc dù khơng dự báo được tương lai, nhưng rõ ràng máy tính điện tử với độ thơng
minh nhất định đã có ảnh hưởng lớn tới cuộc sống ngày nay và tương lai phát triển của
văn minh nhân loại.
Chế tạo được những cỗ máy thơng minh như con người (thậm chí thơng minh
hơn con người) là một ước mơ cháy bỏng của loài người từ hàng ngàn năm nay. Năng
lực máy tính ngày càng mạnh mẽ là một điều kiện hết sức thuận lợi cho trí tuệ nhân
tạo. Điều này cho phép những chương trình máy tính áp dụng các thuật giải trí tuệ
nhân tạo có khả năng phản ứng nhanh và hiệu quả hơn trước. Mặc dù mục tiêu tối
thượng của ngành Trí tuệ nhân tạo là xây dựng một chiếc máy có năng lực tư duy
tương tự như con người nhưng khả năng hiện tại của tất cả các sản phẩm Trí tuệ nhân
tạo vẫn còn rất khiêm tốn so với mục tiêu đã đề ra. Tuy vậy, ngành khoa học mới mẻ
này vẫn đang tiến bộ mỗi ngày và đang tỏ ra ngày càng hữu dụng trong một số cơng
việc địi hỏi trí thơng minh của con người.
Xây dựng trí tuệ nhân tạo là tìm cách biểu diễn tri thức, tìm cách vận dụng tri
thức để giải quyết vấn đề và tìm cách bổ sung tri thức bằng cách "phát hiện" tri thức từ
các thơng tin sẵn có (máy học).

5


2. Tri thức
Tri thức là kết quả của quá trình nhận thức, học tập và lập luận
Người ta thường phân loại tri thức ra làm các dạng như sau:
 Tri thức sự kiện: là các khẳng định về một sự kiện, khái niệm nào đó (trong
một phạm vi xác định).
 Tri thức thủ tục: thường dùng để diễn tả phương pháp, các bước cần tiến
hành, trình tự hay ngắn gọn là cách giải quyết một vấn đề. Thuật toán, thuật giải là
một dạng của tri thức thủ tục.

 Tri thức mô tả: cho biết một đối tượng, sự kiện, vấn đề, khái niệm, ... được
thấy, cảm nhận, cấu tạo như thế nào (một cái bàn thường có 4 chân, con người có 2
tay, 2 mắt, ...).
 Tri thức Heuristic: là một dạng tri thức cảm tính. Các tri thức thuộc loại này
thường có dạng ước lượng, phỏng đốn, và thường được hình thành thơng qua kinh
nghiệm.
3. Biểu diễn tri thức
Biểu diễn tri thức là cách thể hiện tri thức trong máy dưới dạng sao cho bài tốn
có thể được giải tốt nhất. Biểu diễn tri thức trong máy phải:
+ Thể hiện được tất cả các thông tin cần thiết.
+ Cho phép tri thức mới được suy diễn từ tập các sự kiện và luật suy diễn.
+ Cho phép biểu diễn các nguyên lý tổng quát và các tình huống đặc trưng.
+ Bắt lấy được ý nghĩa ngữ nghĩa phức tạp.
+ Cho phép lý giải ở mức tri thức cao hơn.
6


II. CÁC PHƯƠNG PHÁP BIỂU DIỄN TRI THỨC TRÊN MÁY TÍNH
Con người sống trong mơi trường có thể nhận thức được thế giới nhờ các giác
quan (tai, mắt và các giác quan khác), sử dụng các tri thức tích luỹ được và nhờ khả
năng lập luận, suy diễn, con người có thể đưa ra các hành động hợp lý cho công việc
mà con người đang làm. Một mục tiêu của Trí tuệ nhân tạo ứng dụng là thiết kế các
Agent thơng minh (intelligent agent) cũng có khả năng đó như con người. Chúng ta có
thể hiểu Agent thơng minh là bất cứ cái gì có thể nhận thức được mơi trường thông
qua các bộ cảm nhận (sensors) và đưa ra hành động hợp lý đáp ứng lại môi trường
thông qua bộ phận hành động (effectors). Các robots, các softbot (software robot), các
hệ chuyên gia, ... là các ví dụ về Agent thơng minh. Các Agent thơng minh cần phải có
tri thức về thế giới hiện thực mới có thể đưa ra các quyết định đúng đắn.
Cơ sở tri thức là một tập hợp các tri thức được biểu diễn dưới dạng nào đó. Mỗi
khi nhận được các thơng tin đưa vào, Agent cần có khả năng suy diễn để đưa ra các

câu trả lời, đưa ra các hành động hợp lý. Nhiệm vụ này được thực hiện bởi bộ suy diễn
thành phần cơ bản khác của các hệ tri thức. Như vậy, hệ tri thức bao hàm một CSTT
và được trang bị một thủ tục suy diễn. Mỗi khi tiếp nhận các sự kiện từ môi trường,
thủ tục suy diễn thực hiện quá trình liên kết các sự kiện với các tri thức trong CSTT để
rút ra các câu trả lời, hoặc các hành động hợp lý mà Agent cần thực hiện. Khi thiết kế
một Agent giải quyết vấn đề nào đó thì CSTT sẽ chứa các tri thức về đối tượng cụ thể
đó. Để máy tính có thể sử dụng, xử lý tri thức, cần biểu diễn tri thức dưới dạng thuận
tiện. Đó là mục tiêu của biểu diễn tri thức.
1. Logic mệnh đề
Đây có lẽ là kiểu biểu diễn tri thức đơn giản nhất và gần gũi nhất đối với chúng
ta.
Mệnh đề là một khẳng định, một phát biểu mà giá trị của nó chỉ có thể hoặc là
đúng hoặc là sai.
7


Giá trị của mệnh đề không chỉ phụ thuộc vào bản thân mệnh đề đó. Có những
mệnh đề mà giá trị của nó ln đúng hoặc sai bất chấp thời gian nhưng cũng có những
mệnh đề mà giá trị của nó lại phụ thuộc vào thời gian, khơng gian và nhiều yếu tố
khác quan khác. Chẳng hạn như mệnh đề: "Con người không thể nhảy cao hơn 5m với
chân trần" là đúng khi ở trái đất, còn ở những hành tinh có lực hấp dẫn yếu thì có thể
sai.Ta ký hiệu mệnh đề bằng những chữ cái la tinh như a, b, c, ...
Có 3 phép nối cơ bản để tạo ra những mệnh đề mới từ những mệnh đề cơ sở là
phép hội, giao và phủ định. Bên cạnh các thao tác tính ra giá trị các mệnh đề phức từ
giá trị những mệnh đề con, chúng ta có được một cơ chế suy diễn như sau:


Modus Ponens: Nếu mệnh đề A là đúng và mệnh đề A => B là

đúng thì giá trị của B sẽ là đúng.


Modus Tollens: Nếu mệnh đề A => B là đúng và mệnh đề B là sai
thì giá trị của A sẽ là sai.
2. Logic vị từ
Biểu diễn tri thức bằng mệnh đề gặp phải một trở ngại cơ bản là ta không thể
can thiệp vào cấu trúc của một mệnh đề. Hay nói một cách khác là mệnh đề khơng có
cấu trúc . Điều này làm hạn chế rất nhiều thao tác suy luận . Do đó, người ta đã đưa
vào khái niệm vị từ và lượng từ (- với mọi, - tồn tại) để tăng cường tính cấu trúc của
một mệnh đề.
Trong logic vị từ, một mệnh đề được cấu tạo bởi hai thành phần là các đối tượng
tri thức và mối liên hệ giữa chúng (gọi là vị từ). Các mệnh đề sẽ được biểu diễn dưới
dạng:
Vị từ (<đối tượng 1>, <đối tượng 2>, …, <đối tượng n>)
Như vậy để biểu diễn vị của các trái cây, các mệnh đề sẽ được viết thành:


Cam có vị Ngọt. Vị (Cam, Ngọt)
8





Cam có màu Xanh. Màu (Cam, Xanh)
...

Với vị từ, ta có thể biểu diễn các tri thức dưới dạng các mệnh đề tổng quát, là
những mệnh đề mà giá trị của nó được xác định thơng qua các đối tượng tri thức cấu
tạo nên nó.
Chẳng hạn tri thức: "A là bố của B nếu B là anh hoặc em của một người con của

A" có thể được biểu diễn dưới dạng vị từ như sau:


Bố (A, B) = Tồn tại Z sao cho: Bố (A, Z) và (Anh (Z, B) hoặc Anh

(B, Z))
Trong trường hợp này, mệnh đề Bố (A, B) là một mệnh đề tổng quát. Như vậy
nếu ta có các mệnh đề cơ sở là:



Bố ("An", "Bình") có giá trị đúng (An là bố của Bình)
Anh ("Tú", "Bình") có giá trị đúng (Tú là anh của Bình)

Thì mệnh đề Bố ("An", "Tú") sẽ có giá trị là đúng. (An là bố của Tú).
Rõ ràng là nếu chỉ sử dụng logic mệnh đề thơng thường thì ta sẽ khơng thể tìm
được một mối liên hệ nào giữa c và a, b bằng các phép nối mệnh đề, và ¬. Từ đó, ta
cũng khơng thể tính ra được giá trị của mệnh đề c. Sở dĩ như vậy vì ta không thể thể
hiện tường minh tri thức " (A là bố của B) nếu có Z sao cho (A là bố của Z) và (Z anh
hoặc em C)" dưới dạng các mệnh đề thơng thường. Chính đặc trưng của vị từ đã cho
phép chúng ta thể hiện được các tri thức dạng tổng quát như trên.
Thêm một số ví dụ nữa để thấy rõ hơn khả năng của vị từ:
Câu cách ngơn "Khơng có vật gì là lớn nhất và khơng có vật gì là bé nhất!" có
thể được biểu diễn dưới dạng vị từ như sau:

9







LớnHơn (x, y) = x > y
NhỏHơn (x, y) = x < y
x, y: LớnHơn (y, x) và x, y: NhỏHơn (y, x)

Câu châm ngơn "Gần mực thì đen, gần đèn thì sáng" được hiểu là "chơi với bạn
xấu nào thì ta cũng sẽ thành người xấu" có thể được biểu diễn bằng vị từ như sau:


NgườiXấu (x) = y: Bạn (x, y) và NgườiXấu (y)

10


3. Biểu diễn tri thức sử dụng luật dẫn xuất (luật sinh)
a. Khái niệm
Phương pháp biểu diễn tri thức bằng luật sinh được phát minh bởi Newell và Simon
trong lúc hai ông đang cố gắng xây dựng một hệ giải bài toán tổng quát. Đây là một
kiểu biểu diễn tri thức có cấu trúc. Ý tưởng cơ bản là tri thức có thể được cấu trúc
bằng một cặp điều kiện – hành động: "NẾU điều kiện xảy ra THÌ hành động sẽ được
thi hành".
Ngày nay, các luật sinh đã trở nên phổ biến và được áp dụng rộng rãi trong nhiều hệ
thống trí tuệ nhân tạo khác nhau. Luật sinh có thể là một cơng cụ mơ tả để giải quyết
các vấn đề thực tế thay cho các kiểu phân tích vấn đề truyền thống. Trong trường hợp
này, các luật được dùng như là những chỉ dẫn (tuy có thể khơng hồn chỉnh) nhưng rất
hữu ích để trợ giúp cho các quyết định trong q trình tìm kiếm, từ đó làm giảm khơng
gian tìm kiếm. Một cách tổng qt luật sinh có dạng như sau:
P1 P2 ... Pn => Q
Tùy vào các vấn đề đang quan tâm mà luật sinh có những ngữ nghĩa hay cấu tạo khác

nhau:
Trong logic vị từ: P1, P2, ..., Pn, Q là những biểu thức logic.
Trong ngơn ngữ lập trình, mỗi một luật sinh là một câu lệnh.
IF (P1 AND P2 AND ... AND Pn) THEN Q.
Để biễu diễn một tập luật sinh, người ta thường phải chỉ rõ hai thành phần chính sau:
(1) Tập các sự kiện F (Facts)
F = { f1, f2, ... fn }

11


(2) Tập các quy tắc R (Rules) áp dụng trên các sự kiện dạng như sau:
f1 ^ f2 ^ ... ^ fi q
Trong đó, các fi, q đều thuộc F
b. Cơ chế suy luận trên các luật sinh
 Suy diễn tiến: là quá trình suy luận xuất phát từ một số sự kiện ban đầu, xác
định
các sự kiện có thể được "sinh" ra từ sự kiện này.
 Suy diễn lùi: là quá trình suy luận ngược xuất phát từ một số sự kiện ban đầu,
ta tìm kiếm các sự kiện đã "sinh" ra sự kiện này. Một ví dụ thường gặp trong thực tế là
xuất phát từ các tình trạng của máy tính, chẩn đốn xem máy tính đã bị hỏng hóc ở
đâu.
c. Ưu điểm và nhược điểm của biểu diễn tri thức bằng luật
 Ưu điểm:
Biểu diễn tri thức bằng luật đặc biệt hữu hiệu trong những tình huống hệ thống
cần đưa ra những hành động dựa vào những sự kiện có thể quan sát được. Nó có
những ưu điểm chính yếu sau đây:


Các luật rất dễ hiểu nên có thể dễ dàng dùng để trao đổi với người


dùng (vì nó

là một trong những dạng tự nhiên của ngơn ngữ).

Có thể dễ dàng xây dựng được cơ chế suy luận và giải thích từ các
luật.




Việc hiệu chỉnh và bảo trì hệ thống là tương đối dễ dàng.
Có thể cải tiến dễ dàng để tích hợp các luật mờ.
Các luật thường ít phụ thuộc vào nhau.

12


 Nhược điểm:


Các tri thức phức tạp đơi lúc địi hỏi quá nhiều (hàng ngàn) luật

sinh. Điều này sẽ làm nảy sinh nhiều vấn đề liên quan đến tốc độ lẫn quản trị hệ
thống.


Thống kê cho thấy, người xây dựng hệ thống trí tuệ nhân tạo thích

sử dụng luật sinh hơn tất cả phương pháp khác (dễ hiểu, dễ cài đặt) nên họ

thường tìm mọi cách để biểu diễn tri thức bằng luật sinh cho dù có phương pháp
khác thích hợp hơn! Đây là nhược điểm mang tính chủ quan của con người.

Cơ sở tri thức luật sinh lớn sẽ làm giới hạn khả năng tìm kiếm của
chương trình điều khiển. Nhiều hệ thống gặp khó khăn trong việc đánh giá các
hệ dựa trên luật sinh cũng như gặp khó khăn khi suy luận trên luật sinh.
4. Biểu diễn tri thức sử dụng mạng ngữ nghĩa
a. Khái niệm
Mạng ngữ nghĩa là một phương pháp biểu diễn tri thức đầu tiên và cũng là
phương pháp dễ hiểu nhất đối với chúng ta. Phương pháp này sẽ biểu diễn tri thức
dưới dạng một đồ thị, trong đó đỉnh là các đối tượng (khái niệm) còn các cung cho biết
mối quan hệ giữa các đối tượng (khái niệm) này.
Chẳng hạn: giữa các khái niệm chích chịe, chim, hót, cánh, tổ có một số mối
quan hệ như sau:





Chích chịe là một lồi chim.
Chim biết hót
Chim có cánh
Chim sống trong tổ

Các mối quan hệ này sẽ được biểu diễn trực quan bằng một đồ thị như sau:
Do mạng ngữ nghĩa là một loại đồ thị cho nên nó thừa hưởng được tất cả những
mặt mạnh của cơng cụ này. Nghĩa là ta có thể dùng những thuật toán của đồ thị trên
13



mạng ngữ nghĩa như thuật tốn tìm liên thơng, tìm đường đi ngắn nhất, … để thực
hiện

14


III. CÁC TRƯỜNG PHÁI CỦA TRÍ TUỆ NHÂN TẠO.
Trí tuệ nhân tạo (AI) chia thành hai trường phái tư duy: Trí t nhân tạo truyền
thống và trí tuệ tính tốn.
1. Trí tuệ nhân tạo truyền thống
Trí tuê nhân tạo truyền thống hầu như bao gồm các phương pháp hiện được
phân loại là các phương pháp học máy (machine learning), đặc trưng bởi hệ hình thức
(formalism) và phân tích thống kê. Nó cịn được biết với các tên Trí t nhân tạo biểu
tượng, Trí tuê nhân tạo logic, Trí tuê nhân tạo ngăn nắp (neat AI) và Trí tuê nhân tạo
cổ điển (Good Old Fashioned Artificial Intelligence). (Xem thêm ngữ nghĩa học.) Các
phương pháp gồm có:
 Hệ chuyên gia: áp dụng các khả năng suy luận để đạt tới một kết luận.
Một hệ chuyên gia có thể xử lý các lượng lớn thông tin đã biết và đưa
ra các kết luận dựa trên các thơng tin đó. Clippy chương trình trợ giúp
có hình cái kẹp giấy của Microsoft Office là một ví dụ. Khi người
dùng gõ phím, Clippy nhận ra các xu hướng nhất định và đưa ra các
gợi ý.
 Lập luận theo tình huống.
 Mạng Bayes.
2. Trí tuệ nhân tạo tính tốn
Trí tuệ tính tốn nghiên cứu việc học hoặc phát triển lặp (ví dụ: tinh chỉnh tham
số trong hệ thống, chẳng hạn hệ thống connectionist). Việc học dựa trên dữ liệu kinh
nghiệm và có quan hệ với Trí tuệ nhân tạo phi ký hiệu, Trí tuê nhân tạo lộn xộn
(scruffy AI) và tính tốn mềm (soft computing). Các phương pháp chính gồm có:
 Mạng neural: các hệ thống mạnh về nhận dạng mẫu (pattern

recognition).
 Hệ mờ (Fuzzy system): các kỹ thuật suy luận không chắc chắn, đã
được sử dụng rộng rãi trong các hệ thống công nghiệp hiện đại và các
hệ thống quản lý sản phẩm tiêu dùng.
 Tính tốn tiến hóa (Evolutionary computation): ứng dụng các khái
niệm sinh học như quần thể, biến dị và đấu tranh sinh tồn để sinh các
15


lời giải ngày càng tốt hơn cho bài toán. Các phương pháp này thường
được chia thành các thuật toán tiến hóa (ví dụ thuật tốn gene) và trí
tuệ bầy đàn (swarm intelligence) (chẳng hạn hệ kiến).
 Trí tuê nhân tạo dựa hành vi (Behavior based AI): một phương pháp
module để xây dựng các hệ thống Trí tuê nhân tạo bằng tay.
Người ta đã nghiên cứu các hệ thống thông minh lai (hybrid intelligent system),
trong đó kết hợp hai trường phái này. Các luật suy diễn của hệ chuyên gia có thể được
sinh bởi mạng neural hoặc các luật dẫn xuất (production rule) từ việc học theo thống
kê như trong kiến trúc ACT-R.
Các phương pháp trí tuệ nhân tạo thường được dùng trong các cơng trình nghiên
cứu khoa học nhận thức (cognitive science), một ngành cố gắng tạo ra mơ hình nhận
thức của con người (việc này khác với các nghiên cứu Trí t nhân tạo, vì Trí t nhân
tạo chỉ muốn tạo ra máy móc thực dụng, khơng phải tạo ra mơ hình về hoạt động của
bộ óc con người).

16


CHƯƠNG 2: BÀI TỐN QUA SƠNG
I. TỔNG QUAN VỀ ĐỀ TÀI
1. Giới thiệu đề tài

a.

Bài tốn: Qua sơng
Tại bến sơng nọ có 3 con quỷ và 3 thầy tu muốn qua sơng. Biết rằng tại một thời

điểm thuyền chỉ có thể chứa tối đa được 2 khách. Tại mỗi bên song nếu thế quỷ lớn
hơn số thầy tu thì quỷ sẽ ăn thịt thầy tu.
b.

Yêu cầu: Hãy viết chương trình giải quyết bài toán trên.

17


II. PHÂN TÍCH ĐỀ TÀI
Bài tốn có hai trạng thái:
•

Trạng thái bờ trái {số thầy tu, số quỷ}.

•

Trạng thái bờ phải {số thầy tu, số quỷ}.

-

Cách thay đổi các trạng thái:

•


Trạng thái bờ trái: Di chuyển thầy tu hoặc quỷ qua bờ phải.

•

Trạng thái bờ phải: Di chuyển thầy tu hoặc quỷ về lại bờ trái.

-

Mỗi cách thay đổi trạng thái sẽ có cách thay đổi cụ thể:

•

Di chuyển thầy tu hoặc quỷ qua bờ phải có các trường hợp thay đổi trạng thái:



Đưa 2 thầy tu qua bờ phải.



Đưa 2 quỷ qua bờ phải.



Đưa 1 thầy tu hoặc 1 quỷ qua bờ phải.



Đưa 1 thầy tu qua bờ phải.
Xét trường hợp này ta thấy.

+ Tại điều kiện bờ phải khơng có đối tượng nào, khi thực hiện đưa 1 thầy
tu qua bờ phải sẽ phải di chuyển lại thầy tu này về bờ trái.
+ Tại điều kiện bờ phải tồn tại cả quỷ và người, khí đó số lượng quỷ và
thầy tu tại bờ phải là bằng nhau, do đó khi thêm 1 thầy tu sẽ tạo ra sự chênh lệch
số quỷ lớn hơn số thầy tu tại bờ trái (Game over) hoặc số thầy tu ở bờ trái bằng
0 và số quỷ bằng 1. Tại trường hợp này rõ ràng chở 1 thầy tu và 1 quỷ sẽ tối ưu
hơn rất nhiều
+ Tại điều kiện bờ phải toàn quỷ. Nếu số quỷ lớn hơn 1, thầy tu sẽ bị ăn
thịt. Nếu số quỷ bằng 1 ta sẽ phải đưa thầy tu đó về bờ trái. Nên đưa 1 thầy tu
sang bên phải tại điều kiện này hoàn toàn không cần thiết.
+ Sẽ không tồn tại trường hợp bờ phải tồn thầy tu do khi đó thầy tu bên
bờ trái sẽ bị ăn thịt
 Từ các phân tích ta thấy Trường hợp thay đổi trạng thái “Đưa 1 thầy tu qua
bờ phải” là không cần thiết
18




Đưa 1 quỷ qua bờ phải.

•

Di chuyển thầy tu hoặc quỷ về lại bờ trái có hai trường hợp thay đổi trạng thái:



Đưa 1 quỷ về bờ trái.




Đưa 1 thầy tu và 1 quỷ về bờ trái.
Khi di chuyển thầy tu hoặc quỷ về lại bờ trái để tránh tối đa các vịng lặp vơ

hạn, em sẽ chỉ sử dụng 2 trường hợp trên vì 2 trường hợp này là 2 trường hợp tối ưu
nhất.
-

Mỗi lần thực hiện thay đổi trạng thái thì cần phải kiểm tra trạng thái đó có thay

đổi đúng hay khơng?
•

Số thầy tu phải lớn hơn bằng số quỷ hoặc số thầy tu bằng 0 ở mỗi trạng thái.

19


III.

CÀI ĐẶT THUẬT TỐN

1. Ý tưởng
Xây dựng một chương trình dưới dạng trò chơi ở của sổ console, với mục đích
của trị chơi là đưa số thầy tu và sơ quỷ từ bên trái sang bên phải với các ràng buộc của
đề tài. Chương trình cho phép người dùng tự chơi bằng cách nhập dữ liệu từ bàn phím,
nhờ sự trợ giúp của máy tính chơi 1 lượt hoặc để máy tính tự chơi.
2. Xây dựng thuật tốn
Chương trình được viết bằng phần mềm Apache NetBeans bằng ngôn ngữ java
Các thư viện sử dụng bao gồm:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
Bắt đầu thuật toán. Khởi tạo 2 mảng 1 chiều, mỗi mảng có 2 giá trị tương ứng
với số lượng thầy tu và số lượng quỷ tại 2 bên bờ sông và biến input1 được sử dụng để
đọc dữ liệu nhập vào từ bàn phím:
static int[] brinkLeft= new int[2];
static int[] brinkRight=new int[2];
static int count = 0;
static BufferedReader input1= new
BufferedReader(newInputStreamReader(System.in));

20


Tiếp theo xây dựng hàm khởi tạo tham số khởi đầu cho chương trình với tham
số n sẽ do người dùng nhập vào từ trước khi ta gọi hàm:
static void init (int n) {
brinkLeft[0] = n;
brinkLeft[1] = n;
brinkRight[0] = 0;
brinkRight[1] = 0;
}
Xây dựng hàm kiểm tra tính hợp lệ của trạng thái (Số thầy tu lớn hơn hoặc bằng
số quỷ hoặc số thầy tu bằng 0 tại mỗi bên sông của trạng thái) với các tham số là số
lượng thầy tu và quỷ ở mỗi bên:
static boolean check (int monkLeft, int devilLeft, int monkRight, int devilRight,
char mode) {
if (monkLeft == 0 && devilLeft == 2 && monkRight == 2 && devilRight == 0
&& mode == 'Q')

return false;
else if ((monkLeft >= devilLeft || monkLeft == 0) && (monkLeft >= 0
&& devilLeft >= 0)
&& (monkRight >= devilRight || monkRight == 0) && (monkRight >= 0
&& devilRight >= 0))
return true;
return false;
}
Tạo hàm với chức năng đưa quỷ hoặc thầy tu hoặc cả 2 cùng qua sông từ bờ bên
trái sang bờ bên phải. Khi bắt đầu, hàm sẽ đọc dữ liệu về số lượng các đối tượng tại 2
bên, sau đó thực hiện kiểm tra các trường hợp thay đổi trạng thái theo thứ tự ưu tiên,
21


kiểm tra tính thỏa mãn điều kiện của đề bài tại các trường hợp. Nếu thỏa mãn, hàm sẽ
thực hiện trường hợp đó.
static void brinkLeftToRight () {
// Have five case: 2 monk; 2 devil; 1 monk and 1 devil, 1 monk, 1devil pass
over.
int[] tempLeft= new int[2];
int[] tempRight= new int[2];
for (int i = 0; i < 5; i++) {
tempLeft[0] = brinkLeft[0];
tempLeft[1] = brinkLeft[1];
tempRight[0] = brinkRight[0];
tempRight[1] = brinkRight[1];
switch (i) {
case 0: {
tempLeft[0] -= 2;
tempRight[0] += 2;

break;
}
case 1: {
tempLeft[1] -= 2;
tempRight[1] += 2;
break;
}
case 2: {
tempLeft[0]--; tempLeft[1]--;
tempRight[0]++; tempRight[1]++;
break;
}
22


case 3: {
tempLeft[0] -= 1;
tempRight[0] += 1;
break;
}
case 4: {
tempLeft[1] -= 1;
tempRight[1] += 1;
break;
}
default: break;
}
if (check (tempLeft[0], tempLeft[1], tempRight[0], tempRight[1]))
{
count++;

brinkLeft[0] = tempLeft[0];
brinkLeft[1] = tempLeft[1];
brinkRight[0] = tempRight[0];
brinkRight[1] = tempRight[1];
switch (i) {
case 0: {
System.out.println (count +". Two Monk: Left --->>> Right.
break;
}
case 1: {
System.out.println (count +". Two Devil: Left --->>> Right." );
break;
23


}
case 2: {
System.out.println (count + ". One Monk and One Devil: Left --->>>
Right.");
break;
}
case 3: {
System.out.println (count + ". One Monk: Left --->>> Right.");
break;
}
case 4: {
System.out.println (count + ". One Devil: Left --->>> Right.");
break;
}
default: break;

}
break;
}
}
}
Tương tự, ta tạo hàm di chuyển thầy tu và quỷ từ bờ phải trở về bờ trái
static void brinkRightToLeft() {
int[] tempLeft= new int[2];
int[] tempRight= new int[2];
for(int i = 0; i < 3; i++) {
tempLeft[0] = brinkLeft[0];
24


tempLeft[1] = brinkLeft[1];
tempRight[0] = brinkRight[0];
tempRight[1] = brinkRight[1];
switch(i) {
case 0: {
tempLeft[1]++;
tempRight[1]--;
break;
}
case 1: {
tempLeft[0]++; tempLeft[1]++;
tempRight[0]--; tempRight[1]--;
break;
}
default: break;
}

if(check(tempLeft[0], tempLeft[1], tempRight[0], tempRight[1],
'V') ) {
count++;
brinkLeft[0] = tempLeft[0];
brinkLeft[1] = tempLeft[1];
brinkRight[0] = tempRight[0];
brinkRight[1] = tempRight[1];
switch(i) {
case 0: {
System.out.println(count
Devil

: Left <<<--- Right.");
break;
25

+".

One