Page 21 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 21
ขั้นตอนวิธีก ารค ้นหาข ้อมูล 15-11
4. พิจารณาโหนดท่ีติดกับโหนด C ซึ่งก็คือโหนด D และ A โดยโหนด A ได้รับการเลือกแล้วจะไม่น�ำมา
พิจารณาเปรียบเทียบอีกดังน ั้นจึงเหลือแค่โหนด D ท่ีได้ร ับก ารเลือกเป็นโหนดต ่อไป
32
D2B 3
E0
36
A5 C
4 2
5. พิจารณาโหนดท่ีติดกับโหนด D ซ่ึงก็คือโหนด A, B และ C โดยโหนด B เป็นโหนดเดียวท่ียังไม่ได้เลือก
ดังน้ัน โหนด B จึงได้ร ับการเลือกเป็นโหนดต่อไป
32
D2B 3
E0
36
A5 C
4 2
6. ใช้ว ิธีพ ิจารณาเหมือนเดิมจะได้โหนดสุดท้ายท ี่เลือกซึ่งก็ค ือ โหนด E การค้นหาบ รรลุเป้าหมาย
32
2B
D 6 3 E0
3
A5 C
4 2
เส้นท างจ ากโหนด A ถึง E คือ เส้นท าง A -> C -> D -> B-> E มีร ะยะท างร วม = 5 + 6 + 2 + 3 = 16
จากต ัวอย่างเห็นได้ว่า การค ้นหาล ักษณะน ้ีได้ค �ำตอบในเวลาท ่ีร วดเร็ว แต่ไม่รับป ระกันว่าค �ำตอบท่ีได้ม าเป็น
ค�ำตอบท่ีดีท่ีสุด ซึ่งจากตัวอย่างข้างต้นเส้นทางท่ีดีที่สุดคือ A -> D -> B -> E มีระยะทางรวม = 3 + 2 + 3 = 8 ซ่ึงมี
ระยะน้อยกว่าเส้นทางที่ได้จาก best-first search ซึ่งโดยท่ัวไปแล้ววิธีการแบบฮิวริสติกจะได้ค�ำตอบท่ีดีแต่ไม่
รับป ระกันว ่าเป็นค �ำตอบท ี่ดีที่สุด
