hill-Climbing search


หลักการ

1. สุ่มเลือกคำตอบจากสเปซคำตอบ 1 state
2. search ดู state (คำตอบ) ที่อยู่ติดกัน ถ้าหากให้ผลตอบแทนที่ดีกว่า ก็ยึดคำตอบใหม่ ทิ้งคำตอบเก่า ถ้าคำตอบเก่าให้ผลดีกว่า ก็คงคำตอบเก่าเอาไว้ แล้วทำข้อ 2 ซ้ำ จนกว่าจะบรรลุผล

ให้สังเกตจุดที่อาจไม่บรรลุผลจากรูปคือ shoulder, local maximum (Ridges) และ flat local maximum (Plateaux)

ตัวอย่าง ปัญหา 8 Queens


ตัวเลขแสดงจำนวนคู่ของควีนที่โจมตีกันและกัน คำตอบปัจจุบัน h(n) = 17 คำตอบถัดไปที่ควรสำรวจคือเคลื่อนควีนไปยังช่องที่มีค่าคู่การโจมตีต่ำสุดคือ 12 (เคลื่อนตัวใดดี ? นิยมใช้วิธีการสุ่ม)

ตัวอย่าง กรณี local minimum


ค่า h(n) ปัจจุบันเท่ากับ 1 ส่วน h(n) ของคำตอบที่อยู่ติดกันไม่มีตัวใดน้อยกว่า 1

ถ้าความน่าจะเป็นในการทำงานล้มเหลวจากวิธีการนี้เท่ากับ PF หากเราลองซ้ำแล้วซ้ำอีก k ครั้ง ความน่าจะเป็นที่ล้มเหลวทุกครั้งเท่ากับ PFk นั่นคือความน่าจะเป็นที่จะสำเร็จเท่ากับ PS = 1-PFk เมื่อ k มีค่ามากขึ้น โอกาสสำเร็จย่อมมากขึ้น เรียก Random-restart hill-climbing









Create Date : 20 ธันวาคม 2550
Last Update : 20 ธันวาคม 2550 13:45:09 น.
Counter : 2208 Pageviews.

0 comments
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

ศล
Location :
กรุงเทพ  Thailand

[ดู Profile ทั้งหมด]
 ผู้ติดตามบล็อก : 85 คน [?]

บทความทั้งหมด