creatio ex nihilo

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

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 
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 น. 0 comments
Counter : 2172 Pageviews.

ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
  *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.