Chia sẻ miễn phí cho các bạn tài liệu: Phương pháp nhánh và cận.
Tãm t¾t luËn v¨n Ph­¬ng ph¸p nh¸nh vµ cËn cµi ®Æt trªn c©y nhÞ ph©n
Tr©n TriÖu Hïng
Hµ Néi 6/2000
C96B-
CNTT
2
(222)
(231)
(223)
(213)
(211)
(311)
(312)
(322)
(333)
(212)
(313)
(232)
(112)
(
111
)
(123)
(113)
(131)
(121)
(322)
(122)
(132)
(133)
(233)
(321)
(323)
(221)
- C¸c to¸n tö chuyÓn tr¹ng th¸i: Tõ mét tr¹ng th¸i ®· cho ®Õn mét
tr¹ng th¸i kÕ tiÕp.
- Tr¹ng th¸i ®Ých.- Chi phÝ kÌm theo mçi to¸n tö chuyÓn tr¹ng th¸i (cã thÓ cã).
To¸n tö : PhÐp biÕn ®æi tr¹ng th¸i ®­îc biÓu diÔn hoÆc coi nh­ hµm, ¸nh x¹ tõ kh«ng gian tr¹ng th¸i vµo chÝnh nã. HoÆc c¸c quy t¾c s¶n xuÊt(Production rules) d­íi d¹ng S
i
® S
j

M« t¶ c¸c tr¹ng th¸i: C¸c x©u ký hiÖu, vÐct¬, m¶ng mét chiÒu, hai
chiªu, c©y, danh s¸ch...BiÓu diÔn b»ng ®å thÞ: Cho ®å thÞ G=(N,A) : N: Nót (node). A : Lµ cung (a,b) cã h­íng.Ta cã thÓ hiÓu:
Nót : lµ c¸c tr¹ng th¸i.Cung : To¸n tö chuyÓn tr¹ng th¸i. (Cha chuyÓn sang con).
NÕu tr¹ng th¸i ®Çu lµ gèc cña c©y th× lêi gi¶i lµ mét ®­êng ®i tõ gèc n ®Õn nót ®Ých.Bµi to¸n th¸p hµ néi víi n =3To¸n tö truyÓn tr¹ng th¸ilµ di chuyÓn vÞ trÝ cña c¸c ®Üa®­îc ®¸nh sè

II. Ph­êng ph¸p t×m kiÕm lêi gi¶i
II.1.M« h×nh trªn ®å thÞNÕu biÓu diÔn bµi toµn thµnh ®å thÞ trong kh«ng gian th¹ng th¸i lêi gi¶i cña bµi to¸n lµ t×m ®­¬ng ®i trªn mét ®å thÞ, tõ mét ®iÓm xuÊt ph¸t øng víi tr¹ng th¸i ®Çu ®Õn mét ®iÓm ®Ých, øng víi tr¹ng th¸i kÕt thóc cña bµi to¸n.
Mçi nót ® 1 tr¹ng th¸i cña bµi to¸n.
Tuy nhiªn t¹i mçi nót cßn cÇn cã nhiÒu th«ng tin kh¸c n÷a thÓ hiÖn quan hÖ cha, con ®é s©u, chi phÝ (path cost), trong khi tr¹ng th¸i kh«ng thÓ hiÖn râ nh÷ng ®iÒu ®ã.
C¸c cung lµ mét phÐp to¸n, mét quan hÖ ®Ó chuyÓn tõ tr¹ng th¸i
nµy sang tr¹ng th¸i kh¸c .ThuËt gi¶i tæng qu¸t:
 XuÊt ph¸t tõ nót tr¹ng th¸i ban ®Çu:
LÆp: NÕu kh«ng cã nót ®Ó triÓn khai tiÕp ® thÊt b¹i (v« nghiÖm).
Để tìm kiếm lời giải của một bài toán ta có nhiều phương pháp khác nhau. Nếu thể hiện bài toán dưới dạng đồ thị trong không gian trạng thái thì việc tìm lời giả

---

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=375207&pageNumber=2&documentKindID=1

---