creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 
uninformed search

uniformed search = blind search



b = maximum branching factor (no. of children)
d = depth of the shallowest goal node
m = maximum length of any path in the state space

ตัวอย่าง


b = 3, d = 1, m = 2

Uninformed Search Strategies:
» Breadth-First Search
» Uniform-Cost Search
» Depth-First Search
» Depth-Limited Search
» Iterative Deepening Depth-First Search

º Breadth-First Search



Completeness ?
» แน่นอน (ยกเว้น เจอ node ที่มีลูกเป็นอนันต์)

Optimal Solution ?
» ไม่แน่ (ยกเว้น step costs ทุก edge เท่ากัน)

Time Complexity ?
» จำนวน node ทั้งหมดที่ต้องสร้าง (สูงสุดที่เป็นไปได้) x เวลาสร้าง 1 node



TBFS = (b + b2 + b3 + ... + bd + bd+1 - b) x T1NODE ~ O(bd+1)

Space Complexity ?
» Space Complexity = Time Complexity

º Uniform-Cost Search
• Uniform-Cost = Lowest-Cost-First Search
• ลำดับ node ใน frontier จาก costs ต่ำสุด
• ถ้า step costs เท่ากันทั้งหมด: UFS = BFS

Completeness ?
» แน่นอน ตราบเท่าที่ทุก step costs ≥ ε (จำนวนบวกน้อยที่สุด)

Optimal Solution ?
» 100% (ตราบเท่ามันที่ทำงานสำเร็จ)

Time/ Space Complexity ?
» C* = cost of the optimal solution



เมื่อสมมติให้แต่ละ action (หรือ step) มี costs อย่างต่ำเท่ากับ ε
uniform-cost complexity ~ O(b1+C*)

ตัวอย่างปัญหา UCS
• Completeness ? อาจไปไม่ถึงฝั่ง



• Time/ Space Complexity อาจสูงมากกว่าจะถึงฝั่ง (พื้นที่แรเงาคือ cost contours)



º Depth-First Search



Completeness ?
» ไม่แน่ อาจเจอแบบนี้



Optimal Solution ?
» ไม่แน่ เช่นกรณี C กับ J เป็น goal nodes ทั้งคู่ แต่ DFS หยุดที่ J



Time Complexity ?
» O(bm); นานมาก ถ้า m > d มาก ๆ



Space Complexity ?
» O(bm); เนื้อที่มากสุดที่ DFS ต้องการเก็บ node คือ bm+1

• ถ้าเราประหยัดเนื้อที่หน่วยความจำโดยบันทึก explored node ที่เป็น successor เพียง 1 node เรียก Backtracking Search มี Space Complexity ~ O(m)

º Depth-Limited Search
• คือ DFS ที่จำกัด depth = l

Completeness ?
» ไม่สำเร็จแน่ ๆ ถ้า l < d

Optimal Solution ?
» เหมือน DFS (ถ้าสำเร็จ)

Time Complexity ?
» O(bl)

Space Complexity ?
» O(bl)

º Iterative Deepening Depth-First Search
• คือการวนทำ DLS ตั้งแต่ l = 0...∞ หรือทำสำเร็จ

ตัวอย่าง IDS
l = 1


l = 2


l = 3


Completeness/ Optimal Solution ?
» เหมือน BFS

Time Complexity ?
» O(bd)

Space Complexity ?
» O(bd)

º Bi-directional Search
• search พร้อม ๆ กันทั้งจาก start และ จาก goal หยุดเมื่อพบกันที่กึ่งกลาง



Time/ Space Complexity ?
» O(bd/2) จึงทำให้เกิดข้อได้เปรียบเพราะ 2bd/2 << bd


เราต้องตรวจจับการซ้ำสถานะ (Repeated States) เพื่อป้องกันการทำงานเพิ่มโดยไม่จำเป็น

ตัวอย่าง Repeated State


ตัวอย่าง Repeated State
สำหรับ BFS เราไม่จำเป็นต้องกระจาย node ที่วงกลมเอาไว้ (เพราะอะไร ?)










Create Date : 04 ธันวาคม 2550
Last Update : 5 มกราคม 2551 18:13:01 น. 0 comments
Counter : 2050 Pageviews.

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