local search
Keywords (สรุปจาก AIMA p.110-p.111)
• the path to the goal is irrelevant
• applications e.g.
— IC design
— factory-floor layout
— job-shop scheduling
— automatic programming
— telecommunications network optimization
— vehicle routing
— portfolio management
• operate using a single current state & generally move only to neighbors of that state
• use very little memory
• can often find reasonable solutions in large or infinite state space
• are useful for solving pure optimization problems



พิจารณา state space landscape มี 2 ส่วนคือ location (กำหนดโดย state) และ elevation (กำหนดโดย heuristic cost function หรือ objective function) ถ้า elevation ถูกกำหนดโดย cost เป้าหมายของเราคือเลือกจุดต่ำสุด แต่ถ้า elevation ถูกกำหนดโดย objective function เป้าหมายของเราคือเลือกจุดสูงสุด

ตัวอย่าง 4 Queens Problem
เรียง Q 4 ตัวบนกระดาน 4 x 4 เพื่อไม่ให้โจมตีซึ่งกันและกัน


ตัวอย่าง Travelling Salesman Problem
เส้นทางวน loop ที่ cost ต่ำสุด

‣ สลับ 2 edges ของ complete tour








Create Date : 17 ธันวาคม 2550
Last Update : 17 ธันวาคม 2550 11:51:48 น.
Counter : 1173 Pageviews.

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

Zol.BlogGang.com

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

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

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