ngocxit_vn
New Member
Chia sẻ miễn phí cho các bạn tài liệu: Trí tuệ nhân tạo
TiÓ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 Ketnooi, 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í
TiÓ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 Ketnooi, 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í