creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
informed search № 1

f(n) = evaluation function ใช้เป็นข้อมูลช่วยสำหรับกระจาย node
         f(n) ยิ่งน้อย ยิ่งดี
h(n) = heuristic function คือ cost ของเส้นทางที่ถูกที่สุดจาก n ถึง goal

ตัวอย่าง h(n)


• ต้องการจัดรูปจากสถานะ n ให้เป็นรูป goal

h1(n) = จำนวนหมายเลขที่วางผิดตำแหน่ง
h1(n) = 6

h2(n) = ผลรวมของจำนวนครั้งต่ำสุดที่ต้องเลื่อนแต่ละเลข
h2(n) = 3 + 1 + 3 + 0 + 2 + 1 + 0 + 3 = 13

Robot Navigation


• ต้องการเดินจากสีแดงไปยังสีเขียว มีช่องแรเงาคือสิ่งกีดขวาง

h(n) = จำนวนช่องที่ต้องเดินจากช่องที่ n ไปจนถึงสีเขียว แสดงดังรูป



º Greedy Best-First Search

• f(n) = h(n)

เราต้องการเดินทางจาก Arad ไปยัง Bucharest



1. ถ้ากำหนดให้ h(n) = ระยะทางที่สั้นที่สุด (straight-line distance) จากเมือง n ถึงเมือง Bucharest สามารถสรุป h(n) ได้ดังนี้



2. กระจายเฉพาะ node ที่ f(n) ต่ำที่สุด



• การใช้ hSTRAIGHT-LINE DISTANCE เพื่อหา solution กรณีนี้ไม่ Optimal ดูได้จาก costs ที่เกิดขึ้น Arad → Sibiu → Fagaras → Bucharest = 140 + 99 + 211 = 450 ในขณะที่ costs จากเส้นทาง Arad → Sibiu → Rimnicu → Pitesti → Bucharest = 140 + 80 + 97 +101 = 418

• ถ้าเปลี่ยนโจทย์ โดยให้จุดเริ่มต้นอยู่ที่ Isai และมี Fagaras เป็นปลายทาง



hSLD แนะนำ Iasi → Neamt → Iasi → Neamt → ... (loop) ดังนั้นไม่วิธีนี้ไม่รับประกันผลสำเร็จ

• Time/ Space Complexity = O(bm)

º A* Search

• f(n) = g(n) + h(n)
         เมื่อ g(n) = cost รวมจากจุดเริ่มต้นจนถึง n



จากตัวอย่างหาเส้นทาง Arad → Bucharest หลังจากเมือง Sibiu ลำพัง h SLD แนะนำให้เลือก Fagaras เพราะ h(Fagaras) = 176 ซึ่งเป็นค่าต่ำสุด แต่เมื่อนำ g(n) มาคิดร่วม เราเลือก f(Rimnicu) = g(Rimnicu) + h(Rimnicu) = 220+193 = 413 ซึ่งต่ำกว่า f(Fagaras) = g(Fagaras) + h(Fagaras) = 239 + 176 = 415 สุดท้ายได้เส้นทาง Arad → Sibiu → Rimnicu → Pitesti → Bucharest ซึ่งรวม cost = 418 (ถูกที่สุด)



ตัวอย่าง จาก Robot Navigation เราเขียน f(n) = g(n) + h(n) ได้ดังนี้




»•« Admissible Heuristic
กำหนดให้ h*(n) = cost of optimal path จาก n ถึง goal
เราเรียก h(n) ว่า admissible ถ้า 0 ≤ h(n) ≤ h*(n)

• ถ้า h(n) มีคุณสมบัติ admissible แล้ว A* ให้คำตอบเป็น Optimal

พิสูจน์
สมมติมีเป้าหมาย 2 ตัวคือ G กับ G2 โดยที่ G เป็น optimal goal และกำหนดให้ C* คือ cost ของเส้นทางไปสู่ G (หรือ C* = f(G)) เราได้ความสัมพันธ์



‣ f(G2) = g(G2) เพราะ h(G2) = 0
‣ f(G) = g(G) = C* เพราะ h(G) = 0
‣ g(G2) > g(G) เพราะ G เป็น optimal goal
‣ f(G2) > f(G) เพราะ G เป็น optimal goal

ถ้า n เป็น node บน optimal path

‣ h(n) ≤ h*(n) เพราะ h(n) มีลักษณะ admissible
‣ g(n) + h(n) ≤ g(n) + h*(n)
‣ f(n) ≤ C*
‣ f(n) < f(G2) #

ลองพิจารณาตัวอย่างต่อไปนี้



search ด้วย A*



เหตุใด A* จึงไม่ให้คำตอบที่ Optimal ทั้ง ๆ ที่ h(n) มีคุณสมบัติ admissible

»•« Monotonic (Consistent Heuristics)



f(n) เป็น monotonic เมื่อ f(n) ≤ f(n') หรือ h(n) - h(n') ≤ c(n,a,n')

• ถ้า f(n) เป็น monotonic ค่าของ f(n) ตลอดเส้นทางจะไม่ลดลง

f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n)

• เราอาจพิสูจน์ว่า A* ให้คำตอบเป็น optimal เมื่อ h(n) มีลักษณะ admissible และ consistent ได้โดยใช้การพิสูจน์ด้วยข้อขัดแย้ง

‣ f(G) = C*
‣ f(G2) > C*
‣ ถ้า A* ให้ผลลัพธ์คือ G2 เมื่อ n เป็น node บน optimal path สู่ G ดังนั้น f(G2) ≤ f(n)
‣ จากคุณสมบัติ monotone เราได้ C* ≥ f(n)
‣ ดังนั้น C* ≥ f(G2) เกิดข้อขัดแย้ง #


A* Search with a Consistent Heuristic Function



A* กระจาย node โดยเพิ่มค่า f(n) รูปนี้แสดงให้เห็น 3 วง คือ f=380, f=400 และ f=420 โดย nodes ที่อยู่ใน contour มี cost น้อยกว่าหรือเท่ากับ f ของเส้น contour เช่นทุก nodes ที่อยู่ในเส้น f=400 มี f(n) ≤ 400 สำหรับกรณี Uniform-cost Search (A* ที่ใช้ h(n) = 0) เส้น contour จะเป็นวงกลมโดยมีจุดเริ่มต้นคือจุดศูนย์กลาง


คุณสมบัติของ A*
• Completeness ?
‣ แน่นอน ถ้าไม่มี nodes จำนวนอนันต์ที่ f(n) ≤ f(G)

• Optimal Solution ?
‣ แน่นอน เพราะ
         A* กระจายทุก nodes ที่ f(n) < C*
         A* กระจายบาง nodes ที่ f(n) = C*
         A* ไม่กระจาย nodes ที่ f(n) > C*

• Time/ Space Complexity ?
‣ เพิ่มขึ้นอย่างเป็น exponential (ประมาณเท่ากับ BFS); bd
‣ เก็บทุก nodes ลงหน่วยความจำ
ยกเว้น |h(n) - h*(n)| ≤ O(log(h*(n))) เมื่อ h*(n) คือ cost ที่แท้จริงจาก n ถึง goal เป็นเงื่อนไขสำหรับ subexponential growth






(มีต่อ № 2)




Create Date : 06 ธันวาคม 2550
Last Update : 6 ธันวาคม 2550 17:25:33 น. 0 comments
Counter : 2005 Pageviews.

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