การค้นหาข้อมูล (searching)
การค้นหาคําตอบ หรือการค้นหาข้อมูลในทางคอมพิวเตอร์มักจะกระทําบนโครงสร้างข้อมูลแบบต้นไม้ และกราฟ ทั้งนี้เพราะโครงสร้างข้อมูลในลักษณะนี้สามารถทําให้การค้นหาทําได้สะดวกและสามารถพลิกแพลงการค้นหาได้ง่าย ในความเป็นจริงแล้ว การค้นหาข้อมูลบางครั้งสามารถกระทําบนโครงสร้างข้อมูลชนิดอื่นก็ได้เช่น อาเรย์ แสตก และคิว แต่การจัดข้อมูลในโครงสร้างเช่นนี้ มีข้อจํากัดในการค้นหาข้อมูลมาก การค้นหาทําได้แบบเรียงลําดับ(Sequencial Search) เท่านั้น ซึ่งใช้ได้กับข้อมูลที่มีขนาดเล็ก ดังนั้นในการค้นหาข้อมูลที่มีขนาดใหญ่ ก่อนการค้นหา หรือระหว่างการค้นหา ข้อมูลที่จะถูกค้นจะต้องถูกจัดให้อยู่ในรูปแบบของต้นไม้ หรือกราฟเท่านั้น การค้นหาข้อมูลบนโครงสร้างต้นไม้และกราฟสามารถจํ าแนกได้ 2 แบบคือ การค้นหาแบบไบล์ด(Blind Search) และการค้นหาแบบฮิวริสติก(Heuristic Search)
การค้นหาแบบไบล์ด(Blind Search)
การค้นหาแบบไบล์ด(Blind search) เป็นการค้นหาแบบที่เดินทางจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง โดยอาศัยทิศทางเป็นตัวกําหนดการค้นหา ไม่ต้องมีข้อมูลอะไรมาช่วยเสริมการตัดสินใจว่าจะเดินทางต่อไปอย่างไร หรือกล่าวอย่างง่าย ๆ คือการจะหยิบข้อมูลใดมาช่วยในการค้นหาต่อไป ไม่ต้องอาศัยข้อมูลใด ๆ ทั้งสิ้น นอกจากทิศทางซึ่งเป็นรูปแบบตายตัว การค้นหาแบบไบล์ดสามารถแบ่งย่อยได้ดังนี้ คือ การค้นหาทั้หมด และการค้นหาบางส่วน
- การค้นหาทั้งหมด(exhaustive search) คือ การค้นหาทั้งหมดของปริภูมิสถานะ
- การค้นหาบางส่วน (partial search) การค้นหาเพียงบางส่วนของปริภูมิสถานะ ซึ่งในความเป็นจริงการค้นหาส่วนมากใช้การค้นหาเฉพาะบางส่วนเท่านั้นเนื่องจากปริภูมิสถานะมักมีขนาดใหญ่ เท่าให้ไม่สามารถค้นหาได้ทั้งหมด ดังนั้นจึงมีความเป็นไปได้ว่าคำตอบที่ได้อาจไม่ใช่คำตอบที่ดีที่สุด การค้นหาแบบนี้สามารถแบ่งได้เป็น 2 ประเภทคือ การค้นหาแบบลึกก่อน(Depth first search) และการค้นหาแบบกว้างก่อน (Breadth first search)
การค้นหาแบบลึกก่อนเป็นการค้นหาที่กําหนดทิศทางจากรูปของโครงสร้างต้นไม้ ที่เริ่มต้นจากโหนดราก(Root node) ที่อยู่บนสุด แล้วเดินลงมาให้ลึกที่สุด เมื่อถึงโหนดล่างสุด(Terminal node) ให้ย้อนขึ้นมาที่จุดสูงสุดของกิ่งเดี่ยวกันที่มีกิ่งแยกและยังไม่ได้เดินผ่าน แล้วเริ่มเดินลงจนถึงโหนดลึกสุดอีก ทําเช่นนี้สลับไปเรื่อยจนพบโหนดที่ต้องการหาหรือสํารวจครบทุกโหนดแล้วตามรูปที่ 1 การค้นหาแบบลึกก่อนจะมีลําดับการเดินตามโหนดดังตัวเลขที่กํากับไว้ในแต่ละโหนด
รูปที่ 1 ลําดับการเดินทางบนโหนดของการค้นหาแบบลึกก่อนบนโครงสร้างต้นไม้
ดังที่ได้กล่าวมาแล้วว่า โครงสร้างข้อมูลที่ใช้สําหรับการค้นหานี้สามารถใช้กับโครงสร้างกราฟได้ด้วย โดยอาศัยหลักการเดียวกัน แต่สําหรับการเดินทางบนกราฟนั้นจะไม่มีโหนดลึกสุดดังนั้นการเดินทางบนกราฟจะต้องปรับวิธีการเป็นดังนี้ โดยเริ่มจาก
โหนดเริ่มต้น จากนั้นให้นําโหนดที่อยู่ติดกับโหนดที่กําลังสํารวจอยู่(ที่ยังไม่ได้ทําการสํารวจและยังไม่ได้อยู่ในแสต็กมาใส่แสต็ก) มาเก็บไว้ในสแต็กเมื่อสํารวจโหนดนั้นเสร็จ ให้พอพ(pop) ตัวบนสุดของโหนดออกมาทําการสํารวจ แล้วนําโหนดข้างเคียงทั้งหมดที่ยังไม่ได้สํารวจมาต่อท้ายแสต็ก แล้วพอพตัวบนสุดออกมาสํารวจ ทําเช่นนี้เรื่อย ๆ จนกระทั้งพบโหนดที่ต้องการ หรือสํารวจครบทุดโหนด
รูปที่ 2 โครงสร้างข้อมูลแบบกราฟ
การสํารวจจะเริ่มต้นที่ A และนําโหนดข้างเคียง B และ C มาเก็บไว้ในแสต็ก เมื่อสํารวจ Aเสร็จพอพข้อมูลจากแสต็กออกมาได้ C ทําการสํารวจ C และนําโหนดข้างเคียงกับ C ที่ยังไม่ได้ทําการสํารวจและยังไม่ได้อยู่ในแสต็กมาใส่แสต็ก D และ F
พุช(Push) ใส่แสต็ก ดังนั้นในแสต็กตอนนี้มี B D F อยู่ เมื่อสํารวจ C เสร็จ พอพ F ออกมาทําการสํารวจ แล้วนําโหนดข้างเคียงที่ยังไม่ได้สํารวจและยังไม่ได้อยู่ในแสต็กมาใส่แสต็ก ซึ่งก็คือ G ดังนั้นข้อมูลในแสต็กจะเป็น B D G ทํ าเช่นนี้ไปเรื่อย ๆ จนจบการทํางานก็จะได้ลําดับการสํ ารวจคือ (A C F G H E D B) ตามตาราง 1 ดังต่อไปนี้
ตารางที่ 1 ลําดับการค้นหาแบบลึกก่อน
ในการค้นหาข้อมูลแบบนี้บนโครงสร้างของกราฟ มีข้อที่น่าสังเกตุคือ โหนดที่เริ่มต้นการสํารวจจะต้องมีการกําหนดมาให้ว่าโหนดใดเป็นโหนดเริ่มต้น และข้อสังเกตุอีกประการหนึ่งคือวิธีการค้นหาแบบลึกก่อนที่ใช้สําหรับโครงสร้างข้อมูลแบบกราฟ สามารถใช้กับโครงสร้างข้อมูลแบบต้นไม้ได้ด้วย
การค้นหาแบบกว้างก่อนเป็นการกําหนดทิศทางการค้นหาแบบที่ละระดับของโครงสร้างต้นไม้โดยเริ่มจากโหนดราก(ระดับที่ 0) แล้วลงมาระดับที่ 1 จากซ้ายไปขวา เมื่อเสร็จระดับที่ 1 ไประดับที่ 2จากซ้ายไปขวาเช่นกัน ทําเช่นนี้เรื่อย ๆ จนพบโหนดที่ต้องการตามรูปที่ 3 ลําดับการเดินทางของโหนดเป็นไปตามหมายเลขที่กํากับไว้บนโหนด
รูปที่ 3 ลําดับการค้นหาแบบกว้างก่อนบนโครงสร้างต้นไม้
สําหรับการค้นหาแบบกว้างก่อนบนโครงสร้างต้นไม้ จะอาศัยโครงสร้างข้อมูลแบบคิว(Queue)มาช่วย และด้วยวิธีการเช่นเดียวกับการค้นหาแบบลึกก่อนคือ ให้เริ่มต้นสํารวจที่โหนดเริ่มต้น แล้วนําโหนดข้างเคียงเก็บไว้ในคิว เมื่อสํารวจโหนดเริ่มต้นเสร็จ ให้นําข้อมูลในคิวออกมาสํารวจ แล้วนําโหนดข้างเคียงที่ยังไม่ได้สํารวจและไม่ได้อยู่ในคิวใส่คิวไว้ ทําเช่นนี้ไปเรื่อย ๆ จนพบโหนดที่ต้องการ หรือเมื่อสํารวจครบทุกโหนด
รูปที่ 4 โครงสร้างข้อมูลแบบกราฟ
การสํารวจเริ่มต้นที่ A นําโหนดข้างเคียง B C ไว้ในคิว เมื่อสํารวจ A เสร็จ นําข้อมูลในคิว คือ Bออกมาสํารวจ แล้วนําข้อมูลข้างเคียงคือ D E ใส่คิว ตอนนี้คิวจะมี B D E อยู่ แล้วนํา B ออกมาสํารวจทําเช่นนี้เรื่อย ๆ จะได้ลําดับการสํารวจข้อมูลคือ (A B C D E F G H) ตามตารางที่ 2
ตาราง 2 ลําดับการค้นหาแบบกว้างก่อน
เช่นเดียวกับการค้นหาแบบลึกก่อน การค้นหาแบบกว้างก่อนโดยใช้โครงสร้างข้อมูลคิวมาช่วยต้องมีการกําหนดโหนดเริ่มต้น และวิธีการนี้สามารถใช้ได้กับข้อมูลบนโครงสร้างแบบต้นไม้ด้วย
ตารางเปรียบเทียบ การค้นหาแนวลึกก่อนและแนวกว้างก่อน
การค้นหาแนวลึกก่อน | การค้นหาแนวกว้างก่อน |
1.ใช้หน่วยความจำน้อยกว่า เพราะว่าสถานะในเส้นทางค้นหาปัจจุบันเท่านั้นที่ถูกเก็บ(ในขณะใดๆ จะเก็บเส้นทางเดียว พอจะไปเส้นทางอื่นเส้นทางที่ผ่านมาก็ไม่จำเป็นต้องเก็บ) | 1.ใช้หน่วยความจำมาก เพราะต้องเก็บสถานะไว้ทุกตัวเพื่อหาเส้นทางจากสถานะเริ่มต้นไปหาคำตอบ |
2. อาจจะติดเส้นทางที่ลึกมากโดยไม่พบคำตอบ เช่นในกรณีที่เส้นทางนั้นไม่มีคำตอบและเป็นเส้นทางที่ยาวไม่สิ้นสุด จะทำไม่สามารถไปเส้นทางอื่นได้ | 2. จำไม่ติดเส้นทางที่ลึกมาก ๆ โดยไม่พบคำตอบ |
3. ถ้าคำตอบอยู่ในระดับ n+1 สถานะอื่นทุกตัวที่ระดับ 1ถึงระดับ n ไม่จำเป็นต้องถูกกระจายจนหมด | 3. ถ้าคำตอบอยู่ในระดับ n+1 สถานะทุกตัวที่ระดับ 1ถึงระดับ n จะต้องถูกกระจายจนหมด ทำให้มีสถานะที่ไม่จำเป็นในเส้นทางที่จะไปสู่คำตอบถูกกระจายออกด้วย |
4. เมื่อพบคำตอบไม่สามารถรับประกันได้ว่าเส้นที่ได้เป็นเส้นทางที่สั้นที่สุดหรือไม่ | 4. ถ้ามีคำตอบจะรับประกันได้ว่าจะพบคำตอบแน่ ๆ และจะได้เส้นทางสั้นที่สุดด้วย |
การค้นหาแบบฮิวริสติก(Heuristic Search)
การค้นหาคําตอบอาศัยวิธีการทางฮิวริสติก (heuristic search) มีความความแตกต่างจากการค้นหาข้อมูลแบบธรรมดาและแบบฮิวริสติกนั้นอยู่ที่การค้นหาข้อมูลธรรมดา ผู้ที่ทําการค้นข้อมูลจะต้องตรวจสอบข้อมูลทีละตัวทุกตัวจนครบ แต่ฮิวริสติกจะไม่ลงไปดู ข้อมูลทุกตัว วิธีการนี้จะเลือกได้คําตอบที่เหมาะสมให้กับการค้นหา ซึ่งมีข้อดีคือ สามารถทําการ ค้นหาคําตอบจาก ข้อมูลที่มีขนาดใหญ่มาก ๆ ได้ แต่มีข้อเสียคือคําตอบที่ได้เป็นเพียงคําตอบที่ดี เท่านั้นไม่แน่ว่าจะดีที่สุด แต่เนื่องจากว่าปัญหาในบางลักษณะนั้นใหญ่มาก และเป็นไปไม่ได้ที่จะทํา การค้นหาด้วยวิธี ธรรมดากระบวนการของฮิวริสติกจึงเป็นสิ่งที่จําเป็นในเรื่องของฮิวริสติกนั้น นอกจากจะมีการค้นหาแบบฮิวริสติกแล้ว ยังมีอีกสิ่งหนึ่งที่สําคัญคือ ฮิวริสติกฟังก์ชัน (heuristic function) ซึ่งหมายถึงฟังก์ชันที่ทําหน้าที่ในการวัดขนาดของความเป็น ไปได้ในการแก้ปัญหาซึ่งจะแสดงด้วยตัวเลข วิธีการดังกล่าวจะกระทํ าได้โดยการพิจารณาถึงวิธีการ (aspects) ต่าง ๆ ที่ใช้ในการแก้ปัญหา ณ สถานะหนึ่งว่าจะสามารถแก้ปัญหาได้ตามที่ต้องการหรือไม่ โดยกําหนดเป็นนํ้าหนักที่ให้กับการแก้ปัญหาของแต่ละวิธี นํ้าหนักเหล่านี้จะถูกแสดงด้วยตัวเลขที่กํากับไว้กับโหนดต่าง ๆ ในกระบวนการ ค้นหา และค่าเหล่านี้จะเป็นตัวที่ใช้ในการประมาณความเป็นไปได้ว่าเส้นทางที่ผ่านโหนดนั้นจะมี ความเป็นไปได้ในการนําไปสู่หนทางการแก้ปัญหาได้มากน้อยแค่ไหนจุดประสงค์ที่แท้จริงของฮิวริสติก ฟังก์ชันก็คือ การกํากับทิศทางของกระบวนการค้นหา เพื่อให้อยู่ในทิศทางที่ได้ประโยชน์สูงสุด โดยการบอกว่าเราควรเลือกเดินเส้นทางไหนก่อน ในกรณีที่มีเส้น ทางมากกว่าหนึ่งเส้นทางต้องเลือกกระบวนการค้นหาแบบฮิวริสติก โดยปกติแล้วจะต้องอาศัยฮิวริสติกฟังก์ชัน ทําให้การแก้ปัญหาหนึ่ง ๆ จะดีหรือไม่ ก็ขึ้นอยู่กับฮิวริสติกฟังก์ชันดังนั้นการค้นหาแบบนี้จึงไม่มีอะไรเป็นหลักประกันว่าจะได้สิ่งที่ไม่ดีออกมาด้วยเหตุนี้เอง เราจึงเรียกการ ค้นหาแบบฮิวริสติกนี้ว่า Weak Methods หรือจะกล่าวอีกนัยหนึ่งคือ Weak Methods เป็นกระบวนการควบคุมโดยทั่วไป (general-purpose control stategies) ซึ่งการค้นหาแบบนี้ สามารถแบ่งได้เป็น
ฟังก์ชันฮิวริสติกสามารถนำมาช่วยในกระบวนการค้นหาเพื่อให้ได้คำตอบอย่างรวดเร็วและมีประสิทธิภาพ วิธีการที่จะนำฟังก์ชันฮิวริสติกมาใช้มีหลายวิธีด้วยกันขึ้นอยู่กับว่าจะใช้ในลักษณะใด เช่นเลือกสถานะที่มีค่าฮิวริสติกดีขึ้น แล้วเดินไปยังสถานะนั้นเลยโดยไม่ต้องสนใจสถานะที่มีค่าฮิวริสติกแย่กว่าสถานะปัจจุบันหรือว่าจะเก็บสถานะทุกตัวไว้แม้ว่าค่าฮิวริสติกจะแย่ลงแล้วพิจารณาสถานะเหล่านี้ทีหลัง เป็นต้น ในส่วนต่อไปนี้จะกล่าวถึงอัลกอริทึมต่าง ๆ ที่นำฟังก์ชันฮิวริสติกมาช่วยในการค้นหาคำตอบ โดยเริ่มจากอัลกอริทึมปีนเข้า (Hill climbing algorithm)
รูปที่ 5 แสดงลักษณะการค้นหาแบบ Hill climbing
การค้นหาแบบฮิลไคลบิง(Hill climbing) เป็นวิธีการค้นหาข้อมูลที่มีลักษณะคล้ายกับการปีนภูเขา การที่นักปีนภูเขาจะเดินทางไปถึงยอดภูเขา นักปีนเขาจะต้องมองก่อนว่ายอดเขาอยู่ที่ใด แล้วนักปีนเขาจะต้องพยายามไปจุดนั้นให้ได้ ลองนึกภาพของการปีนภูเขาโล้นที่มองเห็นแต่ยอด และนักปีเขากําลังปีนภูเขาอยู่เบื้องล่างที่มีเส้นทางเต็มไปหมด เพื่อที่จะเดินทางไปถึงยอดภูเขาโดยเร็วที่สุด นักปีน
เขาจะมองไปที่ยอดเขาแล้วสังเกตว่าทิศทางใดที่เมื่อปีนแล้วจะยิ่งใกล้ยอดเขา และหลีกเลี่ยงทิศทางที่เมื่อไปแล้วจะทําให้ตัวเองห่างจากยอดเขา นักปีนเขาจะต้องทําเช่นนี้ไปเรื่อย ๆ จนกระทั่งถึงยอดเขา
ตัวอย่างการใช้ฟังก์ชันฮิวริสติก โดยอัลกอริทึมปีนเขาอย่างง่ายโดยปัญหาโลกของ
บล๊อก
รูปที่ 6 การค้นหาแบบ Hill climbing
ตัวเลข h(i) ในรูปแสดงว่า สถานะที่ i มีค่าฮิวริสติกเท่ากับ h จากรู้จะเห็นได้ว่า เริ่มต้นจากสถานะที่ 1 ที่มีค่าฮิวริสติกเท่ากับ -1 อัลกอริทึมปีนเขาใช้ตัวกระทำการเพื่อสร้างสถานะลูกตัวแรกของสถานะที่ 1 แล้ววัดค่าฮิวริสติกได้ 0 ซึ่งมีค่าดีขึ้น ถ้าสังเกตจากรูปที่ จะพบว่าสถานะที่ 1 มีสถานะลูกทั้งหมด 3 ตัว แต่ในกรณีของอัลกอริทึมปีนเขานี้ เมื่อได้สถานะลูกตัวแรกซึ่งมีค่าอิวริสติกดีขึ้น อัลกอริทึมจะไม่สร้างสถานะลูกที่เหลืออีก 2 ตัว และจะไม่มีการย้อนกลับมาที่สถานะลูกทั้ง 2 นี้ แม้ว่าหลังจากนี้อัลกอริทึมจะค้นไม่พบคำตอบกล่าวคือเป็นการตัดทางเลือกทิ้งไปเลย ซึ่งการทำเช่นนี้แม้ว่าจะมีโอกาสไม่พบคำตอบแต่ก็มีข้อดีที่เป็นการช่วยลดเวลาและปริภูมิที่ทำการค้นหาจะลดลงอย่างมากจากนั้นอัลกอริทึมมาสถานะที่ 2 แล้วเริ่มสร้างสถานะลูกได้สถานะที่ 3 ที่มีค่าฮิวริสติก -1 ซึ่งแย่ลงในกรณีที่แย่ลงเช่นนี้ อัลกอริทึมจะไม่ไปยังสถานะลูกตัวนี้และสร้างสถานะลูกตัวต่อไปโดยใช้ตัวกระทำการที่เหลือได้สถานะที่ 4 มีค่าฮิวริสติกเท่ากับ -1 ไม่ดีขึ้นเช่นกันจึงสร้างสถานะลูกตัวถัดไป เป็นสถานะที่5 มีค่าฮิวริสติกเท่ากับ 1 เป็นค่าที่ดีขึ้น อัลกอริทึมจะมายังสถานะนี้และค้นพบคำตอบในที่สุด
อัลกอริทึมปีนเขานี้จะมีประสิทธิภาพมากดังเช่นแสดงในตัวอย่างนี้ซึ่งกระจายสถานะทั้งสิ้นเพียง 6 ตัวแล้วพบคำตอบ เปรียบเทียบกับอัลกอริทึมการค้นหาแนวกว้างก่อนซึ่งใช้สถานะทั้งสิ้นถึง 11 ตัว อย่างไรก็ดีอัลกอริทึมนี้จะมีประสิทธิภาพมาก ถ้าใช้ฟังก์ชันฮิวริสติกที่ดีมาก ๆ ในกรณีที่ฟังก์ชันฮิวริสติกไม่ดีนัก อัลกอริทึมนี้ก็อาจหลงเส้นทางได้ และอาจไม่พบคำตอบแม้ว่าปริภูมิที่กำลังค้นหามีคำตอบอยู่ด้วยก็ตาม สาเหตุการหลงเส้นทางประการหนึ่งมาจากการเลือกสถานะลูก ซึ่งอัลกอริทึมจะไม่ได้พิจารณาสถานะลูกทุกตัวโดยเมื่อพบสถานะลูกตัวใดตัวหนึ่งที่ดีขึ้นก็จะเลือกเส้นทางนั้นทันที อัลกอริทึมนี้สามารถดัดแปลงเล็กน้อยให้พิจารณาสถานะลูกทุกตัวให้ครบก่อน แล้วเลือกสถานะลูกตัวที่มีค่าฮิวริสติกสูงสุด เมื่อทำเช่นนี้ก็จะทำให้อัลกอริทึมได้พิจารณาเส้นทางที่ดีที่สุด ณ ขณะหนึ่ง ๆ ได้ดีขึ้นเราเรียกอัลกอริทึมที่ดัดแปลงนี้ว่าอัลกอริทึมปีนเขาชันสุด (Steepest ascent hill climbing)
เป็นกระบวนการค้นหาข้อมูลที่ได้นําเอาข้อดีของทั้งการค้นหาแบบลึกก่อน(Depth firstsearch) และการค้นหาแบบกว้างก่อน(Breadth first search) มารวมกันเป็นวิธีการเดียว โดยที่แต่ละขั้นของการค้นหาในโหนดลูกนั้น การค้นหาแบบดีที่ดีก่อนจะเลือกเอา โหนดที่ดีที่สุด (most promising)และการที่จะทราบว่าโหนดใดดีที่สุดนี้สามารถทําได้โดยอาศัยฮิวริสติกฟังก์ชัน ซึ่งฮิวริสติก ฟังก์ชันนี้จะทําหน้าที่เหมือนตัววัดผล และให้ผลของการวัดนี้ออกมาเป็นคะแนน รูปที่ 2.7 เป็นตัวอย่างของการค้นหาแบบดีที่สุดก่อน ขั้นตอนนี้เริ่มจากตอน 1 สร้างโหนดราก(root node) ในขั้นตอน 2 สร้างโหนดลูกB และ C แล้วตรวจสอบโหนด B และ C ด้วยฮิวริสติกฟังก์ชัน ได้ผลออกมาเป็นคะแนนคือ 3 และ 1ตามลํ าดับ จากนั้นให้เลือกโหนด C เป็นโหนดต่อไปที่เราสนใจ เพราะมีค่าน้อยกว่า (หมายเหตุ ในการเลือกนี้จะเลือกค่ามากสุด หรือน้อยสุดก็ได้ ขึ้นอยู่กับลักษณะของปัญหา) แล้วสร้างโหนด ลูกให้กับโหนด C ในขั้นตอน 3 ได้โหนด D และ E แล้วตรวจสอบคะแนนได้ 4 และ 6 ตามลํ าดับ จากนั้นทํ าการเปรียบเทียบค่าของโหนดท้ายสุด หรือเทอร์มินอล โหนด(terminal node) ทุกโหนด ว่าโหนด ใดมีค่าดีที่สุด ในที่นี้จะต้องเลือกโหนด B เพราะมีคะแนนเพียง 3 (เลือกคะแนนตํ่าสุด) แล้วสร้างโหนด ลูกตามขั้นตอน 4 ได้ F และ G แล้วตรวจ สอบคะแนนได้ 6 และ 5 คะแนนตามลํ าดับ ทําเช่นนี้เรื่อย ๆ จนพบคําตอบหรือจนไม่สามารถ สร้างโหนดต่อไปได้อีก
รูปที่ 7 ขั้นตอนของการค้นหาแบบดีที่สุดก่อน
รูปที่ 8 การค้นหาแบบดีสุดก่อน
อัลกอริธึม: การค้นหาแบบดีที่สุดก่อน
1. เริ่มด้วย OPEN ที่มีเพียงโหนดเริ่มต้น
2. ทําจนกว่าจะพบเป้าหมาย หรือว่าไม่มีโหนดเหลืออยู่ใน OPEN
� เลือกโหนดที่ดีที่สุดใน OPEN
� สร้างโหนดลูกให้กับโหนดที่ดีที่สุดนั้น
� สําหรับโหนดลูกแต่ละตัวให้ทําดังต่อไปนี้
i) ถ้าโหนดนั้นยังไม่เคยถูกสร้างมาก่อนหน้านั้น ให้ตรวจสอบค่าของมันโดย
ใช้ฮิวริสติกฟังชัน แล้วเพิ่มเข้าไปใน OPEN แล้วบันทึกว่าเป็นโหนดแม่
ii) ถ้าโหนดนั้นถูกสร้างมาก่อนหน้านี้แล้ว ให้เปลี่ยนโหนดแม่ของมัน ถ้าเส้น
ทางใหม่ที่ได้ดีกว่าโหนดแม่ตัวเดิม ในกรณีนี้ ให้ปรับเปลี่ยนค่าตามเส้น
ทางที่อาจจะเกิดขึ้น
กรีดีอัลกอริธึม เป็นการค้นหาแบบดีที่สุดก่อน(Best first search) ที่ง่ายที่สุด หลักการของการค้นหาแบบนี้คือ การเลือกโหนดที่ดีที่สุดตลอดเวลาอัลกอริธึม กรีดี
1. เลือกโหนดเริ่มต้นมาหนึ่งโหนด
2. ให้โหนดที่เลือกมานี้เป็นสถานะปัจจุบัน
3. ให้ทําตามขบวนการข้างล่างนี้จนกว่าจะไม่สามารถสร้างโหนดลูกได้อีก
3.1 สร้างสถานะใหม่ที่เป็นโหนดลูกที่เป็นไปได้ทั้งหมดจากสถานะปัจจุบัน
3.2 จากสถานะใหม่ที่สร้างขึ้นมาทั้งหมด ให้เลือกสถานะ หรือ โหนดลูก ที่ดีที่สุดออกมาเพียงโหนดเดียว
4. กลับไปที่ขึ้นตอนที่ 2
ตัวอย่าง จากเรื่องการเดินทางของเซลแมนที่จะต้องเดินทางไปยังเมือง A B C D ซึ่งมีระยะทางตามตารางที่ 3 เราจะแก้ปัญหานี้ด้วยวิธีการของกรีดีบ้าง
รูปที่ 9 การแก้ปัญหาการเดินทางของเซลแมนด้วยกรีดีอัลกอริธึม
จากรูปที่ 9 การแก้ปัญหาเริ่มจาก การเลือก A เป็นเมืองเริ่มแรก จากนั้นทําการสร้างโหนดลูกB C และ D หารระยะทางระหว่าง A ถึงเมืองเหล่านี้ได้ 20 30 และ 50 ตามลําดับ เลือก B เป็นเมืองที่จะเดินทางต่อมา จากนั้นสร้างโหนดลูกของ B ได้ C และ D และได้ระยะทางเท่ากับ 15 และ 20 ตามลําดับ เลือก C เป็นเมืองที่จะเดินทางต่อไป จากนั้นสร้างโหนดลูกให้ C ได้ D มีค่าเท่ากับ 10 เลือกเดินมาที่ D เป็นเมืองสุดท้ายก่อนกลับไป A รวมระยะทางเท่ากับ 20 + 15 + 10 + 50 = 95
รูปที่ 10 ข้อมูลในรูปแบบกราฟ
ตาราง 3 การค้นหาแบบกรีดี
การค้นหาแบบ A* เป็นอีกแบบของการค้นหาแบบดีที่สุดก่อน วิธีการเลือกโหนดที่จะใช้ในการดําเนินการต่อจะพิจารณาจากโหนดที่ดีที่สุด แต่ในกรณีของ A* นี้จะมีลักษณะพิเศษกว่าคือ ในส่วนของฮิวริสติกฟังก์ชัน ในกรณีของการค้นหาแบบดีที่สุดก่อนนั้น ค่าที่ได้จากฮิวริสติก ฟังก์ชัน จะเป็นค่าที่วัดจาก โหนดปัจจุบัน แต่ในกรณีของ A* ค่าของฮิวริสติก ฟังก์ชัน จะวัดจากค่า 2 ค่าคือ ค่าที่วัดจากโหนดปัจจุบันไปยังโหนดราก และจากโหนดปัจจุบันไปยังโหนดเป้าหมาย ถ้าเราให้ตัวแปร f แทนค่าของฮิวริสติก ฟังก์ชัน g เป็นฟังก์ชันที่ใช้วัดค่า cost จากสถานะเริ่มต้นจนถึงสถานะปัจจุบัน h' เป็นฟังก์ชันที่ใช้วัดค่า cost จากสถานะปัจจุบันถึงสถานะเป้าหมาย ดังนั้น
f = g + h’ |
อัลกอริทึม A* (A* Search) เป็นการขยายอัลกอริทึมดีสุดก่อนโดยพิจารณาเพิ่มเติมถึงต้นทุนจากสถานะเริ่มต้นมายังสถานะปัจจุบันเพื่อใช้คำนวณค่าฮิวริสติกด้วย ในกรณีของอัลกอริทึม A* เราต้องการหาค่าต่ำสุดของฟังก์ชัน f' ของสถานะ s นิยามดังนี้
f'(s)=g(s)+h'(s)
โดยที่ g คือฟังก์ชันที่คำนวณต้นทุนจากสถานะเริ่มต้นมายังสถานะปัจจุบัน h' คือฟังก์ชันที่ประมาณต้นทุนจากสถานะปัจจุบันไปยังคำตอบ ดังนั้น f' จึงเป็นฟังก์ชันที่ประมาณต้นทุนจากสถานะเริ่มต้นไปยังคำตอบ (ยิ่งน้อยยิ่งดี) เรามองได้ว่าฟังก์ชัน h' คือฟังก์ชันฮิวริสติกที่เราเคยใช้ในการค้นหาอื่น ๆ ก่อนหน้านี้เช่นอัลกอริทึมปีนเขา อัลกอริทึมดีสุดก่อน เป็นต้น ในที่นี้เราใส่เครื่องหมาย ' เพื่อแสดงว่าฟังก์ชันนี้เป็นฟังก์ชันประมาณของฟังก์ชันจริงที่ไม่รู้ (เราทำได้แค่ประมาณว่า h' คือต้นทุนจากสถานะปัจจุบันไปยังคำตอบ เราจะรู้ต้นทุนจริงก็ต่อเมื่อเราได้ทำการค้นหาจริงจนไปถึงคำตอบแล้ว) ส่วน g เป็นฟังก์ชันที่คำนวณต้นทุนจริงจากสถานะเริ่มต้นมายังสถานะปัจจุบัน (จึงไม่ได้ใส่เครื่องหมาย ' ) เพราะเราสามารถหาต้นทุนจริงได้เนื่องจากได้ค้นหาจากสถานะเริ่มต้นจนมาถึงสถานะปัจจุบันแล้ว ส่วน f' ก็เป็นเพียงแค่ฟังก์ชันประมาณโดยการรวมต้นทุนทั้งสอง คือ h' กับ g
อัลกอริทึม A* จะทำการค้นหาโดยวิธีเดียวกันกับอัลกอริทึมดีสุดก่อนทุกประการ ยกเว้น ฟังก์ชันฮิวริสติกที่ใช้เปลี่ยนมาเป็น f' (ต่างจากอัลกอริทึมดีสุดก่อนที่ใช้ h') โดยการใช้ f' อัลกอริทึม A* จึงให้ความสำคัญกับสถานะหนึ่ง ๆ 2 ประการ คือ (1) สถานะที่ดีต้องมี h' ดีคือต้นทุนเพื่อจะนำไปสู่คำตอบหลังจากนี้ต้องน้อย และ (2) ต้นทุนที่จ่ายไปแล้วกว่าจะถึงสถานะนี้ (g) ต้องน้อยด้วย เราจึงได้ว่า A* จะค้นหาเส้นทางที่ให้ต้นทุนโดยรวมน้อยที่สุดตามค่า f' ซึ่งต่างจากอัลกอริทึมดีสุดก่อน ที่เน้นความสำคัญของสถานะที่ต้นทุนหลังจากนี้ที่จะนำไปสู่คำตอบต้องน้อย โดยไม่สนใจว่าต้นทุนที่จ่ายไปแล้วกว่าจะนำมาถึงสถานะนี้ต้องเสียไปเท่าไหร่
รูปที่ 11 แสดงการค้นหาด้วยอัลกอริทึม A* กันสถานะในรูปที่ 8 โดยสมมติให้ต้นทุนหรือระยะห่างระหว่างสถานะพ่อแม่ไปยังสถานะลูกเท่ากับ 1 หน่วย เช่นต้น ทุนจริง (g) จาก A ไปยัง B,C หรือ D มีค่าเท่ากับ 1 หน่วย
จากรูปจะเห็นได้ว่าในขั้นตอนที่ 4 สถานะ C จะถูกเลือกมากระจายโดยอัลกอริทึม A* เนื่องจากมีค่า f' น้อยสุดเท่ากับ 3.5 ซึ่งน้อยกว่า E ที่มีค่าเท่ากับ 4 แม้ว่าค่า h' ของ E จะน้อยกว่าซึ่งต่างจากการสร้างสถานะของอัลกอริทึมดีสุดก่อน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น