Page 18 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 18
15-8 โครงสร้างข้อมูลแ ละข ั้นต อนว ิธี 56
ตัวอย่างโครงสร้างแ บบกราฟด ังภาพท ่ี 15.5
34 53
49 54
ภาพท ่ี 15.5 การจ ัดเก็บขอ้ มูลโครงสรา้ งแ บบก ราฟ
ขั้นต อนว ิธีก ารค ้นหาข้อมูลตามโครงสร้างแบบนี้แบ่งอ อกได้เป็น 2 กลุ่ม ได้แก่
- การค้นห าแบบไบล ด์ (Blind search) และ
- การค้นหาแบบฮิวร ิสติก (Heuristic search)
2.1 การคน้ หาแบบไบล ด์ เป็นการค ้นหาโดยอาศัยทิศทางเป็นตัวก�ำหนด เช่น จ ากซ ้ายสุดไปขวาสุด หรือจาก
บนลงล่าง ซึ่งตัวอย่างขั้นตอนวิธีในลักษณะนี้ประกอบด้วย การค้นหาแบบกว้าง (breadth first search) การค้นหา
แบบล ึก (depth first search) เป็นต้น
ตวั อยา่ งที่ 15.1 จงแ สดงให้เห็นถ ึงรูปแบบข ้ันต อนว ิธีการค ้นห าแบบไบลด์ โดยใช้ก ารค้นหาแ บบก ว้าง ส�ำหรับข ้อมูลต ่อ
ไปนี้
ก�ำหนดให้ข ้อมูลจัดเก็บในล ักษณะของโครงสร้างต้นไม้ด ังน้ี
53
34 49 56
25 29 54
ก�ำหนดให้ค่าท่ีต้องการค้นหาคือ 49
แนวคิดการค้นหาจะเริ่มจ ากทางซ ้ายส ุดไปท างข วาส ุดท ีละร ะดับจ นพ บโหนดเป้าหมาย
วิธีก ารค ้นหาเป็นดังนี้
1. เปรียบเทียบโหนดแ รกค่า 53 กับค ่าท่ีต้องการค้นหา 49 ซ่ึงไม่ใช่
2. เปรียบเทียบโหนดลูกท างซ้ายสุดข อง 53 ซึ่งก็ค ือ 34 กับค ่า 49 ซ่ึงไม่ใช่
3. เปรียบเทียบโหนดถัดมาซึ่งก็คือ 49 กับค่า 49 ซึ่งใช่
4. หยุดการค ้นหา
