Page 19 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 19
ขั้นตอนวิธีก ารค้นหาข้อมูล 15-9
2.2 การค น้ หาแบบฮ ิวริสติก พจนานุกรมอ อนไลน์ (dict.longdo.com) ให้ค วามหมายของ ฮิวร ิส ติก ว่าเป็น
วิธีการแก้ปัญหาที่ไม่มีแนวทางหรือกฎเกณฑ์ที่ชัดเจน เช่น ในเกมหมากรุก คงมีแ ต่การทดลองหรือคาดเดาหลายๆ ทาง
ให้ตัดสินเลือกทางที่คิดว่าจะได้ผลดีที่สุด ซึ่งมักจะใช้ผลจากประสบการณ์ท่ีผ่านมา ตรงข้ามกับสามัญส�ำนึก
(common sense) ตัวอย่างวิธีการแบบฮิวร ิสติก ในช ีวิตประจ�ำวัน เช่น ถ ้าแก้ปัญหาท่ีเป็นนามธรรมยากต่อความเข้าใจ
ใหห้ าตวั อยา่ งทเี่ ปน็ รปู ธรรมจะไดเ้ ขา้ ใจและเหน็ ปญั หาชดั เจนขนึ้ การคน้ หาแบบฮวิ รสิ ตกิ นนั้ เปน็ วธิ กี ารคน้ หาทเี่ หมาะสม
กับข้อมูลจ�ำนวนมาก พ้ืนท่ีการค้นหาขนาดใหญ่ ซึ่งถ้าใช้วิธีการแบบพื้นฐานหรือบรูทฟอร์ซจะใช้เวลานานมาก ดังน้ัน
การคาดเดาหนทางที่น่าจะน�ำไปสู่ค�ำตอบจะช่วยลดเวลาในการประมวลผลในการให้ได้มาซ่ึงค�ำตอบท่ียอมรับได้
ซึ่งข ั้นต อนว ิธแี บบน ี้น ิยมน �ำมาใชก้ ับว ิธกี ารท างป ัญญาป ระดิษฐ์ (Artificial Intelligence) โดยใชค้ วามร ู้เกี่ยวก ับป ัญหา
มาช่วยในการค้นหาโดยความรู้เกี่ยวกับปัญหาจะอยู่ในรูปของฟังก์ชันท่ีเรียกว่า ฟังก์ชันฮิวริสติก ซึ่งจะแปลงค่าสถานะ
ของการค้นหาปัจจุบันเป็นตัวเลขที่ประมาณการว่าเข้าใกล้เป้าหมายท่ีต้องการเพียงใด และใช้เป็นตัวก�ำหนดทิศทาง
ในการค้นหาเช่นต้องการจะเดินทางจากเมือง A ไปเมือง Z ด้วยระยะทางท่ีสั้นท่ีสุด โดยเมืองระหว่าง A และ Z
ประกอบด้วยเมือง B, C, ..., X และ Y ฟังก์ชันฮิวริสติกส�ำหรับปัญหานี้อาจเป็นระยะที่เป็นเส้นตรงที่ลากจากแต่ละ
เมืองถ ึง Z โดยที่ร ะยะท างจ ริงต ้องข ้ึนอ ยู่ก ับค วามค ดเคี้ยวข องถ นน ซ่ึงว ิธีก ารค ้นหาท ี่ใช้ฮ ิวร ิส ติก ได้แก่ การค ้นหาแ บบ
เลือกดีที่สุด (best-first search) การค้นหาแบบปีนเขา (hill-climbing search) การค้นหาโดยใช้การจ�ำลองการอบ
เหนียว (simulated annealing search) การค ้นหาแบบเอส ตาร์ (A* search) และการค ้นหาโดยใช้ร ูปแ บบพันธุกรรม
(genetic search) เป็นต้น
ตัวอย่างท ่ี 15.2 จงแ สดงให้เห็นถ ึงร ูปแ บบข ั้นต อนว ิธีก ารค ้นหาแ บบฮ ิวร ิสติก โดยใช้ข ั้นต อนว ิธีค ้นหาแ บบเลือกด ีท่ีสุด
ในการค้นหาเส้นทางจากโหนด A ถึง โหนด E จากกราฟสองทศิ ทางท่ีมีโหนดประกอบดว้ ย A B C D E และระยะทาง
ระหว่างโหนดก�ำหนดให้มีค่าด ังน้ี
ระยะท างร ะหว่างโหนด A และ โหนด C มีค่าเท่ากับ 5
ระยะท างระหว่างโหนด A และ โหนด D มีค ่าเท่ากับ 3
ระยะท างร ะหว่างโหนด B และ โหนด D มีค ่าเท่ากับ 2
ระยะท างร ะหว่างโหนด B และ โหนด E มีค ่าเท่ากับ 3
ระยะท างร ะหว่างโหนด C และ โหนด D มีค่าเท่ากับ 6
D 2B 3 E
3 6
A5 C
ก�ำหนดให้ฟังก์ชันฮิวร ิส ติกประมาณค่าจากโหนดท ่ีเลือกถึงโหนด E ดังนี้
โหนด A B C D E
0
ค่าฮิวริสติก 4 2 2 3
