informed search № 2
(ต่อจาก № 1)

Heuristic Function
heuristic คือข้อมูลช่วยในการเดาขั้นต่อไปสำหรับแก้ปัญหา

ตัวอย่าง 1


h1(n) = จำนวนหมายเลขที่อยู่ผิดที่ = 6
h2(n) = ผลรวม Manhattan distance = 4+0+3+3+1+0+2+1 = 14

ตัวอย่าง 2 ใช้ A*
f(n) = g(n) + h(n)
เมื่อ h(n) = จำนวนแผ่นสีที่อยู่ผิดที่


ตัวอย่าง 3 Robot Navigation
f(n) = g(n) + h(n)
เมื่อ h(n) = การกระจัดจาก n ถึง goal


‣ ถ้า h2(n) ≥ h1(n) สำหรับทุก n เราเรียก h2(n) dominates h1(n) ใช้ h2(n) ในการ search ดีกว่า h1(n)

‣ h(n) = max{hi(n)}


Relaxed Problems
• Relaxed problem = ปัญหาที่มีข้อบังคับน้อย
• Relaxed problem → Admissible heuristic

จากตัวอย่าง 1มีข้อบังคับ
‣ ช่อง A เลื่อนไปยังช่อง B ได้ก็ต่อเมื่อ A อยู่ติดกับ B และ B เป็นช่องว่าง

Relaxed version 1
‣ A เลื่อนไปยัง B เมื่อ B ว่าง → สามารถใช้ h1(n)
Relaxed version 2
‣ A เลื่อนไปยัง B เมื่อ A อยู่ติดกับ B → สามารถใช้ h2(n)

º Iterative Deepening A*
• Each iteration is depth-first with cutoff on the value of f(n) of expanded nodes

ตัวอย่าง cutoff = 4
f(n) = g(n) + h(n)
เมื่อ h(n) = จำนวนแผ่นสีที่อยู่ผิดที่

STEP 1

STEP 2

STEP 3

STEP 4

STEP 5


• เพิ่ม cutoff = 5









Create Date : 13 ธันวาคม 2550
Last Update : 5 มกราคม 2551 21:16:22 น.
Counter : 1276 Pageviews.

3 comments
  
f(n) = g(n) + h(n)
แล้ว g(n) คือไรคับ?
โดย: ไซลาซ (Zilarx ) วันที่: 25 เมษายน 2551 เวลา:0:49:12 น.
  
g(n) = cost รวมจากจุดเริ่มต้นจนถึง n
โดย: ศล วันที่: 29 เมษายน 2551 เวลา:2:11:10 น.
  
กำลังเขียนโปรแกรม(เล่น ๆ) เกี่ยวกับเรื่องนี้อยู่

สำหรับผมกลับเข้าใจไปว่า g(n)= ลำดับของโหนด(level) ใน state space tree.



โดย: ray (Hueristic ) วันที่: 2 ตุลาคม 2554 เวลา:5:37:14 น.
ชื่อ : * blog นี้ comment ได้เฉพาะสมาชิก
Comment :
 *ส่วน comment ไม่สามารถใช้ javascript และ style sheet
 

Zol.BlogGang.com

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

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

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