Page 20 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 20
15-10 โครงสร้างข ้อมูลแ ละขั้นต อนวิธี
จากโ จทย์ก�ำหนดใ ห้
โหนดเริ่มต้นคือโหนด A
โหนดเป้าห มายคือโหนด E
1. ฟังก ์ชันฮ ิวร ิส ติก ป ระมาณค ่าจ ากโหนดท ่ีเลือก ถึงโหนด E ซึ่งในท ่ีน ี้ค ่าที่ก �ำหนดจ ะแ สดงต ิดก ับโหนดน ้ันๆ
ค่าฮ ิวร ิสติกส �ำหรับโหนด A คือ 4
ค่าฮิวริส ติกส�ำหรับโหนด B คือ 2
ค่าฮ ิวร ิสติกส �ำหรับโหนด C คือ 2
ค่าฮิวร ิสติก ส�ำหรับโหนด D คือ 3
ค่าฮิวร ิสติกส �ำหรับโหนด E คือ 0
3 2 2 3
D B
E0
36
4A 5 C
2
2. เริ่มจ ากโหนด A โดยใช้เครื่องหมายสี่เหล่ียมล้อมโหนดเพ่ือเป็นการก�ำหนดว่าโหนดน้ีได้ถูกเลือกแ ล้ว
3 2 2 3
D B
E0
36
A5 C
4 2
3. พิจารณาโหนดท่ีติดกับโหนด A ซึ่งก็คือโหนด C และ D โดยโหนด C มีค่าฮิวริสติกเท่ากับ 2 และโหนด
D มีค่าฮ ิวริส ติกเท่ากับ 3 จะเห็นว่าค่าของโหนด C น้อยกว่าดังน้ัน จึงเลือกโหนด C
32
D2B 3
E0
36
A5 C
4 2
