Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Lời nói đầu.
Lý thuyết đồ thị là một ngành khoa học có từ lâu nhưng lại có nhiều ứng dụng
hiện đại. Những ý tưởng ban đầu của nó được đưa ra bởi nhà toán học người Thụy Sĩ là
Leonhard Euler.
Lý thuyết đồ thị được dùng để giải quyết nhiều bài toán thuộc nhiều lĩnh vực
khác nhau chẳng hạn như: dùng mô hình đồ thị để xác định xem hai máy tính trong một
mạng máy tính có trao đổi thông tin với nhau được không?.Đồ thị với các trọng số được gắn
cho các cạnh có thể dùng để giải quyết bài toán tìm đường đi ngắn nhất trong một mạng lưới
giao thông. Chúng ta có thể phân biệt các hợp chất hóa học có cùng công thức phân tử
nhưng có cấu trúc khác nhau nhờ vào đồ thị.
Vấn đề tìm đường đi, đặc biệt là bài toán tìm đường đi trong mê cung là một chủ đề
khá thú vị, mang tính chất trò chơi gắn liền với câu chuyện thần thoại Hi Lạp nhưng lại có
rất nhiều ứng dụng trong cuộc sống. Ngày này nhiều người đã thiết kế ra các mê cung nhằm
phục vụ nhu cầu giải trí tham gia trò chơi mở mang trí lực….
Do là lí do chúng em chọn đề tài “ Bài toán tìm đường đi trong mê cung và ứng
dụng”.
Chúng em xin chân thành cảm ơn Thầy PGS.TSKH Trần Quốc Chiến đã giúp chúng
em có kiến thức và càng hiểu rõ vấn đề này.

Nhóm 2

Trang 1


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Phân công công việc
STT
1
2
3
4

Họ và tên
Trương Hoài Bão
Lê Thị Hạnh Vân
Đỗ Xuân
Nguyễn Thị Yến

Phần thực hiện
Tìm hiểu đại cương về lý thuyết đồ thị.
Tìm hiểu thuật toán, viết chương trình.
Tìm hiểu bài toán tìm đường đi trong mê cung và ƯD
Tìm hiểu thuật toán, viết chương trình.

Chữ kí

Phần 1:
Nhóm 2

Trang 2


Đề tài: Tìm đường đi trong mê cung và ứng dụng


GVHD: PGS.TSKH Trần Quốc Chiến

Đại cương về lý thuyết đồ thị.
Lý thuyết đồ thị bắt đầu với tư cách là một ngành Toán học bằng bài báo nổi tiếng của
nhà toán học Euler năm 1736 về những cây cầu ở Konigsberg. Mãi hơn 100 năm sau tức là
vào giữa thế kỉ 19, người ta mới chú ý đến các vấn đề của Lý thuyết đồ thị đặc biệt là ở nước
Anh.
Bài toán nổi tiếng nhất là : “ Giả thiết bốn màu” do DeMorgan đưa ra lần đầu tiên năm
1850. Đây là bài toán có rất nhiều đóng góp cho Lý thuyết đồ thị.
Ngày này Lý thuyết đồ thị đã phát triển thành một nghành Toán học có vị trí đặc biệt
quan trọng về mặt lý thuyết cũng như ứng dụng.
I. Đại cương về đồ thị.
1.

Đồ thị vô hướng và đồ thị có hướng.
Đồ thị vô hướng G=(V,E) là một tập V các đỉnh và tập E các cạnh.
Đồ thị có hướng G=(V,E) gồm một tập V các đỉnh và tập E các cạnh có hướng gọi là

cung.
Cho đồ thị (có hướng hoặc vô hướng) G= (V,E).
Nếu cạnh e liên kết đỉnh v,w thì ta nói cạnh e liên thuộc đỉnh v,w, các đỉnh w,v liên
thuộc cạnh e, các đỉnh v,w gọi là các đỉnh biên của cạnh e và đỉnh v kề đỉnh w.
Nếu có nhiều cạnh liên kết cùng một cặp đỉnh thì ta nói đó là các cạnh song song.
Cạnh có hai đỉnh liên kết không trùng nhau gọi là khuyên.
Đỉnh không kề với đỉnh khác gọi là đỉnh cô lập.
Số đỉnh của đồ thị gọi là bậc của đồ thị, số cạnh hoặc số cung của đồ thị thì gọi là cỡ
của đồ thị.
Đồ thị hữu hạn là đồ thị có cỡ và bậc hữu hạn.
Đồ thị đơn là đồ thị không có khuyên và không có cạnh song song.
Đồ thị vô hướng đủ là đồ thị mà mọi cặp đỉnh đều kề nhau.

Nhóm 2

Trang 3


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Đồ thị có hướng đủ là đồ thị có đồ thị lót đủ.
2.

Bậc, nửa bậc vào, nửa bậc ra.
•

Cho đồ thị G=(V,E)

Giả sử v ∈ V có p khuyên và q cạnh liên thuộc( không phải là khuyên). Khi đó bậc của
đỉnh v là 2p+q và kí hiệu là deg(v).
Đỉnh cô lập trong đồ thị đơn là đỉnh có bậc bằng 0.
Đỉnh có bậc bằng 1 gọi là đỉnh treo.
Cho G= (V,E) là đồ thị có hướng , v ∈ V,

•

nửa bậc ra của đỉnh v kí hiệu là: dego(v), là số cung đi ra từ đỉnh v
nửa bậc vào của đỉnh v kí hiệu là: deg1(v) là số cung đi tới đỉnh v.
Bổ đề bắt tay- Hand Shaking Lemma
Cho đồ thị G=(V,E). Khi đó:
i. Tổng bậc các đỉnh đồ thị là bậc chẵn và


∑ deg(v) = 2.card ( E )

v ∈V

ii. Nếu G là đồ thị có hướng thì

∑
v∈V

dego(V)=

∑
v∈V

deg1(v)= card(E)

Trong đó card(E) là số phần tử của tập E.
Chú ý: Số đỉnh bậc lẻ của đồ thị vô hướng là số chẵn.
•

Đồ thị Kn là đồ thị đơn, đủ n đỉnh .

•

Mọi đỉnh của đồ thị Kn có n-1 bậc và Kn có n(n-1)/2 cạnh.

•

Đồ thị lưỡng phân.


Cho G=(V,E) là đồ thị mà các tập đỉnh được phân làm 2 tập rời nhau V1 và V2 sao cho mỗi
cạnh của nó liên kết với một đỉnh thuộc V1 và một đỉnh thuộc V2 kí hiệu:
G=({V1,V2},E)

Nhóm 2

Trang 4


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Đồ thị Km.n là đồ thị lưỡng phân G=({V1,V2},E) với tập V1 có m đỉnh và tập V2 có n đỉnh và
mỗi đỉnh của V1 được nối với mỗi đỉnh của V2 bằng một cạnh duy nhất.
Cho đồ thị lưỡng phân đủ Km.n= G=({V1,V2},E) với tập V1 có m đỉnh và tập V2 có n đỉnh.
Khi đó mỗi đỉnh trong V1 có bậc là n và mỗi đỉnh trong V2 có bậc là m và Km.n có m.n cạnh.
•

Cho đồ thị đơn G. vecto bậc d(G) của đồ thị G là dãy các
bậc của tất cả các đỉnh của G sắp xếp giảm dần.

Véc tơ v gồm các số tự nhiên gọi là vecto đồ thị nếu tồn tại đơn đồ thị có vecto bậc là v.
3.

Đường đi, chu trình, tính liên thông.
•

Cho đồ thị G=(V,E).


Dây µ từ đỉnh v đến đỉnh w là tập hợp các đỉnh và cạnh nối tiếp nhau bắt đầu từ đỉnh v kết
thúc tại đỉnh w. Số cạnh trên dây µ gọi là độ dài của dây µ .
Dây µ từ đỉnh v đến đỉnh w độ dài k được biểu diễn như sau
µ = (v,e1,e2,e3,v2,….,vk-1,ek,w)

Trong đó vi (i= 1,…,k-1) là các đỉnh trên dây và ei( i=1,…,k-1)là các cạnh trên dây.
Đường đi sơ cấp là đường đi không qua đỉnh quá một lần.
Vòng là dây có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau.
Chu trình sơ cấp là chu trình không đi qua một đỉnh quá một lần.
Đồ thị vô hướng gọi là liên thông nếu mọi cặp đỉnh của nó đều có đường đi nối chúng lại với
nhau.
Đồ thị có hướng gọi là liên thông mạnh nếu mọi cặp đỉnh của nó đều có đường đi có hướng
nối chúng lại với nhau.
Đồ thị có hướng gọi là liên thông yếu nếu đồ thị lót của nó liên thông.
Đồ thị có hướng gọi là bán liên thông nếu với mọi cặp đỉnh (u,v) bao giờ cũng tồn tại đường
đi có hướng từ u đến v hoặc v đến u.
• Trọng đồ (có hướng) là đồ thị ( có hướng) mà mỗi cạnh( cung) của nó đều gắn một số.

Nhóm 2

Trang 5


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Phần 2:

Bài Toán Tìm Đường Đi Trong Mê Cung.
Bài toán tìm đường đi trong mê cung đố vui đồ thị lâu đời nhất. Trong văn học Hi Lạp
câu chuyện dũng sĩ Theseus đi cứu công chúa Ariadne bị con nhân mã Minotaur giam giữ
trong mê cung.
Ở đảo Crete có một con quái vật đầu bò, mình người tên là Minotaur chuyên ăn thịt
người và súc vật. Nhà vua sai kiến trúc sư nổi tiếng Daedalus xây dựng một cung điện lớn
gồm nhiều hành lang, khó có thể đi ra ngoài được để nhốt Minotaur ở đó. Hằng năm các
nước chư hầu phải đưa người đến nộp cho quái vật. Chàng dũng sĩ Theseus muốn tiêu diệt
quái thú trừ họa cho muôn dân và chàng gặp được công chúa Ariadne, công chúa đem lòng
yêu Theseus nên đã tìm Daedalus hỏi kế giúp chàng khỏi lạc trong cung điện. Theo lời của
Daedalus, Ariadne đã đưa cho chàng dũng sĩ cuộn chỉ. Nhờ vậy sau khi giết xong quái thú
anh ra ngoài mà không bị lạc đường.
Ngày nay vẫn còn rất nhiều mê cung trên thế giới như:

Mê cung Reignac-sur-Indre ở Pháp. Đây là mê cung cây cối lớn nhất trên thế giới.
Nhóm 2

Trang 6


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Mê cung Hampton Court ở Anh. Đây là mê cung rào có tuổi thị cao nhất ở Anh.

Mê cung Imprint ở Gloucester.

Nhóm 2


Trang 7


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Trang trại Pisaniở Italia. Đây là mê cung phức tạp nhất trên thế giới.

Mê cung cây dứa ở Hawaii. Đây là mê cung dài nhất trên thế giới.

Nhóm 2

Trang 8


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Mê cung là một hệ thống gồm nhiều hành lang nối với nhau. Bài toán tìm đường đi
trong mê cung là đứng từ vị trí S( bên trong mê cung hoặc cửa vào) Tìm đường đi đến vị trí
E( cửa ra hoặc bên trong mê cung).
Nếu biểu diễn mê cung bằng đồ thị trong đó các hành lang là cạnh, còn giao điểm của
chúng là đỉnh thì ta có bài toán tìm đường đi trong đồ thị. Lưu ý rằng ta không biết sơ đồ của
mê cung.
D
G
H
C


J
K
E

F

I

L

Mê cung có thể biểu diễn bằng đồ thị sau:
G
D

H
J

E
C

F
A

Nhóm 2

L

K


B

Trang 9


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

1. Một vài thuật toán tìm đường đi trong mê cung.
Cho đồ thị G= (V,E) và đỉnh s,e thuộc V.Tìm đường đi từ s đến e.
a. Thuật toán Wiener:
Xuất phát từ đỉnh s đi theo cạnh của đồ thị theo nguyên tắc sau:
• Tại mỗi đỉnh chọn cạnh chưa đi qua trước đó.
• Nếu tại đỉnh nào đó mọi cạnh liên thuộc nó đã đi qua thì quay ngược lại
cho đến khi gặp đỉnh có cạnh chưa qua.
Hiển nhiên là bằng cách này đi qua tất cả các cạnh của đồ thị. Tuy nhiên để
thực hiện thuật toán này cần phải nhớ thứ tự các cạnh đã đi qua phải có phương
tiện nhớ giống như “ cuộn chỉ Ariadne”.
b. Thuật toán Tarri
Xuất phát từ đỉnh s đi theo cạnh của đồ thị theo nguyên tắc sau:
• Đánh dấu hướng đã đi qua của cạnh.
• Với mỗi đỉnh bậc lớn hơn bằng 3 của đồ thị, cạnh dẫn đến nó lần đầu
tiên được đánh dấu đặc biệt.
• Tại mỗi đỉnh chọn cạnh chưa đi qua trước đó. Trường hợp các cạnh đã
đi qua thì chọn cạnh đi theo hướng ngược lại. Cạnh đánh dấu đặc biệt là
phương án cuối cùng nếu không có cách nào khác.
Bằng cách này ta đi qua tất cả các cạnh của đồ thị. Như vậy nếu đồ thị liên thông thì
lúc nào đó ta sẽ đến đỉnh e.
c. Tìm đường đi trong mê cung

Mê cung là một đồ thị vô hướng gồm N đỉnh được mã số từ 1 đến N, với các cạnh,
mỗi cạnh nối 2 đỉnh nào đó với nhau.Cho 2 đỉnh S và T trong mê cung tìm đường đi
từ S tới T.
 Dữ liệu vào: file MECUNG.INP với cấu trúc như sau:

Nhóm 2

Trang 10


Đề tài: Tìm đường đi trong mê cung và ứng dụng

•

GVHD: PGS.TSKH Trần Quốc Chiến

Dòng đầu tiên, được gọi là dòng 0, chứa 3 số tự nhiên N,S,T
ghi cách nhau bởi dấu cách, trong đó n là số lượng đỉnh của mê cung, S là
đỉnh xuất phát, T là đỉnh kết thúc.

•

Dòng thứ i ,i= 1…n-1 cho biết có hay không cạnh nối đỉnh i
với j, j= i+1.. n.

Ví dụ:

Trong đó:
- Dòng 0: 9 6 7 là mê cung gồm 9 đỉnh ( mã số từ 1..9), cần tìm đường
đi từ đỉnh 6 đến đỉnh 7.

- Dòng 1: 1 0 1 1 1 0 0 0 nghĩa là đỉnh 1 được nối với các đỉnh 2,4,5,6.
Không có cạnh nối đỉnh 1 với các đỉnh 3, 7,8,9.
- ……………
- Dòng 8: 1 nghĩa là đỉnh 8 nối với đỉnh 9.
Vì đồ thị vô hướng nên cạnh nối đỉnh x với đỉnh y cũng giống cạnh nối
đỉnh y với đỉnh x.
Nhóm 2

Trang 11


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Thông tin vê đỉnh n không cần thông báo vì mỗi đỉnh i ta chỉ cần liệt kê
các đỉnh j>i tạo thành cạnh (i,j).
Kết quả được lưu vào file MECUNG.OUT
- Dòng đầu tiên ghi số tự nhiên k là số đỉnh trên đường đi từ S đến T
nếu không tìm được đường đi ghi số 0.
- Từ dòng tiếp theo ghi lần lượt các đỉnh có trên đường đi.
Với ví dụ trên có kết quả là:

Từ đỉnh 6 có thể đến được đỉnh 7 qua 5 đỉnh như sau:
6

4

2


3

7.

Với mê cùng này nếu yêu cầu tìm đường đi từ đỉnh 6 đến đỉnh 9 với dữ liệu vào
như trên thì sẽ nhận được kết quả là 0 với ý nghĩa không có đường đi từ đỉnh 6 đến đỉnh 9,
do mê cung đã cho không liên thông, đỉnh 6 và đỉnh 9 nằm ở hai vùng liên thông khác nhau.

Nhóm 2

Trang 12


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Thuật toán:
Xuất phát từ đỉnh v[1] = s, mỗi bước lặp i ta thực hiện các bước kiểm tra sau.
Gọi k là số đỉnh đã đi qua và được tích lũy trong trong mảng giải trình đường đi v. Cụ thể
xuất phát từ đỉnh v[1] =s, sau một số lần duyệt ta quyết định chọn đường đi qua các đỉnh
v[1],v[2],v[3],….,v[k]. Có thể gặp các tình huống sau:
a.

(Đến đích) nếu v[k]= t, tức là đã đến được đỉnh t: thông báo kết
quả dừng thuật toán, ngược lại sang bước b.

b.

(Thất bại) k=0: nếu đã quay lại vị trí xuất phát v[i]=s mà từ đó

không còn đường đi nào khác phải lùi một bước, do đó k= 0.Trường hợp
này chứng tỏ bài toán vô nghiệm, tức là do đồ thị không liên thông nên
không có đường đi từ đỉnh s đến đỉnh t. Ta thông báo vô nghiệm và dừng
thuật toán.

c.

(Đi tiếp) Nếu từ đỉnh v[k] tìm được một cạnh chưa đi qua và dẫn
đến một đỉnh i nào đó thì tiến theo đường đó nếu không thực hiện bước d.

d.

(Lùi một bước) bỏ đỉnh v[k] lùi lại đỉnh v[k-1].

Thuật toán trên có tên là sợi chỉ Arian.
Chương trình.
(* Pascal *)
(*-----------------------------------MECUNG.PAS Tim duong trong me cung
-------------------------------------*)
{$B-}
uses crt;
const
MN = 100; {So dinh toi da }
fn = 'MECUNG.INP'; {input file }
gn = 'MECUNG.OUT'; {output file }
Nhóm 2

Trang 13



Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

nl = #13#10; {xuong dong moi }
bl = #32; {dau cach }
type
MB1 = array[0..MN] of byte;
MB2 = array[0..MN] of MB1;
var
a: MB2; {ma tran ke, doi xung }
v: MB1; {vet tim kiem }
d: MB1; {danh dau dinh da chon }
n: byte; {so dinh }
s: byte; {dinh xuat phat }
t: byte; {dinh ket thuc }
k: byte; {buoc duyet }
f,g: text; {f: input file; g: output file}
(*------------------------Doc du lieu
------------------------*)
procedure Doc;
var i,j: byte;
begin
assign(f,fn);
reset(f);
read(f,n,s,t);
fillchar(a,sizeof(a),0);
if (n < 1) or (n > MN) then exit;
for i := 1 to n-1 do
for j := i+1 to n do

Nhóm 2

Trang 14


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

begin
read(f,a[i,j]);
a[j,i] := a[i,j]; {lay doi xung }
end;
close(f);
end;

(*-----------------------Xem du lieu
-------------------------*)
procedure xem;
var i,j: byte;
begin
write(nl,n,bl,s,bl,t,nl);
for i := 1 to n do
begin
for j := 1 to n do
write(a[i,j],bl);
write(nl);
end;
end;
(*--------------------------------------Ghi ket qua.

k = 0: vo nghiem
k > 0: co duong tu s den t gom k canh
----------------------------------------*)
Nhóm 2

Trang 15


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

procedure Ket(k: byte);
var i: byte;
begin
assign(g,gn); rewrite(g);
write(g,k,nl);
if k > 0 then
begin
write(g,v[1]);
for i := 2 to k do
write(g,bl,v[i]);
end;
close(g);
end;
(*-------------------------------------------Tu dinh v[k] tim duoc mot buoc di den dinh i.
d[i] = 0 - dinh i chua xuat hien
trong lich trinh v
d[i] = 1 - dinh i da xuat hien
trong lich trinh v,

---------------------------------------------*)
function Tim: byte;
var i: byte;
begin
Tim := 0;
for i := 1 to n do
if d[i] = 0 then {dinh i chua tham }
Nhóm 2

Trang 16


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

if a[v[k],i] = 1 {co duong tu v[k] den i }
then
begin
Tim := i;
exit;
end;
end;
(*--------------------------Di 1 buoc tu v[k] den i
----------------------------*)
procedure NhaChi(i: byte);
begin
inc(k);
v[k] := i; {tien them 1 buoc }
d[i] := 1; {danh dau dinh da qua }

end;
(*------------------------------------Lui 1 buoc vi tu dinh v[k] khong co kha nang nao
dan den ket qua
-------------------------------------*)
procedure CuonChi;
begin
dec(k);
end;
(*------------------------------Tim duong trong me cung
(Thuat toan Soi chi Arian)
Nhóm 2

Trang 17


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

s: dinh xuat phat
t: dinh ket.
-------------------------------*)
(*---------------------------------------MC - Tim duong trong me cung
(Thuat toan Arian)
s: dinh xuat phat
t: dinh ket.
------------------------------------------*)
procedure MC;
var i: byte;
begin

Doc; {doc du lieu}
{---------------------------khoi tao mang d,
danh dau cac dinh da tham:
d[i] = 1: dinh da tham
d[i] = 0: dinh chua tham
-----------------------------}
fillchar(d,sizeof(d),0);
k := 1; {k – dem so dinh da chon }
v[k] := s; {dinh xuat phat }
d[s] := 1; {da tham dinh s }
repeat
if v[k] = t then {den dich }
begin
ket(k); {ghi ket qua: giai trinh duong di }
Nhóm 2

Trang 18


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

exit;
end;
if k < 1 then {vo nghiem }
begin
ket(0);
exit;
end;

i := Tim;
{tu dinh v[k] tim 1 dinh chua tham i }
if i > 0 then
{neu tim duoc, i > 0, di den dinh i }
NhaChi(i)
else CuonChi;
{neu khong tim duoc, }
{ i = 0: lui 1 buoc - bo dinh v[k] }
until false;
end;
BEGIN
MC; write(nl,'fini');
END.

Nhóm 2

Trang 19


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Phần 3:
Một vài bài toán ứng dụng
1.

Bài toán dê, sói và cải.

Một người nông dân chở dê, sói và cải qua sông bằng một con thuyền nhỏ. Mỗi lần

chỉ chở được một thứ hoặc sói hoặc dê hoặc cải và không được để sói đứng với dê hoặc cải
đứng với dê mà không có người trông coi. Hãy chỉ cách chở.
Ta kí hiệu n( người), s( sói), d(dê) và c( cải). Ta lập đồ thị biểu diễn khả năng chuyển
đổi trạng thái người, sói, dê, và cải ở bên bờ sông xuất phát. Mỗi nút trạng thái là một tập
con của (nsdc) trừ các tập (sd),(nc),(dc),(ns). Sau đó áp dụng thuật toán trên tìm đường đi từ
(nsdc) đến nút ø.
Sau đây là hai phương pháp giải :
nsdc

sc

nsc

c

ndc

d

nd

ø

s

nsd

d

nd


và
nsdc
2.

sc

nsc

ø

Bài toán ba ông chồng ghen.

Có ba cặp vợ chồng qua sông bằng 1 chiếc thuyền nhỏ. Mỗi thuyền chở được nhiều
nhất 2 người và ai cũng biết bơi thuyền. Các ông chồng mắc bệnh ghen nặng nên không cho
vợ đứng cạnh người đàn ông khác khi không có mình. Hãy tìm phương pháp chở tất cả sang
sông.
Ký hiệu các cặp vợ chồng là Aa, Bb, Cc. Ta lập đồ thị, biễu diễn khả năng chuyển đổi
trạng thái các cặp vợ chồng ở bên bờ sông xuất phát. Mỗi nút trạng thái là tập con cuả
(AaBbCc) trừ các tập dạng:
{S| ((aB)) ⊂ S or (aC) ⊂ S) and A∉ S}
{S| ((bA)) ⊂ S or (bC) ⊂ S and B ∉ S}
{S| ((cA)) ⊂ S or (cB) ⊂ S) and C ∉ S}

Nhóm 2

Trang 20


Đề tài: Tìm đường đi trong mê cung và ứng dụng


GVHD: PGS.TSKH Trần Quốc Chiến

Và các tập bù của chúng.
Sau đó áp dụng thuật toán trên để tìm đường đi từ nút AaBbCc đến nút ø.
Sau đây là một phương pháp giải bài toán.
AaBbCc
AaCc

ac

abc

AaBb
c

3.

AaBbC
Cc

ABC

ABCc

Cc

ø

Bài toán ba thầy tu và ba con quỷ


Ba thầy tu và ba con quỷ sang sông bằng một thuyền nhỏ.Mỗi lần thuyền chỉ chở được
nhiều nhất hai người và ai cũng có khả năng bơi thuyền. Hãy tìm phương án sang sông sao
cho nếu có thầy tu và quỷ trên bờ thì số thầy tu không được ít hơn số quỷ ( nếu ngược lại
thầy tu sẽ bị ăn thịt).
Kí hiệu nút trạng thái ở bờ sông là (m,n) trong đó n là số thầy tu, m là số quỷ. Cặp
(m,n) thỏa mãn( 0 ≤ n,m ≤ 3) và [(n=0) or (n ≥ m)]
Ta lập đồ thị biểu diễn khả năng chuyển đổi trạng thái các thầy tu và quỷ ở bên bờ
sông xuất phát.
Sau đó áp dụng thuật toán trên để tìm đường đi từ nút (3,3) đến (0,0).
Sau đây là một phương án giải bài toán:

Nhóm 2

(3,3)

(2,2)

(1,1)

(0,0).

(3,2)

(3,0)

(3, 1) (1,1)

(2,2)


(0,2)

(0,3)

(0,1)

Trang 21


Đề tài: Tìm đường đi trong mê cung và ứng dụng

GVHD: PGS.TSKH Trần Quốc Chiến

Tài liệu tham khảo.
1. Giáo trình Lý Thuyết Đồ Thị Và Ứng Dụng
Tác giả: PGS.TSKH Trần Quốc Chiến.
2. Bài giảng Lý Thuyết Đồ Thị Và Ứng Dụng.
Tác giả: PGS. Hoàng Chí Thành và PGS. Lê Trọng Vĩnh.
3. Và tham khảo trên một vài trang web



Nhóm 2

Trang 22