Chia sẻ miễn phí cho các bạn tài liệu: Trí tuệ nhân tạoTiÓu luËn kÕt thóc m«n häc: HÖ chuyªn gia
Häc viªn: Lª Thñy Th¹chLíp Cao häc Tin häc khãa 20042006
2
tr×nh trß ch¬i. PhÇn 3: LÊy mét vÝ dô lËp tr×nh trß ch¬i Caro ®Ó minh häa cho hai phÇn ®· ®îc tr×nh bµy.
PhÇn II. Néi dung
AMét sè ph¬ng ph¸p t×m kiÕm lêi gi¶i
I/ T×m kiÕm theo chiÒu s©u vµ t×m kiÕm theo chiÒu réng
§Ó ®a ra ®îc ý tëng cña thuËt gi¶i heuristic, tríc hÕt xin tr×nh bµy
hai ph¬ng ph¸p t×m kiÕm lêi gi¶i c¬ b¶n lµ t×m kiÕm theo chiÒu réng vµ t×m kiÕm theo chiÒu s©u.1.1/ T×m kiÕm theo chiÒu s©u.
T×m kiÕm theo chiÒu s©u chÝnh lµ thösai quay lui. NghÜa lµ ë tr¹ng
th¸i hiÖn t¹i, ta chän mét tr¹ng th¸i kÕ tiÕp lµm tr¹ng th¸i hiÖn t¹i cho ®Õn khi tr¹ng th¸i hiÖn t¹i lµ tr¹ng th¸i ®Ých. NÕu ë tr¹ng th¸i hiÖn t¹i ta kh«ng thÓ biÕn ®æi thµnh tr¹ng th¸i kÕ tiÕp th× ta sÏ quay lui l¹i tr¹ng th¸i tríc tr¹ng th¸i hiÖn t¹i ®Ó chän ®êng kh¸c. NÕu ë tr¹ng th¸i tríc nµy mµ còng kh«ng thÓ biÕn ®æi ®îc n÷a th× ta quay lui l¹i tr¹ng tr¸i kÕ tríc n÷a vµ cø nh thÕ. NÕu ®· quay lui ®Õn tr¹ng th¸i khëi ®Çu mµ vÉn thÊt b¹i th× kÕt luËn lµ kh«ng cã lêi gi¶i.1.2/ T×m kiÕm theo chiÒu réng
T×m kiÕm chiÒu réng mang h×nh ¶nh cña vÕt dÇu loang. Tõ tr¹ng th¸i
ban ®Çu, ta x©y dùng tËp S bao gåm c¸c tr¹ng th¸i kÕ tiÕp cña S. Sau ®ã øng víi mçi tr¹ng th¸i T
k
, trong tËp S ta x©y dùng tËp S
k
bao gåm c¸c tr¹ng th¸i kÕ
tiÕp cña T
k
, råi ghÐp S
k
vµo S. Qu¸ tr×nh nµy cø lÆp l¹i cho ®Õn lóc S cã
chøa tr¹ng th¸i kÕt thóc hoÆc S kh«ng thay ®æi sau khi ®· bæ sung tÊt c¶ S
k
.
1.3/ §¸nh gi¸
T×m kiÕm theo chiÒu s©u vµ t×m kiÕm theo chiÒu réng ®Òu lµ c¸c
ph¬ng ph¸p t×m kiÕm mµ ch¾c ch¾n t×m ra lêi gi¶i. Tuy nhiªn, do b¶n chÊt lµ vÐt c¹n nªn víi nh÷ng bµi to¸n cã kh«ng gian lín th× ta kh«ng thÓ dïng hai ph¬ng ph¸p nµy ®îc. H¬n n÷a, hai ph¬ng ph¸p nµy ®Òu cã tÝnh chÊt “mï qu¸ng” v× chóng kh«ng chó ý ®Õn nh÷ng th«ng tin ë tr¹ng th¸i hiÖn thêi vµ th«ng tin vÒ ®Ých cÇn ®¹t tíi vµ mèi quan hÖ gi÷a chóng. C¸c th«ng tin nµy rÊt quan träng vµ rÊt cã ý nghÜa ®Ó thiÕt kÕ c¸c thuËt gi¶i cã hiÖu qu¶ h¬n.II/ T×m kiÕm leo nói2.1/ Leo nói ®¬n gi¶n.
T×m kiÕm leo nói thùc chÊt chØ lµ mét trêng hîp ®Æc biÖt cña t×m
kiÕm theo chiÒu s©u nhng kh«ng thÓ quay lui. Trong t×m kiÕm leo nói,
Nhiều bài toán phức tạp có thể được phát biểu dưới dạng sau: Cho trước hai trạng thái T0 và TG. Hãy xây dựng chuỗi trạng thái T0, T1, T2, ...Tn (TG) sao cho cos
Dành riêng cho anh em Ket-noi, bác nào cần
download miễn phí bản đầy đủ thì trả lời topic này, Nhóm Mods sẽ gửi tài liệu cho bạn qua hòm tin nhắn nhé.
- Bạn nào có tài liệu gì hay thì up lên đây chia sẻ cùng anh em.
- Ai cần tài liệu gì mà không tìm thấy ở forum, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
source: content/getpagecontent?id=381360&pageNumber=2&documentKindID=1
