การค้นหาแบบฮิวริสติก (Heuristic Search)

Posted by : Antioch วันจันทร์ที่ 24 สิงหาคม พ.ศ. 2558

การค้นหาแบบกำหนดทิศทาง

เป็นการค้นหาแบบที่เริ่มต้นการสำวจจากโหนดหนึ่งไปยังอีกโหนดหนึ่งอาศัยทิศทางเป็นตัวกำหนดการค้นหา ไม่มีข้อมูลอะไรมาเสริมการตัดสินใจ คือการหยิบข้อมูลมาตรวจสอบในขั้นต่อไป ไม่ต้องอาศัยข้อมูลใดๆทั้งสิ้น ตัวอย่าง Depth First Search ,Breadth First Search

การค้นหาDepth First Search

เป้นการค้นหาแบบลึกก่อน กำหนดทิศทางจากรูปโครงสร้างต้นไม้ เริ่มจากRoot เดินลงมาที่ลึกสุดTerminal Node ให้ย้อนขึ้นไปที่กิ่ง แยกต่ำสุดของกิ่งเดียวกัน และยังไม่ทำการสำรวจแล้วทำการสำรวจโหนดในกิ่งนั้น ถ้าพบโหนดที่ต้องการการค้นหาก็สิ้นสุด ถ้าไม่พบก็สำรวจจนถึงปลายทาง ถ้าไม่พบให้ย้อนขึ้นมายังกิ่งแยกต่ำสุดที่ยังไม่สำรวจถัดไปแล้วทำการสำรวจโหนดบนกิ่งแยกนั้น ทำสลับกับไปเรื่อยๆจนพบโหนดที่ต้องการหาหรือสำรวจให้ครบทุกโหนด

เมื่อการค้นหาในกิ่งแรกมาถึงโหนดปลายทาง คือ 4 การค้นหาจะย้ายไปที่โหนดต่ำสุดที่มีกิ่งแยกไม่มีการสำรวจ ในที่นี้คือกิ่งโหนด 3 ให้ทำการสำรวจโหนด 5 ซึ่งเป็นโหนดปลายทาง จากนั้นย้อนไปจุดต่ำสุดในตำแหน่งเดียวกันที่มีกิ่งแยกและกิ่งแยกนั้นไม่มีการสำรวจ ในที่นี้โหนด2 ทำการสำรวจโหนด 6 ทำเช่นนี้ครบทุกโหนด หรือพบโหนดที่ต้องการหาแบบลึกก่อน เมื่อสำรวจโหนดในกิ่งใดกิ่งหนึ่ง ที่เริ่มต้นจากโหนดรากลงมา เราต้องบันทึกว่าโหนดใดบ้างมีกิ่งแยกออกมา

การค้นหาBreadth First Search

เป็นการกำหนดทิศทางการค้นหาที่ทำการสำรวจที่ละระดับของโครงสร้างต้นไม้ ดดยเริ่มจากโหนดรากแล้วลงมาที่ระดับ1จากซ้ายไปขวา จนกว่าจะพบโหนดที่ต้องการ หรือจนครบทุกโหนด เป้นหมายเลขที่กำกับบนโหนด

จะอาศัยการจัดการโครงสร้างข้อมูลแบบคิวมาช่วย เช่นกัน ด้วยวิธีการเช่นเดียวกับการค้นหาแบบลึกก่อน คือให้เริ่มต้นสำรวจที่โหนดเริ่มต้น แล้วนำโหนดที่ข้างเคียงเก็บไว้ในคิว เมื่อสำรวจโหนดเริ่มต้นจนเสร็จ ให้นำข้อมูลในคิวออกมาสำรวจ นำโหนดข้างเคียงที่ไม่ได้สำรวจและไม่ได้อยู่ในคิวใส่ในคิว ทำจนพบโหนดที่ต้องการหรือเมื่อสำรวจครบทุกโหนด สำหรับโหนดข้างเคียงในที่นี้หมายถึงโหนดที่มีเส้นเชื่อม เชื่อมกับโหนดที่กำลังสำรวจหรือกล่าวอีกนัยหนึ่ง คือ โหนดที่อยู่ติดกันและมีทางเดินเชื่อมหากัน

การค้นหาแบบฮิวริสติก

ความแตกต่างระหว่างการค้นหาข้อมูลธรรมดา และ การค้นหาข้อมูลแบบฮิวริสติก(Heuristic Search) การค้นหาแบธรรมดาจะเป็นการตรวจสอบข้อมูลจนครบ ถ้าข้อมูลไม่ใหญ่มาก การค้นหาแบบนี้จะให้คำตอบที่ถูกต้องเสมอ แต่ในบางครั้งข้อมูลมีขนาดใหญ่มาก การตรวจสอบต้องทำหลายล้านครั้ง ซึ่งทำให้การเปรียบเทียบข้อมูลทุกตัวเพื่อหาคำตอบที่เป็นไปไม่ได้ ลักษณะของปัยหาแบบนี้ เช่น การหาทางที่สั้นที่สุดเราจะต้องเปรียบเทียบเส้นทาง 99! ครั้ง หรือ (n-1)! เมื่อ n คือจำนวนเมืองซึ่งต้องการเปรียบเทียบจำนวนที่ไม่อาจเปรียบเทียบให้เสร็จได้ ดังนั้นจะตอบคำถามว่าเส้นที่สั้นที่สุดคือเส้นทางใด จะยากมากและอาจหาไม่ได้เลยก็ได้ ดังนั้นการแก้ปัญหาต้องอาศัยวิธีการฮิวริสติก วิธีการนี้เลือกคำตอบที่เหมาะสมให้กับการค้นหาเท่านั้น แต่ไม่ได้คำตอบที่ดีที่สุด
เครื่องมือช่วยค้นหาฮิวริสติก คือ ฮิวริสติกฟังชัน
Heuristic Functionทำหน้าที่วัดขนาดความเป็นไปได้ในการแก้ปัญหา เพื่อกำหนดทิศทางของการค้นหาคำตอบ หรือกล่าวอีกนัยหนึ่งคือ ฮิวริสติกฟังชันจะเป็นการบอกว่าสำรวจครั้งต่อไปจะเลือกสำรวจโหนดที่กิ่งใด โดยบอกขนาดของความเป็นไปได้ และขนาดความเป็นไปได้แสดงเป้นตัวเลข
การวัดความเป็นไปได้ในการแก้ปัญหา จะกระทำได้โดยพิจารณษถึงวิธีการ(Aspects)ต่างๆ ที่ใช้ในการแก้ปัญหา ณ สถานะหนึ่งว่า จะสามารถแก้ปัญหาได้ตามที่ต้องการหรือไม่ โดยกำหนดน้ำหนักที่ให้กับการแก้ปัญหาของแต่ละวิธี น้ำหนักเหล่านี้จะถูกแสดงด้วยตัวเลขที่กำกับไว้โหนดต่างๆ ในกระบวนการค้นหา และค่าเหล่านี้จะเป็นตัวที่ใช้ในการประมาณความเป็นไปได้ว่าเส้นทางผ่านโหนดนั้น มีความเป็นไปได้นำสู่หนทางการแก้ปัญหาได้มากน้อยแค่ไหน

การค้นหาBest-first search

การค้นหาแบบเลือกโหนดที่ดีที่สุด (most promising) การทราบว่าโหนดใดดีที่สุดนี้สามารถทำได้โดยอาศัยฮิวริสติกฟังชั่น ฮิวริสติก ฟังชันนี้ทำหน้าที่เหมือนตัววัดผล

กรีดีอัลกอริทึมGreedy Algorithm

เลือกโหนดที่ดีที่สุดก่อน อาศัยการวัดสถานะไปยังเป้าหมาย ดังนั้นการเลือกโหนดต้องเลือกโหนดที่มีค่าh ดีที่สุด

การค้นหาด้วยอัลกอริทึมA*

เลือกโหนดที่ใช้ดำเนินการต่อที่ดีที่สุด วิธีการเลือกโหนดที่ใช้ในการดำเนินการต่อ พิจารณาจากโหนดที่ดีที่สุด ความแตกต่างระหว่างA* กับฮิวริกฟังชั่น ฮิวริกฟังชั่น จะวัดจากโหนดราก(เริ่ม) โหนดปัจจุบัน(สถานะปัจจุบัน) แต่ค่าฮิวริสติก ฟังก์ชั่นA*จะเกิดการรวมค่า2ค่า คือ ค่าวัดจากสถานะปัจจุบันไปยังสถานะเริ่มต้น รวมค่าที่วัดจากสถานะปัจจุบัยนไปยังสถานะเป้าหมายถ้ากำหนดให้ตัวแปร fแทนค่าของฮิวริสติก ฟังชันของA* และg เป็นฟังชันที่ใช้วัดค่า(cost)จากสถานะเริ่มต้นจนถึงสถานะปัจจุบัน h' เป็นฟังชั่นที่ใช้วัดค่าจากสถานะปัจจุบันถึงสถานะเป้าหมาย

การค้นหาข้อมูลแบบ A*ของปัญหา 8-Puzzle ในการคำนวณค่าของ g คือการเปรียบเทียบสถานะปัจจุบัน กับสถานะเริ่มต้น และค่า h' คือการเปรียบเทียบสถานะปัจจุบันกับสถานะเป้าหมาย ซึ่งในการคำนวณค่าgและh'

สถานะเริ่มต้น

สถานะเป้าหมาย

การหาค่าของ g ทำได้โดยเปรียบเทียบสถานะปัจจุบันกับสถานะเริ่มต้น คือการนับว่าแต่ละช่องของตารางปัจจุบันห่างจากจุดเริ่มต้นไปกี่ช่อง เช่นที่ช่อง1ตารางทั้งสองไม่ห่างกัน ดังนั้นได้ค่า0 ที่ช่อง1ที่ช่อง2 สถานะปัจจุบันไม่มีค่าไม่คิด และเช่นกันที่ช่องที่3และ4ก็มีค่าเป็น0 เพราะทั้งสองตารางไม่ต่างกัน สำหรับตารางที่5 จะมีค่าเป็น1เพราะ8ห่างจากที่เคยอยู่ 1 ช่อง ทำเช่นนี้เรื่อยๆเราจะได้คำตอบช่องตารางต่างๆ ดังนี้
1=0,2=0,3=0,4=0,5=1,6=0,7=0,8=1,9=0รวม g=2

สำหรับค่าของ h'จะได้
1=1,2=0,3=0,4=1,5=1,6=0,7=0,8=1,9=0รวมh'=3 f=2+3=5

ข้อสังเกต

1.เกี่ยวกับตัวอัลกอริทึม

คำนึงถึงเส้นทางที่ดีที่สุดด้วย
ทำอย่างไรให้ได้คำตอบนั้น กำหนดให้ g=0
ถ้าต้องการให้ได้เส้นทางที่มีขั้นตอนน้อยที่สุด เราสามารถกำหนดให้ ค่าของโหนดไปยังโหนดลูกมีค่าคงที่(เท่ากับ 1)

2.เกี่ยวกับค่า h'และ h (ค่าจากโหนดถึงโหนดลูก)

ถ้า h'เป็น perfect estimator ของh, A* algorithm กลายเป็นการเข้าหาเป้าหมายโดยไม่มีการค้นหา
เมื่อ h'= ค่าที่ดีที่สุด ก็คือการหากำหนดระยะทางที่ใกล้ที่สุด
เมื่อh'=0 การค้นหาจะถูกควบคุมโดยg
ถ้าg=0อีก การค้นหาจะเป็นแบบ random
ถ้าgเป็น1การค้นหาจะเป็น breadth-first