›
›

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

Download
Heuristic Search  
Chapter 3  
Outline  
• Generate-and-test  
• Hill climbing  
• Simulated annealing  
• Best-first search  
• Means-ends analysis  
• Constraint satisfaction  
Cao Hoang Tru  
CSE Faculty - HCMUT  
2
24 February, 2009  
Generate-and-Test  
Algorithm  
1. Generate a possible solution.  
2. Test to see if this is actually a solution.  
3. Quit if a solution has been found.  
Otherwise, return to step 1.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
3
24 February, 2009  
Generate-and-Test  
• Acceptable for simple problems.  
• Inefficient for problems with large space.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
4
24 February, 2009  
Generate-and-Test  
• Exhaustive generate-and-test.  
• Heuristic generate-and-test: not consider paths that  
seem unlikely to lead to a solution.  
• Plan generate-test:  
− Create a list of candidates.  
− Apply generate-and-test to that list.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
5
24 February, 2009  
Generate-and-Test  
Example: coloured blocks  
“Arrange four 6-sided cubes in a row, with each side of  
each cube painted one of four colours, such that on all four  
sides of the row one block face of each colour is showing.”  
Cao Hoang Tru  
CSE Faculty - HCMUT  
6
24 February, 2009  
Generate-and-Test  
Example: coloured blocks  
Heuristic: if there are more red faces than other colours  
then, when placing a block with several red faces, use few  
of them as possible as outside faces.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
7
24 February, 2009  
Hill Climbing  
• Searching for a goal state = Climbing to the top of a hill  
Cao Hoang Tru  
CSE Faculty - HCMUT  
8
24 February, 2009  
Hill Climbing  
• Generate-and-test + direction to move.  
• Heuristic function to estimate how close a given state  
is to a goal state.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
9
24 February, 2009  
Simple Hill Climbing  
Algorithm  
1. Evaluate the initial state.  
2. Loop until a solution is found or there are no new  
operators left to be applied:  
− Select and apply a new operator  
− Evaluate the new state:  
goal → quit  
better than current state → new current state  
Cao Hoang Tru  
CSE Faculty - HCMUT  
10  
24 February, 2009  
Simple Hill Climbing  
Algorithm  
1. Evaluate the initial state.  
2. Loop until a solution is found or there are no new  
operators left to be applied:  
− Select and apply a new operator  
− Evaluate the new state:  
goal → quit  
better than current state → new current state  
not try all possible new states!  
Cao Hoang Tru  
CSE Faculty - HCMUT  
11  
24 February, 2009  
Simple Hill Climbing  
Example: coloured blocks  
Heuristic function: the sum of the number of different  
colours on each of the four sides (solution = 16).  
Cao Hoang Tru  
CSE Faculty - HCMUT  
12  
24 February, 2009  
Simple Hill Climbing  
• Heuristic function as a way to inject task-specific  
knowledge into the control process.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
13  
24 February, 2009  
Steepest-Ascent Hill Climbing  
(Gradient Search)  
• Considers all the moves from the current state.  
• Selects the best one as the next state.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
14  
24 February, 2009  
Steepest-Ascent Hill Climbing  
(Gradient Search)  
Algorithm  
1. Evaluate the initial state.  
2. Loop until a solution is found or a complete iteration  
produces no change to current state:  
− Apply all the possible operators  
− Evaluate the best new state:  
goal → quit  
better than current state → new current state  
Cao Hoang Tru  
CSE Faculty - HCMUT  
15  
24 February, 2009  
Steepest-Ascent Hill Climbing  
(Gradient Search)  
Algorithm  
1. Evaluate the initial state.  
2. Loop until a solution is found or a complete iteration  
produces no change to current state:  
− SUCC = a state such that any possible successor of the  
current state will be better than SUCC (the worst state).  
− For each operator that applies to the current state, evaluate  
the new state:  
goal → quit  
better than SUCC → set SUCC to this state  
− SUCC is better than the current state → set the new current  
state to SUCC.  
Cao Hoang Tru  
16  
CSE Faculty - HCMUT  
24 February, 2009  
Hill Climbing: Disadvantages  
Local maximum  
A state that is better than all of its neighbours, but not  
better than some other states far away.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
17  
24 February, 2009  
Hill Climbing: Disadvantages  
Plateau  
A flat area of the search space in which all neighbouring  
states have the same value.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
18  
24 February, 2009  
Hill Climbing: Disadvantages  
Ridge  
The orientation of the high region, compared to the set  
of available moves, makes it impossible to climb up.  
However, two moves executed serially may increase  
the height.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
19  
24 February, 2009  
Hill Climbing: Disadvantages  
Ways Out  
• Backtrack to some earlier node and try going in a  
different direction.  
• Make a big jump to try to get in a new section.  
• Moving in several directions at once.  
Cao Hoang Tru  
CSE Faculty - HCMUT  
20  
24 February, 2009  
Tải về để xem bản đầy đủ
pdf 45 trang myanh 17820 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 3: Heuristic 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_3_heuristic_search.pdf