Giao_trinh_Tri_Tue_Nhan_Tao___Dinh_Manh_Tuong.pdf

http://blogthuthuat.com


inh Mnh Tng Trang 5
Một tập hợp T các trạng thái kết thúc (trạng thái đích). T l tập con của không
gian U. Trong vấn đề của du khách trên, chỉ có một trạng thái đích, đó l thnh phố B.
Nhng trong nhiều vấn đề (chẳng hạn các loại cờ) có thể có nhiều trạng thái đích v ta
không thể xác định trớc đợc các trạng thái đích. Nói chung trong phần lớn các vấn đề
hay, ta chỉ có thể mô tả các trạng thái đích l các trạng thái thỏa mãn một số điều kiện
no đó.
Khi chúng ta biểu diễn một vấn đề thông qua các trạng thái v các toán tử, thì việc
tìm nghiệm của bi toán đợc quy về việc tìm đờng đi từ trạng thái ban đầu tới trạng
thái đích. (Một đờng đi trong không gian trạng thái l một dãy toán tử dẫn một trạng
thái tới một trạng thái khác).
Chúng ta có thể biểu diễn không gian trạng thái bằng đồ thị định hớng, trong đó
mỗi đỉnh của đồ thị tơng ứng với một trạng thái. Nếu có toán tử R biến đổi trạng thái u
thnh trạng thái v, thì có cung gán nhãn R đi từ đỉnh u tới đỉnh v. Khi đó một đờng đi
trong không gian trạng thái sẽ l một đờng đi trong đồ thị ny.
Sau đây chúng ta sẽ xét một số ví dụ về các không gian trạng thái đợc xây dựng
cho một số vấn đề.
Ví dụ 1:
Bi toán 8 số. Chúng ta có bảng 3x3 ô v tám quân mang số hiệu từ 1 đến
8 đợc xếp vo tám ô, còn lại một ô trống, chẳng hạn nh trong hình 2 bên trái. Trong
trò chơi ny, bạn có thể chuyển dịch các quân ở cạch ô trống tới ô trống đó. Vấn đề của
bạn l tìm ra một dãy các chuyển dịch để biến đổi cảnh huống ban đầu (hình 1.2 bên
trái) thnh một cảnh huống xác định no đó, chẳng hạn cảnh huống trong hình 1.2 bên
phải.

http://blogthuthuat.com


inh Mnh Tng Trang 6
Trong bi toán ny, trạng thái ban đầu l cảnh huống ở bên trái hình 1.2, còn trạng
thái kết thúc ở bên phải hình 1.2. Tơng ứng với các quy tắc chuyển dịch các quân, ta có
bốn toán tử:
up
(đẩy quân lên trên),
down
(đẩy quân xuống dới),
left
(đẩy quân sang
trái),
right
(đẩy quân sang phải). Rõ rng l, các toán tử ny chỉ l các toán tử bộ phận;
chẳng hạn, từ trạng thái ban đầu (hình 1.2 bên trái), ta chỉ có thể áp dụng các toán tử
down, left, right
.
Trong các ví dụ trên việc tìm ra một biểu diễn thích hợp để mô tả các trạng thái
của vấn đề l khá dễ dng v tự nhiên. Song trong nhiều vấn đề việc tìm hiểu đợc biểu
diễn thích hợp cho các trạng thái của vấn đề l hon ton không đơn giản. Việc tìm ra
dạng biểu diễn tốt cho các trạng thái đóng vai trò hết sức quan trọng trong quá trình giải
quyết một vấn đề. Có thể nói rằng, nếu ta tìm đợc dạng biểu diễn tốt cho các trạng thái
của vấn đề, thì vấn đề hầu nh đã đợc giải quyết.
Ví dụ 2
: Vấn đề triệu phú v kẻ cớp. Có ba nh triệu phú v ba tên cớp ở bên bờ
tả ngạn một con sông, cùng một chiếc thuyền chở đợc một hoặc hai ngời. Hãy tìm
cách đa mọi ngời qua sông sao cho không để lại ở bên bờ sông kẻ cớp nhiều hơn
triệu phú. Đơng nhiên trong bi toán ny, các toán tử tơng ứng với các hnh động chở
1 hoặc 2 ngời qua sông. Nhng ở đây ta cần lu ý rằng, khi hnh động xẩy ra (lúc
thuyền đang bơi qua sông) thì ở bên bờ sông thuyền vừa dời chỗ, số kẻ cớp không đợc
nhiều hơn số triệu phú. Tiếp theo ta cần quyết định cái gì l trạng thái của vấn đề.
ở
đây
ta không cần phân biệt các nh triệu phú v các tên cớp, m chỉ số lợng của họ ở bên
bờ sông l quan trọng. Để biểu diễn các trạng thái, ta sử dụng bộ ba (a, b, k), trong đó a
l số triệu phú, b l số kẻ cớp ở bên bờ tả ngạn vo các thời điểm m thuyền ở bờ ny
hoặc bờ kia, k = 1 nếu thuyền ở bờ tả ngạn v k = 0 nếu thuyền ở bờ hữu ngạn. Nh vậy,
không gian trạng thái cho bi toán triệu phú v kẻ cớp đợc xác định nh sau:
Trạng thái ban đầu l (3, 3, 1).
Các toán tử. Có năm toán tử tơng ứng với hnh động thuyền chở qua sông 1 triệu
phú, hoặc 1 kẻ cớp, hoặc 2 triệu phú, hoặc 2 kẻ cớp, hoặc 1 triệu phú v 1 kẻ cớp.
Trạng thái kết thúc l (0, 0, 0).
1.5 Các chiến lợc tìm kiếm
Nh ta đã thấy trong mục 1.1, để giải quyết một vấn đề bằng tìm kiếm trong
không gian trạng thái, đầu tiên ta cần tìm dạng thích hợp mô tả các trạng thái cảu vấn
đề. Sau đó cần xác định:
Trạng thái ban đầu.
Tập các toán tử.
Tập T các trạng thái kết thúc. (T có thể không đợc xác định cụ thể gồm các trạng
thái no m chỉ đợc chỉ định bởi một số điều kiện no đó).
Giả sử u l
một trạng thái no đó v R l một toán tử biến đổi u thnh v. Ta sẽ gọi
v l trạng thái kề u, hoặc v đợc sinh ra từ trạng thái u bởi toán tử R. Quá trình áp dụng
các toán tử để sinh ra các trạng thái kề u đợc gọi l phát triển trạng thái u. Chẳng hạn,
trong bi toán toán số, phát triển trạng thái ban đầu (hình 2 bên trái), ta nhận đợc ba
trạng thái kề (hình 1.3).

http://blogthuthuat.com


inh Mnh Tng Trang 7
Khi chúng ta biểu diễn một vấn đề cần giải quyết thông qua các trạng thái v các
toán tử thì việc tìm lời giải của vấn đề đợc quy về việc tìm đờng đi từ trạng thái ban
đầu tới một trạng thái kết thúc no đó.
Có thể phân các chiến lợc tìm kiếm thnh hai loại:
Các chiến lợc tìm kiếm mù. Trong các chiến lợc tìm kiếm ny, không có một
sự hớng dẫn no cho sự tìm kiếm, m ta chỉ phát triển các trạng thái ban đầu cho tới
khi gặp một trạng thái đích no đó. Có hai kỹ thuật tìm kiếm mù, đó l tìm kiếm theo bề
rộng v tìm kiếm theo độ sâu.
T tởng của tìm kiếm theo bề rộng l các trạng thái đợc phát triển theo thứ tự
m chúng đợc sinh ra, tức l trạng thái no đợc sinh ra trớc sẽ đợc phát triển trớc.
Trong nhiều vấn đề, dù chúng ta phát triển các trạng thái theo hệ thống no (theo
bề rộng hoặc theo độ sâu) thì số lợng các trạng thái đợc sinh ra trớc khi ta gặp trạng
thái đích thờng l cực kỳ lớn. Do đó các thuật toán tìm kiếm mù kém hiệu quả, đòi hỏi
rất nhiều không gian v thời gian. Trong thực tế, nhiều vấn đề không thể giải quyết đợc
bằng tìm kiếm mù.
Tìm kiếm kinh nghiệm (tìm kiếm heuristic). Trong rất nhiều vấn đề, chúng ta có
thể dựa vo sự hiểu biết của chúng ta về vấn đề, dựa vo kinh nghiệm, trực giác, để đánh
giá các trạng thái. Sử dụng sự đánh giá các trạng thái để hớng dẫn sự tìm kiếm: trong
quá trình phát triển các trạng thái, ta sẽ chọn trong số các trạng thái chờ phát triển, trạng
thái đ
ợc đánh giá l tốt nhất để phát triển. Do đó tốc độ tìm kiếm sẽ nhanh hơn. Các
phơng pháp tìm kiếm dựa vo sự đánh giá các trạng thái để hớng dẫn sự tìm kiếm gọi
chung l các phơng pháp tìm kiếm kinh nghiệm.
Nh vậy chiến lợc tìm kiếm đợc xác định bởi chiến lợc chọn trạng thái để phát
triển ở mỗi bớc. Trong tìm kiếm mù, ta chọn trạng thái để phát triển theo thứ tự m
đúng đợc sinh ra; còn trong tìm kiếm kinh nghiệm ta chọn trạng thái dựa vo sự đánh
giá các trạng thái.
Cây tìm kiếm

http://blogthuthuat.com


inh Mnh Tng Trang 8
Chúng ta có thể nghĩ đến quá trình tìm kiếm nh quá trình xây dựng
cây tìm
kiếm
. Cây tìm kiếm l cây m các đỉnh đợc gắn bởi các trạng thái của không gian trạng
thái. Gốc của cây tìm kiếm tơng ứng với trạng thái ban đầu. Nếu một đỉnh ứng với
trạng thái u, thì các đỉnh con của nó ứng với các trạng thái v kề u. Hình 1.4a l đồ thị
biểu diễn một không gian trạng thái với trạng thái ban đầu l A, hình 1.4b l cây tìm
kiếm tơng ứng với không gian trạng thái đó.
Mỗi chiến lợc tìm kiếm trong không gian trạng thái tơng ứng với một phơng
pháp xây dựng cây tìm kiếm. Quá trình xây dựng cây bắt đầu từ cây chỉ có một đỉnh l
trạng thái ban đầu. Giả sử tới một bớc no đó trong chiến lợc tìm kiếm, ta đã xây
dựng đợc một cây no đó, các lá của cây tơng ứng với các trạng thái cha đợc phát
triển. Bớc tiếp theo phụ thuộc vo chiến lợc tìm kiếm m một đỉnh no đó trong các lá
đợc chọn để phát triển. Khi phát triển đỉnh đó, cây tìm kiếm đợc mở rộng bằng cách
thêm vo các đỉnh con của đỉnh đó. Kỹ thuật tìm kiếm theo bề rộng (theo độ sâu) tơng
ứng với phơng pháp xây dựng cây tìm kiếm theo bề rộng (theo độ sâu).
1.6 Các chiến lợc tìm kiếm mù
Trong mục ny chúng ta sẽ trình by hai chiến lợc tìm kiếm mù: tìm kiếm theo
bề rộng v tìm kiếm theo độ sâu. Trong tìm kiếm theo bề rộng, tại mỗi bớc ta sẽ chọn
trạng thái để phát triển l trạng thái đợc sinh ra trớc các trạng thái chờ phát triển khác.
Còn trong tìm kiếm theo độ sâu, trạng thái đợc chọn để phát triển l
trạng thái đợc
sinh ra sau cùng trong số các trạng thái chờ phát triển.
Chúng ta sử dụng danh sách L để lu các trạng thái đã đợc sinh ra v chờ đợc
phát triển. Mục tiêu của tìm kiếm trong không gian trạng thái l tìm đờng đi từ trạng
thái ban đầu tới trạng thái đích, do đó ta cần lu lại vết của đờng đi. Ta có thể sử dụng
hm father để lu lại cha của mỗi đỉnh trên đờng đi,
father
(v) = u nếu cha của đỉnh v l
u.
1.6.1

Tìm kiếm theo bề rộng
Thuật toán tìm kiếm theo bề rộng đợc mô tả bởi thủ tục sau:
procedure
Breadth_First_Search
;
begin

http://blogthuthuat.com


inh Mnh Tng Trang 9
1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu;
2.
loop do
2.1
if
L rỗng
then
{
thông báo tìm kiếm thất bại
;

stop};
2.2

Loại trạng thái u ở đầu danh sách L
;
2.3
if
u l trạng thái kết thúc
then
{
thông báo tìm kiếm thnh công
; stop};
2.4
for
mỗi trạng thái v kề u
do {
Đặt v vo cuối danh sách L
;
father(v) <- u
}
end;
Chúng ta có một số nhận xét sau đây về thuật toán tìm kiếm theo bề rộng:
Trong tìm kiếm theo bề rộng, trạng thái no đợc sinh ra trớc sẽ đợc phát triển
trớc, do đó danh sách L đợc xử lý nh hng đợi. Trong bớc 2.3, ta cần kiểm tra xem
u có l trạng thái kết thúc hay không. Nói chung các trạng thái kết thúc đợc xác định
bởi một số điều kiện no đó, khi đó ta cần kiểm tra xem u có thỏa mãn các điều kiện đó
hay không.

Nếu bi toán có nghiệm (tồn tại đờng đi từ trạng thái ban đầu tới trạng thái
đích), thì thuật toán tìm kiếm theo bề rộng sẽ tìm ra nghiệm, đồng thời đờng đi tìm
đợc sẽ l ngắn nhất. Trong trờng hợp bi toán vô nghiệm v không gian trạng thái hữu
hạn, thuật toán sẽ dừng v cho thông báo vô nghiệm.

Đánh giá tìm kiếm theo bề rộng
Bây giờ ta đánh giá thời gian v bộ nhớ m tìm kiếm theo bề rộng đòi hỏi. Giả sử
rằng, mỗi trạng thái khi đợc phát triển sẽ sinh ra b trạng thái kề. Ta sẽ gọi b l
nhân tố
nhánh
. Giả sử rằng, nghiệm của bi toán l đờng đi có độ di d. Bởi nhiều nghiệm có
thể đợc tìm ra tại một đỉnh bất kỳ ở mức d của cây tìm kiếm, do đó số đỉnh cần xem xét
để tìm ra nghiệm l:
1 + b + b
2
+ + b
d-1
+ k
Trong đó k có thể l 1, 2, , b
d
. Do đó số lớn nhất các đỉnh cần xem xét l:
1 + b + b
2
+ + b
d

Nh vậy, độ phức tạp thời gian của thuật toán tìm kiếm theo bề rộng l O(b
d
). Độ
phức tạp không gian cũng l O(b
d
), bởi vì ta cần lu vo danh sách L tất cả các đỉnh của
cây tìm kiếm ở mức d, số các đỉnh ny l b
d
.
Để thấy rõ tìm kiếm theo bề rộng đòi hỏi thời gian v không gian lớn tới mức no,
ta xét trờng hợp nhân tố nhánh b = 10 v độ sâu d thay đổi. Giả sử để phát hiện v kiểm
tra 1000 trạng thái cần 1 giây, v lu giữ 1 trạng thái cần 100 bytes. Khi đó thời gian v
không gian m thuật toán đòi hỏi đợc cho trong bảng sau:

http://blogthuthuat.com


inh Mnh Tng Trang 10
Độ sâu d Thời gian Không gian
4 11 giây 1 megabyte
6 18 giây 111 megabytes
8 31 giờ 11 gigabytes
10 128 ngy 1 terabyte
12 35 năm 111 terabytes
14 3500 năm 11.111 terabytes
1.6.2

Tìm kiếm theo độ sâu
Nh ta đã biết, t tởng của chiến lợc tìm kiếm theo độ sâu l, tại mỗi bớc trạng
thái đợc chọn để phát triển l trạng thái đợc sinh ra sau cùng trong số các trạng thái
chờ phát triển. Do đó thuật toán tìm kiếm theo độ sâu l hon ton tơng tự nh thuật
toán tìm kiếm theo bề rộng, chỉ có một điều khác l, ta xử lý danh sách L các trạng thái
chờ phát triển không phải nh hng đợi m nh ngăn xếp. Cụ thể l trong bớc 2.4 của
thuật toán tìm kiếm theo bề rộng, ta cần sửa lại l Đặt v vo
đầu
danh sách L.
Sau đây chúng ta sẽ đa ra các nhận xét so sánh hai chiến lợc tìm kiếm mù:
Thuật toán tìm kiếm theo bề rộng luôn luôn tìm ra nghiệm nếu bi toán có
nghiệm. Song không phải với bất kỳ bi toán có nghiệm no thuật toán tìm kiếm theo độ
sâu cũng tìm ra nghiệm! Nếu bi toán có nghiệm v không gian trạng thái hữu hạn, thì
thuật toán tìm kiếm theo độ sâu sẽ tìm ra nghiệm. Tuy nhiên, trong trờng hợp không
gian trạng thái vô hạn, thì có thể nó không tìm ra nghiệm, lý do l ta luôn luôn đi xuống
theo độ sâu, nếu ta đi theo một nhánh vô hạn m nghiệm không nằm trên nhánh đó thì
thuật toán sẽ không dừng. Do đó ngời ta khuyên rằng, không nên áp dụng tìm kiếm
theo dộ sâu cho các bi toán có cây tìm kiếm chứa các nhánh vô hạn.
Độ phức tạp của thuật toán tìm kiếm theo độ sâu.
Giả sử rằng, nghiệm của bi toán l đờng đi có độ di d, cây tìm kiếm có nhân tố
nhánh l b v có chiều cao l d. Có thể xẩy ra, nghiệm l đỉnh ngoi cùng bên phải trên
mức d của cây tìm kiếm, do đó độ phức tạp thời gian của tìm kiếm theo độ sâu trong
trờng hợp xấu nhất l O(b
d
), tức l cũng nh tìm kiếm theo bề rộng. Tuy nhiên, trên
thực tế đối với nhiều bi toán, tìm kiếm theo độ sâu thực sự nhanh hơn tìm kiếm theo bề
rộng. Lý do l tìm kiếm theo bề rộng phải xem xét ton bộ cây tìm kiếm tới mức d-1, rồi
mới xem xét các đỉnh ở mức d. Còn trong tìm kiếm theo độ sâu, có thể ta chỉ cần xem
xét một bộ phận nhỏ của cây tìm kiếm thì đã tìm ra nghiệm.
Để đánh giá độ phức tạp không gian của tìm kiếm theo độ sâu ta có nhận xét rằng,
khi ta phát triển một đỉnh u trên cây tìm kiếm theo độ sâu, ta chỉ cần lu các đỉnh cha
đợc phát triển m chúng l các đỉnh con của các đỉnh nằm trên đờng đi từ gốc tới đỉnh
u. Nh vậy đối với cây tìm kiếm có nhân tố nhánh b v độ sâu lớn nhất l d, ta chỉ cần
lu ít hơn db đỉnh. Do đó độ phức tạp không gian của tìm kiếm theo độ sâu l O(db),
trong khi đó tìm kiếm theo bề rộng đòi hỏi không gian nhớ O(b
d
)!

http://blogthuthuat.com


inh Mnh Tng Trang 11
1.6.3

Các trạng thái lặp
Nh ta thấy trong mục 1.2, cây tìm kiếm có thể chứa nhiều đỉnh ứng với cùng một
trạng thái, các trạng thái ny đợc gọi l trạng thái lặp. Chẳng hạn, trong cây tìm kiếm
hình 4b, các trạng thái C, E, F l các trạng thái lặp. Trong đồ thị biểu diễn không gian
trạng thái, các trạng thái lặp ứng với các đỉnh có nhiều đờng đi dẫn tới nó từ trạng thái
ban đầu. Nếu đồ thị có chu trình thì cây tìm kiếm sẽ chứa các nhánh với một số đỉnh lập
lại vô hạn lần. Trong các thuật toán tìm kiếm sẽ lãng phí rất nhiều thời gian để phát triển
lại các trạng thái m ta đã gặp v đã phát triển. Vì vậy trong quá trình tìm kiếm ta cần
tránh phát sinh ra các trạng thái m ta đã phát triển. Chúng ta có thể áp dụng một trong
các giải pháp sau đây:
1. Khi phát triển đỉnh u, không sinh ra các đỉnh trùng với cha của u.
2. Khi phát triển đỉnh u, không sinh ra các đỉnh trùng với một đỉnh no đó nằm trên
đờng đi dẫn tới u.
3. Không sinh ra các đỉnh m nó đã đợc sinh ra, tức l chỉ sinh ra các đỉnh mới.
Hai giải pháp đầu dễ ci đặt v không tốn nhiều không gian nhớ, tuy nhiên các
giải pháp ny không tránh đợc hết các trạng thái lặp.
Để thực hiện giải pháp thứ 3 ta cần lu các trạng thái đã phát triển vo tập Q, lu
các trạng thái chờ phát triển vo danh sách L. Đơng nhiên, trạng thái v lần đầu đợc
sinh ra nếu nó không có trong Q v L. Việc lu các trạng thái đã phát triển v kiểm tra
xem một trạng thái có phải lần đầu đợc sinh ra không đòi hỏi rất nhiều không gian v
thời gian. Chúng ta có thể ci đặt tập Q bởi bảng băm (xem [ ]).
1.6.4

Tìm kiếm sâu lặp
Nh chúng ta đã nhận xét, nếu cây tìm kiếm chứa nhánh vô hạn, khi sử dụng tìm
kiếm theo độ sâu, ta có thể mắc kẹt ở nhánh đó v không tìm ra nghiệm. Để khắc phục
hon cảnh đó, ta tìm kiếm theo độ sâu chỉ tới mức d no đó; nếu không tìm ra nghiệm, ta
tăng độ sâu lên d+1 v lại tìm kiếm theo độ sâu tới mức d+1. Quá trình trên đợc lặp lại
với d lần lợt l 1, 2, dến một độ sâu max no đó. Nh vậy, thuật toán tìm kiếm sâu
lặp (iterative deepening search) sẽ sử dụng thủ tục tìm kiếm sâu hạn chế (depth_limited
search) nh thủ tục con. Đó l thủ tục tìm kiếm theo độ sâu, nhng chỉ đi tới độ sâu d
no đó rồi quay lên.
Trong thủ tục tìm kiếm sâu hạn chế, d l tham số độ sâu, hm depth ghi lại độ sâu
của mỗi đỉnh
procedure
Depth_Limited_Search(d)
;
begin
1. Khởi tạo danh sách L chỉ chứa trạng thái ban đầu u
0
;
depth(u
0
) 0
;
2.
loop do
2.1
if
L rỗng
then
{
thông báo thất bại
; stop};

http://blogthuthuat.com


inh Mnh Tng Trang 12
2.2

Loại trạng thái u ở đầu danh sách L
;
2.3
if
u l trạng thái kết thúc
then
{
thông báo thnh công
; stop};
2.4
if
depth(u) <= d
then
for
mỗi trạng thái v kề u
do
{
Đặt v vo đầu danh sách L
;
depth(v) depth(u) + 1
};
end;

procedure
Depth_Deepening_Search
;
begin
for
d 0
to
max
do
{
Depth_Limited_Search(d)
;
if
thnh công
then exit}
end;
Kỹ thuật tìm kiếm sâu lặp kết hợp đợc các u điểm của tìm kiếm theo bề rộng v
tìm kiếm theo độ sâu. Chúng ta có một số nhận xét sau:
Cũng nh tìm kiếm theo bề rộng, tìm kiếm sâu lặp luôn luôn tìm ra nghiệm (nếu
bi toán có nghiệm), miễn l ta chọn độ sâu mã đủ lớn.
Tìm kiếm sâu lặp chỉ cần không gian nhớ nh tìm kiếm theo độ sâu.
Trong tìm kiếm sâu lặp, ta phải phát triển lặp lại nhiều lần cùng một trạng thái.
Điều đó lm cho ta có cảm giác rằng, tìm kiếm sâu lặp lãng phí nhiều thời gian. Thực ra
thời gian tiêu tốn cho phát triển lặp lại các trạng thái l không đáng kể so với thời gian
tìm kiếm theo bề rộng. Thật vậy, mỗi lần gọi thủ tục tìm kiếm sâu hạn chế tới mức d,
nếu cây tìm kiếm có nhân tố nhánh l b, thì số đỉnh cần phát triển l:
1 + b + b
2
+ + b
d

Nếu nghiệm ở độ sâu d, thì trong tìm kiếm sâu lặp, ta phải gọi thủ tục tìm kiếm
sâu hạn chế với độ sâu lần lợt l 0, 1, 2, , d. Do đó các đỉnh ở mức 1 phải phát triển
lặp d lần, các đỉnh ở mức 2 lặp d-1 lần, , các đỉnh ở mức d lặp 1 lần. Nh vậy tổng số
đỉnh cần phát triển trong tìm kiếm sâu lặp l:
(d+1)1 + db + (d-1)b
2
+ + 2b
d-1
+ 1b
d

Do đó thời gian tìm kiếm sâu lặp l O(b
d
).
Tóm lại, tìm kiếm sâu lặp có độ phức tạp thời gian l O(b
d
) (nh tìm kiếm theo bề
rộng), v có độ phức tạp không gian l O(biểu diễn) (nh tìm kiếm theo độ sâu). Nói
chung, chúng ta nên áp dụng tìm kiếm sâu lặp cho các vấn đề có không gian trạng thái
lớn v độ sâu của nghiệm không biết trớc.

http://blogthuthuat.com


inh Mnh Tng Trang 13
1.7 Quy vấn đề về các vấn đề con. Tìm kiếm trên đồ thị v/hoặc.
1.7.1

Quy vấn đề về các vấn đề con:
Trong mục 1.1, chúng ta đã nghiên cứu việc biểu diễn vấn đề thông qua các trạng
thái v các toán tử. Khi đó việc tìm nghiệm của vấn đề đợc quy về việc tìm đờng trong
không gian trạng thái. Trong mục ny 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. Quy vấn đề về
các vấn đề con (còn gọi l rút gọn vấn đề) l một phơng pháp đợc sử dụng rộng rãi
nhất để giải quyết các vấn đề. Trong đời sống hng ngy, cũng nh trong khoa học kỹ
thuật, mỗi khi gặp một vấn đề cần giải quyết, ta vẫn thờng cố gắng tìm cách đa nó về
các vấn đề đơn giản hơn. Quá trình rút gọn vấn đề sẽ đợc tiếp tục cho tới khi ta dẫn tới
các vấn đề con có thể giải quyết đợc dễ dng. Sau đây chúng ta xét một số vấn đề.
Vấn đề tính tích phân bất định
Giả sử ta cần tính một tích phân bất định, chẳng hạn
(xe
x

+ x
3
) dx. Quá trình
chúng ta vẫn thờng lm để tính tích phân bất định l nh sau. Sử dụng các quy tắc tính
tích phân (quy tắc tính tích phân của một tổng, quy tắc tính tích phân từng phần ), sử
dụng các phép biến đổi biến số, các phép biến đổi các hm (chẳng hạn, các phép biến
đổi lợng giác), để đa tích phân cần tính về tích phân của các hm số sơ cấp m
chúng ta đã biết cách tính. Chẳng hạn, đối với tích phân
(xe
x

+ x
3
) dx, áp dụng quy
tắc tích phân của tổng ta đa về hai tích phân
xe
x
dx v x
3
dx.
á
p dụng quy tắc tích
phân từng phần ta đa tích phân
xe
x
dx về tích phân
e
x
dx. Quá trình trên có thể biểu
diễn bởi đồ thị trong hình 1.5.
Các tích phân
e
x
dx v
x
3
dx l các tích phân cơ bản đã có trong bảng tích phân.
Kết hợp các kết quả của các tích phân cơ bản, ta nhận đợc kết quả của tích phân đã
cho.
Chúng ta có thể biểu diễn việc quy một vấn đề về các vấn đề con cơ bởi các trạng
thái v các toán tử.
ở
đây, bi toán cần giải l trạng thái ban đầu. Mỗi cách quy bi toán
về các bi toán con đợc biểu diễn bởi một toán tử, toán tử AB, C biểu diễn việc quy
bi toán A về hai bi toán B v C. Chẳng hạn, đối với bi toán tính tích phân bất định, ta
có thể xác định các toán tử dạng:
(f
1
+ f
2
) dx f
1
dx, f
2
dx v u dv v du

http://blogthuthuat.com


inh Mnh Tng Trang 14
Các trạng thái kết thúc l các bi toán sơ cấp (các bi toán đã biết cách giải).
Chẳng hạn, trong bi toán tính tích phân, các tích phân cơ bản l các trạng thái kết thúc.
Một điều cần lu ý l, trong không gian trạng thái biểu diễn việc quy vấn đề về các vấn
đề con, các toán tử có thể l đa trị, nó biến đổi một trạng thái thnh nhiều trạng thái
khác.
Vấn đề tìm đờng đi trên bản đồ giao thông
Bi toán ny đã đợc phát triển nh bi toán tìm đờng đi trong không gian trạng
thái (xem 1.1), trong đó mỗi trạng thái ứng với một thnh phố, mỗi toán tử ứng với một
con đờng nối, nối thnh phố ny với thnh phố khác. Bây giờ ta đa ra một cách biểu
diễn khác dựa trên việc quy vấn đề về các vấn đề con. Giả sử ta có bản đồ giao thông
trong một vùng lãnh thổ (xem hình 1.6). Giả sử ta cần tìm đờng đi từ thnh phố A tới
thnh phố B. Có con sông chảy qua hai thnh phố E v G v có cầu qua sông ở mỗi
thnh phố đó. Mọi đờng đi từ A đến B chỉ có thể qua E hoặc G. Nh vậy bi toán tìm
đờng đi từ A đến B đợc quy về:
1) Bi toán tìm đờng đi từ A đến B qua E (hoặc)
2) Bi toán tìm đờng đi từ A đến b qua G.
Mỗi một trong hai bi toán trên lại có thể phân nhỏ nh sau
1) Bi 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)
1.2 Tìm đờng đi từ E đến B.
2) Bi 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.

Xem chi tiết: Giao_trinh_Tri_Tue_Nhan_Tao___Dinh_Manh_Tuong.pdf