лекция 2. общие стратегии поиска.

Views:
 
Category: Entertainment
     
 

Presentation Description

Общие стратегии поиска.

Comments

Presentation Transcript

Blind (Uninformed) Search (Where we systematically explore alternatives) R&N: Chap. 3, Sect. 3.3–5 :

1 Blind (Uninformed) Search (Where we systematically explore alternatives) R&N: Chap. 3, Sect. 3.3–5

Simple Problem-Solving-Agent Agent Algorithm:

2 Simple Problem-Solving-Agent Agent Algorithm s 0  sense/read initial state GOAL?  select/read goal test Succ  read successor function solution  search (s 0 , GOAL?, Succ) perform(solution)

Search Tree:

3 Search Tree Search tree Note that some states may be visited multiple times State graph

Search Nodes and States:

4 Search Nodes and States 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 6 8 1 3 4 5 6 7 8 2 4 7 2 1 2 3 4 5 6 7 8

Search Nodes and States:

5 Search Nodes and States 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 6 8 1 3 4 5 6 7 8 2 4 7 2 1 2 3 4 5 6 7 8 If states are allowed to be revisited, the search tree may be infinite even when the state space is finite

Data Structure of a Node:

6 Data Structure of a Node PARENT-NODE 1 2 3 4 5 6 7 8 STATE Depth of a node N = length of path from root to N (depth of the root = 0) BOOKKEEPING 5 Path-Cost 5 Depth Right Action Expanded yes ... CHILDREN

Node expansion:

7 Node expansion The expansion of a node N of the search tree consists of: Evaluating the successor function on STATE (N) Generating a child of N for each state returned by the function node generation  node expansion 1 2 3 4 5 6 7 8 N 1 3 5 6 8 1 3 4 5 6 7 8 2 4 7 2 1 2 3 4 5 6 7 8

Fringe of Search Tree:

8 Fringe of Search Tree The fringe is the set of all search nodes that haven’t been expanded yet 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 3 5 6 8 1 3 4 5 6 7 8 2 4 7 2 1 2 3 4 5 6 7 8

Slide 9:

9 Is it identical to the set of leaves?

Search Strategy:

10 Search Strategy The fringe is the set of all search nodes that haven’t been expanded yet The fringe is implemented as a priority queue FRINGE INSERT(node,FRINGE) REMOVE(FRINGE) The ordering of the nodes in FRINGE defines the search strategy

Search Algorithm #1:

11 Search Algorithm #1 SEARCH#1 If GOAL?(initial-state) then return initial-state INSERT( initial-node,FRINGE) Repeat: If empty(FRINGE) then return failure N  REMOVE(FRINGE) s  STATE( N ) For every state s’ in SUCCESSORS( s ) Create a new node N’ as a child of N If GOAL?( s’ ) then return path or goal state INSERT( N’ ,FRINGE) Expansion of N

Performance Measures:

12 Performance Measures Completeness A search algorithm is complete if it finds a solution whenever one exists [What about the case when no solution exists?] Optimality A search algorithm is optimal if it returns a minimum-cost path whenever a solution exists Complexity It measures the time and amount of memory required by the algorithm

Blind vs. Heuristic Strategies:

13 Blind vs. Heuristic Strategies Blind (or un-informed ) strategies do not exploit state descriptions to order FRINGE. They only exploit the positions of the nodes in the search tree Heuristic (or informed ) strategies exploit state descriptions to order FRINGE (the most “promising” nodes are placed at the beginning of FRINGE)

Example:

14 Example For a blind strategy , N 1 and N 2 are just two nodes (at some position in the search tree) Goal state N 1 N 2 STATE STATE 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

Example:

15 Example For a heuristic strategy counting the number of misplaced tiles, N 2 is more promising than N 1 Goal state N 1 N 2 STATE STATE 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

Remark:

16 Remark Some search problems, such as the (n 2 -1)-puzzle, are NP-hard One can’t expect to solve all instances of such problems in less than exponential time (in n) One may still strive to solve each instance as efficiently as possible  This is the purpose of the search strategy

Blind Strategies:

17 Blind Strategies Breadth-first Bidirectional Depth-first Depth-limited Iterative deepening Uniform-Cost (variant of breadth-first) Arc cost = 1 Arc cost = c(action)    0

Breadth-First Strategy:

18 Breadth-First Strategy New nodes are inserted at the end of FRINGE 2 3 4 5 1 6 7 FRINGE = (1)

Breadth-First Strategy:

19 Breadth-First Strategy New nodes are inserted at the end of FRINGE FRINGE = (2, 3) 2 3 4 5 1 6 7

Breadth-First Strategy:

20 Breadth-First Strategy New nodes are inserted at the end of FRINGE FRINGE = (3, 4, 5) 2 3 4 5 1 6 7

Breadth-First Strategy:

21 Breadth-First Strategy New nodes are inserted at the end of FRINGE FRINGE = (4, 5, 6, 7) 2 3 4 5 1 6 7

Important Parameters:

22 Important Parameters Maximum number of successors of any state  branching factor b of the search tree Minimal length (≠ cost) of a path between the initial and a goal state  depth d of the shallowest goal node in the search tree

Evaluation:

23 Evaluation b : branching factor d : depth of shallowest goal node Breadth-first search is: Complete? Not complete? Optimal? Not optimal?

Evaluation:

24 Evaluation b : branching factor d : depth of shallowest goal node Breadth-first search is: Complete Optimal if step cost is 1 Number of nodes generated: ???

Evaluation:

25 Evaluation b : branching factor d : depth of shallowest goal node Breadth-first search is: Complete Optimal if step cost is 1 Number of nodes generated: 1 + b + b 2 + … + b d = ???

Evaluation:

26 Evaluation b : branching factor d : depth of shallowest goal node Breadth-first search is: Complete Optimal if step cost is 1 Number of nodes generated: 1 + b + b 2 + … + b d = (b d+1 -1)/(b-1) = O(b d )  T ime and space complexity is O(b d )

Big O Notation:

27 Big O Notation g(n) = O(f(n)) if there exist two positive constants a and N such that: for all n > N: g(n)  a  f(n)

Time and Memory Requirements:

28 Time and Memory Requirements d # Nodes Time Memory 2 111 .01 msec 11 Kbytes 4 11,111 1 msec 1 Mbyte 6 ~10 6 1 sec 100 Mb 8 ~10 8 100 sec 10 Gbytes 10 ~10 10 2.8 hours 1 Tbyte 12 ~10 12 11.6 days 100 Tbytes 14 ~10 14 3.2 years 10,000 Tbytes Assumptions: b = 10; 1,000,000 nodes/sec; 100bytes/node

Time and Memory Requirements:

29 Time and Memory Requirements d # Nodes Time Memory 2 111 .01 msec 11 Kbytes 4 11,111 1 msec 1 Mbyte 6 ~10 6 1 sec 100 Mb 8 ~10 8 100 sec 10 Gbytes 10 ~10 10 2.8 hours 1 Tbyte 12 ~10 12 11.6 days 100 Tbytes 14 ~10 14 3.2 years 10,000 Tbytes Assumptions: b = 10; 1,000,000 nodes/sec; 100bytes/node

Remark:

30 Remark If a problem has no solution, breadth-first may run for ever (if the state space is infinite or states can be revisited arbitrary many times) 12 14 11 15 10 13 9 5 6 7 8 4 3 2 1 12 15 11 14 10 13 9 5 6 7 8 4 3 2 1 ?

Bidirectional Strategy:

31 Bidirectional Strategy 2 fringe queues: FRINGE1 and FRINGE2 s Time and space complexity is O(b d/2 )  O(b d ) if both trees have the same branching factor b Question: What happens if the branching factor is different in each direction?

Depth-First Strategy:

32 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5 FRINGE = (1)

Depth-First Strategy:

33 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5 FRINGE = (2, 3)

Depth-First Strategy:

34 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5 FRINGE = (4, 5, 3)

Depth-First Strategy:

35 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

36 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

37 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

38 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

39 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

40 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

41 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Depth-First Strategy:

42 Depth-First Strategy New nodes are inserted at the front of FRINGE 1 2 3 4 5

Evaluation:

43 Evaluation b : branching factor d : depth of shallowest goal node m : maximal depth of a leaf node Depth-first search is: Complete? Optimal?

Evaluation:

44 Evaluation b : branching factor d : depth of shallowest goal node m : maximal depth of a leaf node Depth-first search is: Complete only for finite search tree Not optimal Number of nodes generated (worst case): 1 + b + b 2 + … + b m = O(b m ) Time complexity is O(b m ) Space complexity is O(bm) [or O(m)] [Reminder: Breadth-first requires O(b d ) time and space]

Depth-Limited Search:

45 Depth-Limited Search Depth-first with depth cutoff k (depth at which nodes are not expanded) Three possible outcomes: Solution Failure (no solution) Cutoff (no solution within cutoff)

Iterative Deepening Search:

46 Iterative Deepening Search Provides the best of both breadth-first and depth-first search Main idea: IDS For k = 0, 1, 2, … do: Perform depth-first search with depth cutoff k (i.e., only generate nodes with depth  k) Totally horrifying !

Iterative Deepening:

47 Iterative Deepening

Iterative Deepening:

48 Iterative Deepening

Iterative Deepening:

49 Iterative Deepening

Performance:

50 Performance Iterative deepening search is: Complete Optimal if step cost =1 Time complexity is: (d+1)(1) + db + (d-1)b 2 + … + (1) b d = O(b d ) Space complexity is: O(bd) or O(d)

Calculation:

51 Calculation db + (d-1)b 2 + … + (1) b d = b d + 2b d-1 + 3b d-2 +… + db = (1 + 2b -1 + 3b -2 + … + db -d )  b d  ( S i=1,…,  ib (1-i) )  b d = b d ( b/(b-1) ) 2

Number of Generated Nodes (Breadth-First & Iterative Deepening):

52 d = 5 and b = 2 BF ID 1 1 x 6 = 6 2 2 x 5 = 10 4 4 x 4 = 16 8 8 x 3 = 24 16 16 x 2 = 32 32 32 x 1 = 32 63 120 120/63 ~ 2 Number of Generated Nodes (Breadth-First & Iterative Deepening)

Number of Generated Nodes (Breadth-First & Iterative Deepening):

53 Number of Generated Nodes (Breadth-First & Iterative Deepening) d = 5 and b = 10 BF ID 1 6 10 50 100 400 1,000 3,000 10,000 20,000 100,000 100,000 111,111 123,456 123,456/111,111 ~ 1.111

Comparison of Strategies:

54 Comparison of Strategies Breadth-first is complete and optimal, but has high space complexity Depth-first is space efficient, but is neither complete, nor optimal Iterative deepening is complete and optimal, with the same space complexity as depth-first and almost the same time complexity as breadth-first Quiz: Would IDS + bi-directional search be a good combination?

Revisited States:

55 Revisited States 8-queens No assembly planning Few 1 2 3 4 5 6 7 8 8-puzzle and robot navigation Many search tree is finite search tree is infinite

Avoiding Revisited States:

56 Avoiding Revisited States Requires comparing state descriptions Breadth-first search: Store all states associated with generated nodes in VISITED If the state of a new node is in VISITED, then discard the node

Avoiding Revisited States:

57 Avoiding Revisited States Requires comparing state descriptions Breadth-first search: Store all states associated with generated nodes in VISITED If the state of a new node is in VISITED, then discard the node Implemented as hash-table or as explicit data structure with flags

Avoiding Revisited States:

58 Avoiding Revisited States Depth-first search: Solution 1: Store all states associated with nodes in current path in VISITED If the state of a new node is in VISITED, then discard the node ??

Avoiding Revisited States:

59 Avoiding Revisited States Depth-first search: Solution 1: Store all states associated with nodes in current path in VISITED If the state of a new node is in VISITED, then discard the node Only avoids loops Solution 2: Store all generated states in VISITED If the state of a new node is in VISITED, then discard the node  Same space complexity as breadth-first !

Uniform-Cost Search:

60 Uniform-Cost Search Each arc has some cost c   > 0 The cost of the path to each node N is g(N) =  costs of arcs The goal is to generate a solution path of minimal cost The nodes N in the queue FRINGE are sorted in increasing g(N) Need to modify search algorithm S 0 1 A 5 B 15 C S G A B C 5 1 15 10 5 5 G 11 G 10

Search Algorithm #2:

61 Search Algorithm #2 SEARCH#2 INSERT( initial-node,FRINGE) Repeat: If empty(FRINGE) then return failure N  REMOVE(FRINGE) s  STATE( N ) If GOAL?( s ) then return path or goal state For every state s’ in SUCCESSORS( s ) Create a node N’ as a successor of N INSERT( N’ ,FRINGE) The goal test is applied to a node when this node is expanded , not when it is generated.

Avoiding Revisited States in Uniform-Cost Search:

62 Avoiding Revisited States in Uniform-Cost Search For any state S , when the first node N such that STATE ( N ) = S is expanded, the path to N is the best path from the initial state to S N N’ N” g(N)  g(N’) g(N)  g(N”)

Avoiding Revisited States in Uniform-Cost Search:

63 Avoiding Revisited States in Uniform-Cost Search For any state S , when the first node N such that STATE ( N ) = S is expanded, the path to N is the best path from the initial state to S So: When a node is expanded , store its state into CLOSED When a new node N is generated: If STATE (N) is in CLOSED , discard N If there exits a node N’ in the fringe such that STATE (N’) = STATE (N), discard the node -- N or N’ -- with the highest-cost path

authorStream Live Help