›
›

Bài giảng Trí tuệ nhân tạo - Chapter 2: Problems and Search

Download
Problems and Search  
Chapter 2  
Outline  
• State space search  
• Search strategies  
• Problem characteristics  
• Design of search programs  
Cao Hoang Tru  
CSE Faculty - HCMUT  
2
13 February, 2009  
State Space Search  
Problem solving  
=
Searching for a goal state  
Cao Hoang Tru  
CSE Faculty - HCMUT  
3
13 February, 2009  
State Space Search: Playing Chess  
• Each position can be described by an 8-by-8 array.  
• Initial position is the game opening position.  
• Goal position is any position in which the opponent  
does not have a legal move and his or her king is  
under attack.  
• Legal moves can be described by a set of rules:  
− Left sides are matched against the current state.  
− Right sides describe the new resulting state.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
4
13 February, 2009  
State Space Search: Playing Chess  
• State space is a set of legal positions.  
• Starting at the initial state.  
• Using the set of rules to move from one state to  
another.  
• Attempting to end up in a goal state.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
5
13 February, 2009  
State Space Search: Water Jug Problem  
“You are given two jugs, a 4-litre one and a 3-litre one.  
Neither has any measuring markers on it. There is a  
pump that can be used to fill the jugs with water. How  
can you get exactly 2 litres of water into 4-litre jug.”  
Cao Hoang Tru  
CSE Faculty - HCMUT  
6
13 February, 2009  
State Space Search: Water Jug Problem  
• State: (x, y)  
x = 0, 1, 2, 3, or 4  
• Start state: (0, 0).  
• Goal state: (2, n) for any n.  
y = 0, 1, 2, 3  
• Attempting to end up in a goal state.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
7
13 February, 2009  
State Space Search: Water Jug Problem  
1. (x, y)  
if x  
→
→
→
→
(4, y)  
(x, 3)  
<
4
3
0
0
2. (x, y)  
if y  
3. (x, y)  
if x  
4. (x, y)  
if y  
<
(x  
−
d, y)  
>
(x, y  
−
d)  
>
Cao Hoang Tru  
CSE Faculty - HCMUT  
8
13 February, 2009  
State Space Search: Water Jug Problem  
5. (x, y)  
if x  
→
→
→
→
(0, y)  
(x, 0)  
>
0
0
y
y
6. (x, y)  
if y  
7. (x, y)  
if x  
8. (x, y)  
if x  
>
(4, y  
−
(4  
−
x))  
+
≥
≥
4, y  
3, x  
>
>
0
0
(x  
−
(3  
−
y), 3)  
+
Cao Hoang Tru  
CSE Faculty - HCMUT  
9
13 February, 2009  
State Space Search: Water Jug Problem  
9. (x, y)  
if x  
→
→
(x  
+
y, 0)  
+
y
y
≤
≤
4, y  
3, x  
>
>
0
0
10. (x, y)  
if x  
(0, x  
+
y)  
+
11. (0, 2)  
12. (2, y)  
→
→
(2, 0)  
(0, y)  
Cao Hoang Tru  
CSE Faculty - HCMUT  
10  
13 February, 2009  
State Space Search: Water Jug Problem  
1. current state = (0, 0)  
2. Loop until reaching the goal state (2, 0)  
− Apply a rule whose left side matches the current state  
− Set the new current state to be the resulting state  
(0, 0)  
(0, 3)  
(3, 0)  
(3, 3)  
(4, 2)  
(0, 2)  
(2, 0)  
Cao Hoang Tru  
11  
13 February, 2009  
CSE Faculty - HCMUT  
State Space Search: Water Jug Problem  
The role of the condition in the left side of a rule  
⇒ restrict the application of the rule  
⇒ more efficient  
1. (x, y)  
if x  
→
→
(4, y)  
(x, 3)  
<
4
3
2. (x, y)  
if y  
<
Cao Hoang Tru  
CSE Faculty - HCMUT  
12  
13 February, 2009  
State Space Search: Water Jug Problem  
Special-purpose rules to capture special-case  
knowledge that can be used at some stage in solving a  
problem  
11. (0, 2)  
12. (2, y)  
→
→
(2, 0)  
(0, y)  
Cao Hoang Tru  
CSE Faculty - HCMUT  
13  
13 February, 2009  
State Space Search: Summary  
1. Define a state space that contains all the possible  
configurations of the relevant objects.  
2. Specify the initial states.  
3. Specify the goal states.  
4. Specify a set of rules:  
− What are unstated assumptions?  
− How general should the rules be?  
− How much knowledge for solutions should be in the  
rules?  
Cao Hoang Tru  
CSE Faculty - HCMUT  
14  
13 February, 2009  
Search Strategies  
Requirements of a good search strategy:  
1. It causes motion  
Otherwise, it will never lead to a solution.  
2. It is systematic  
Otherwise, it may use more steps than necessary.  
3. It is efficient  
Find a good, but not necessarily the best, answer.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
15  
13 February, 2009  
Search Strategies  
1. Uninformed search (blind search)  
Having no information about the number of steps from the  
current state to the goal.  
2. Informed search (heuristic search)  
More efficient than uninformed search.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
16  
13 February, 2009  
Search Strategies  
(0, 0)  
(4, 0)  
(0, 3)  
(4, 3)  
(0, 0)  
(1, 3)  
(4, 3)  
(0, 0)  
(3, 0)  
Cao Hoang Tru  
CSE Faculty - HCMUT  
17  
13 February, 2009  
Search Strategies: Blind Search  
• Breadth-first search  
Expand all the nodes of  
one level first.  
• Depth-first search  
Expand one of the nodes at  
the deepest level.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
18  
13 February, 2009  
Search Strategies: Blind Search  
Criterion  
Breadth-  
First  
Depth-  
First  
Time  
Space  
Optimal?  
Complete?  
b: branching factor  
d: solution depth  
m: maximum depth  
Cao Hoang Tru  
CSE Faculty - HCMUT  
19  
13 February, 2009  
Search Strategies: Blind Search  
Criterion  
Breadth-  
First  
Depth-  
First  
bd  
bm  
Time  
bd  
bm  
Space  
Optimal?  
Complete?  
Yes  
No  
Yes  
No  
b: branching factor  
d: solution depth  
m: maximum depth  
Cao Hoang Tru  
CSE Faculty - HCMUT  
20  
13 February, 2009  
Tải về để xem bản đầy đủ
pdf 50 trang myanh 18760 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Chapter 2: Problems and Search", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pdfbai_giang_tri_tue_nhan_tao_chapter_2_problems_and_search.pdf