Ch ng 3 ươ
PHÂN RÃ BÀI TOÁN - TÌM KI M L I GI I Ế Ờ Ả
TRÊN Đ TH VÀ/ HO CỒ Ị Ặ
1. Đ t v n đ .ặ ấ ề
Trong ch ng 2, chúng ta đã nghiên c u vi c bi u di n bài toán thôngươ ứ ệ ể ễ
qua các tr ng thái và các toán t . Khi đó vi c tìm l i gi i c a bài toán đ cạ ử ệ ờ ả ủ ượ
quy v vi c tìm đ ng đi trong không gian tr ng thái. Trong ch ng nàyề ệ ườ ạ ươ
chúng ta s nghiên c u m t ph ng pháp lu n khác đ gi i quy t v n đ ,ẽ ứ ộ ươ ậ ể ả ế ấ ề
d a trên vi c quy v n đ v các v n đ con.ự ệ ấ ề ề ấ ề
Ý t ng ch y u là xu t phát t bài toán ban đ u, tách ra các bài toánưở ủ ế ấ ừ ầ
con, quá trình này ti p t c đ i v i các bài toán con cho đ n khi g p các bàiế ụ ố ớ ế ặ
toán s c p (bài toán có l i gi i ngay).ơ ấ ờ ả
Ví d 1. ụ Xét bài toán tính tích phân
dxxxx )(ln 2
∫
+
.
Thông th ng đ tính tích phân b t đ nh, chúng ta th ng s d ng cácườ ể ấ ị ườ ử ụ
quy t c tính tích phân: tích phân c a t ng, quy t c tích phân t ng ph n hay cácắ ủ ổ ắ ừ ầ
phép bi n đ i v.v… đ đ a tích phân c n tính v tích phân c a các hàm s sế ổ ể ư ầ ề ủ ố ơ
c p mà chúng ta đã bi t cách tính. Đ i v i tích phân trên, áp d ng quy t c tíchấ ế ố ớ ụ ắ
phân c a t ng ta đ a v hai tích phân ủ ổ ư ề ∫xlnxdx và tích phân ∫x3dx. Áp d ngụ
quy t c tích phân t ng ph n ta đ a tích phân ắ ừ ầ ư ∫xlnx v tích phân ề∫xdx. Quá
trình trên có th bi u di n b i đ th trong Hình 1.ể ể ễ ở ồ ị
90
∫x(lnx+x2)dx
∫xlnxdx ∫x3dx
∫xdx
Hình 1.
Trong bài toán tích phân, các tích phân c b n là các tr ng thái k t thúc.ơ ả ạ ế
Ví d 2.ụ Bài toán tìm đ ng đi trên b n đ giao thông.ườ ả ồ
Bài toán này đã đ c phát bi u nh bài toán tìm đ ng đi trong khôngượ ể ư ươ
gian tr ng thái, trong đó m i tr ng thái ng v i m t thành ph , m i toán tạ ỗ ạ ứ ớ ộ ố ỗ ử
ng v i m t con đ ng, n i thành ph này v i thành ph khác. Bây gi taứ ớ ộ ườ ố ố ớ ố ờ
đ a ra m t cách b u di n khác d a trên vi c quy v n đ v các v n đ con..ư ộ ể ễ ự ệ ấ ề ề ấ ề
Xét b n đ giao thông gi a các thành ph trong Hình 2.ả ồ ữ ố
A
C D H
F E G
I B K
Hình 2.
Gi s ta c n tìm đ ng đi t thành ph A đ n thành ph B. Có m tả ử ầ ườ ừ ố ế ố ộ
con sông ch y qua hai thành ph E và G và có c u qua sông m i thành phả ố ầ ở ỗ ố
đó. Nh v y m i đ ng đi t A đ n B đ u ph i đi qua E ho c G. Khi đó bàiư ậ ọ ườ ừ ế ề ả ặ
toán tìm đ ng đi t A đ n B đ c quy v m t trong hai bài toán:ườ ừ ế ượ ề ộ
1) Bài toán tìm đ ng đi t A đ n B qua Eườ ừ ế
2) Bài toán tìm đ ng đi t A đ n B qua Gườ ừ ế
M i m t bài toán trên l i có th phân nh nh sau:ỗ ộ ạ ể ỏ ư
1) Bài toán tìm đ ng đi t A đ n B qua E đ c quy v :ườ ừ ế ượ ề
1.1. Tìm đ ng đi t A đ n E vàườ ừ ế
91
1.2. Tìm đ ng đi t E đ n Bườ ừ ế
2) Bài toán tòm đ ng đi t A đ n B qua G đ c quy v :ườ ừ ế ượ ề
2.1. Tìm đ ng đi t A đ n G vàườ ừ ế
2.2. Tìm đ ng đi t G đ n Bườ ừ ế
T ng quát, t bài toán P ta đ a v m t trong các tr ng h p:ổ ừ ư ề ộ ườ ợ
- Đ a P v các bài toán t ng đ ng: P1, P2,..., Pkư ề ươ ươ
- Đ a P v các bài toán con: P1, P2,..., Pk ư ề
Ph ng pháp phân chia bài toán ban đ u nh trên đã g p trong l p trìnhươ ầ ư ặ ậ
truy n th ng v i cách g i “chia đ tr ” , “Modul hoá”.ề ố ớ ọ ể ị
2. Đ th VÀ/HO C:ồ ị Ặ
Không gian tr ng thái mô t vi c quy v n đ v các v n đ con có thạ ả ệ ấ ề ề ấ ề ể
bi u di n d i d ng đ th đ nh h ng đ c bi t g i là đ th và/ho c. Đ thể ễ ướ ạ ồ ị ị ướ ặ ệ ọ ồ ị ặ ồ ị
này đ c xây d ng nh sau:ượ ự ư
M i bài toán ng v i m t đ nh c a đ th . N u có m t toán t quy bàiỗ ứ ớ ộ ỉ ủ ồ ị ế ộ ử
toán v các bài toán t ng đ ng thì s có các cung đi t bài toán xu t phátề ươ ươ ẽ ừ ấ
đ n các bài toán t ng đ ng đó. N u m t toán t quy bài toán v các bàiế ươ ươ ế ộ ử ề
toán con thì cũng có các cung n i t bài toán xu t phát đ n các bài toán con,ố ừ ấ ế
ngoài ra gi a các cung này cũng có đ ng n i v i nhau.. Ch ng h n, gi sữ ườ ớ ớ ẳ ạ ả ử
bài toán A đ c đ a v hai bài táon t ng đ ng A1 và A2. Bài toán A1 l iượ ư ề ươ ươ ạ
đ c quy v hai bài toán con B1 và B2, ta có bi u di n nh hình 3.ượ ề ể ễ ư
A
A1 A2
92
B1 B2
Hình 3
M t cách hình th c ta có th đ nh nghĩa đ th và/ho c nh sau:ộ ứ ể ị ồ ị ặ ư
Đ th G = (V, E) đ c g i là đ th VÀ/HO C n u ồ ị ượ ọ ồ ị Ặ ế
Vn ∈∀
, T(n) ho cặ
các bài toán con c a n (n g i là các đ nh VÀ) ho c là t p các bài toán t ngủ ọ ỉ ặ ậ ươ
đ ng v i n (n g i là đ nh HO C).ươ ớ ọ ỉ Ặ
Cách bi u di n nh sau:ể ễ ư
n
n1n2 ...... nk
n đ c g i là đ nh HO C (nượ ọ ỉ Ặ ⇔ n1 ⇔...⇔ nk )
n
n1n2 ...... nk
n đ c g i là đ nh VÀ (nượ ọ ỉ ⇔ n1∩...∩ nk )
Khi đó đ gi i bài toán n ta ph i tìm đ th con c a G là m t cây có g cể ả ả ồ ị ủ ộ ố
là đ nh xu t phát n sao cho m i đ nh trên đ th con này đ a v đ c các bàiỉ ấ ọ ỉ ồ ị ư ề ượ
toán s c p (đ nh k t thúc).ơ ấ ỉ ế
Nh n xét: G i ậ ọ VA: t p các đ nh VÀậ ỉ
VO: t p các đ nh HO Cậ ỉ Ặ
•N u VA= ế∅ ⇒ tìm l i gi i trên đ th bi u di n b ng không gian tr ngờ ả ồ ị ể ễ ằ ạ
thái
Khi đó:
- Bài toán n đ c g i là gi i đ c n u: ượ ọ ả ượ ế
+ ho c n là đ nh k t thúcặ ỉ ế
93
+ ho c T(n)={nặ1, n2,..., nk} và n u n là đ nh HO C ế ỉ Ặ
)...1( ki ∈∃⇒
sao cho ni
gi i đ c, ng c l i nả ượ ượ ạ i gi i đ c ả ượ
ki ...1
=∀
.
- Bài toán n đ c g i là không gi i đ c n u: ượ ọ ả ượ ế
+ ho c n là đ nh lá và n không ph i là đ nh k t thúc.ặ ỉ ả ỉ ế
+ ho c T(n)={nặ1, n2,..., nk}và n u n là đ nh HO C ế ỉ Ặ
)...1( ki ∈∃⇒
sao cho nj
không gi i đ c, ng c l i nả ượ ượ ạ i không gi i đ c ả ượ
ki ...1
=∀
.
•Đ tìm l i gi i c a bài toán khi đ c phân rã v đ th VÀ/HO C khôngể ờ ả ủ ượ ề ồ ị Ặ
ph i tìm đ ng đi mà ph i đi tìm đ th con g i là đ th con l i gi i (hayả ườ ả ồ ị ọ ồ ị ờ ả
cây l i gi i)ờ ả
Cây l i gi i là đ th con G’ c a G tho :ờ ả ồ ị ủ ả
- Đ nh g c (xu t phát) ỉ ố ấ
'
0Vn ∈
-
'Vn
∈∀
, n gi i đ c.ả ượ
•Ta có s t ng quan:ự ươ
Phân rã bài toán Đ th VÀ/HO Cồ ị Ặ
Bài toán Đ nhỉ
Chuy n bài toán thành các bài toánể
con
Cung
Bài toán s c pơ ấ Đ nh cu iỉ ố
Các bài toán con ph ụĐ nh VÀỉ
Các bài toán con đ c l p ộ ậ Đ nh HO Cỉ Ặ
Gi i bài toánảTìm đ th con l i gi i bàiồ ị ờ ả
toán
3. Các ph ng pháp tìm ki m l i gi i trên đ th và/ho c.ươ ế ờ ả ồ ị ặ
Sau khi l a ch n mô t bài toán và các toán t quy bài toán v bài toánự ọ ả ử ề
con, ta có th xây d ng đ th Và/ho c đ gi i quy t bài toán ban đ u ho cể ự ồ ị ặ ể ả ế ầ ặ
ch ng t tính không gi i đ c c a nó. Cũng nh đ th trong không gianứ ỏ ả ượ ủ ư ồ ị
94