Chapter 3 search

One . Some search concepts

• edge （ Open node table ）： A collection of all leaf nodes to be extended

• CLOSE surface ： Used to record nodes that have been expanded

• Performance evaluation of the algorithm

  • completeness ： If there is a problem , Can find the solution

  • Optimality ： The solution found is optimal

  • Time complexity

  • Spatial complexity

    • A measure of time and space complexity ：

      1. Time is measured by the number of nodes generated in the search process

      2. Space is measured by the maximum number of nodes stored in memory

      3. Usually less than the number of state spaces |V|+|E|

• Branching factors ： How many child nodes can a node expand , That is, the number of branches of the tree

Search tree

Search graph

Be careful

Tree search ： Repeated states increase time overhead , Even lead to dead circulation
Figure search ： Avoid repeating states , It costs a lot of space

Two . No information search

1. BFS

BFS The most important thing is to solve the problem of space ,O(b^d) Complexity . Space for O(b^m)

2. The price of consistency （Djakarta） Algorithm

f(n) = g(n)

Every time you select f(n) Expand the largest or smallest （ Using priority queues , Record nodes ）

If the consensus cost exists, the cost is 0 Your actions will fall into a dead circle .

If the cost of each step is greater than or equal to 0, Then the uniform cost algorithm is complete

Time complexity O(b^{(1+lowbound(C/e)})

Spatial complexity O(b^{1+lowbound(C/e)})

3. DFS

4. Depth limited search （ Not a specific search algorithm ）

The assumed depth is l The node of has no successor node

When the depth reaches a certain value, it will not search deeply . This is equivalent to a height of h Using the depth first algorithm on the tree

Time complexity O(b^m)

Spatial complexity O(bm)

5. Depth first algorithm for iterative deepening

This algorithm calls the above depth limited search ( From depth to 0 To maximum depth d,)

Algorithm simulation

The depth is increasing . For each depth, the depth first algorithm is adopted . If the solution appears at the last layer, the search process will be very huge .

Breadth first iteration deepening is meaningless , Because breadth first search is always increasing in depth . There is no need to limit the depth of the search .

Performance analysis

For a depth of d, The number of branches is b The situation of ,

• The number of nodes generated by the depth constrained search algorithm is ：

  N(DLS)= b0 + b1+…+ bd

• The number of nodes generated by the depth first algorithm of iterative deepening is ：

  N(IDS)=(d+1)+(d)b+(d-1)*b2+….+(1)bd

  The first layer has a node , But it generated (d+1) Time

  The second floor has b Nodes , Generated (d) Time

  The third layer has b² individual , Generate (d-1)

  . . .

• When b = 10, d = 5,

  N(DLS)= 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111

  N(IDS)= 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456

Time complexity O(b^m)

Spatial complexity O(bm)

6. Two way search

No information search performance

3、 ... and . Heuristic search

Heuristic search mainly depends on heuristic function f(n) = g(n) + h(n) Expand . Considering both the past state and the future state

• f(n) : Evaluate the value of the current node
• g(n) : The value from the starting point to the current node
• h(n) : The estimated value from the current node to the big target

1. Greedy best first algorithm （GBS）

f(n) = h(n)

Select the node closest to the target to expand each time （ Using priority queues , Record nodes ）

Greedy algorithm is designed to extend the nearest node from the current node to the target node . This algorithm only uses the simplest heuristic function f(n)=h(n), In the case of Romania , It uses the straight-line distance from the current location to the destination （ This information cannot be calculated from the description of the problem itself , And this information is useful —— Because it is related to the actual distance , So it's a useful heuristic ）, In this question ,GBS The search cost is minimal , But not the best .

Why the uniform cost algorithm can get the optimal value but the greedy optimal algorithm can not

Because the heuristic function selected by the uniform cost algorithm is f(n) = g(n), Is the actual value from the starting point to the current node

The heuristic function selected by the uniform cost algorithm is f(n) = h(n), Is the estimated value from the starting point to the current node

There is an error in the estimated value , The actual value does not exist

• Complexity :
  • Time O(b^m)
  • Space O(b^m)

2. A* Algorithm

It combines the uniform cost algorithm and the greedy optimal algorithm .A* The algorithm is both complete and optimal

f(n) = g(n) + h(n) As an evaluation function , Use priority queues to extend f(n) The largest or smallest node , Until the desired results of the search .

Consistent heuristics are acceptable

A* Proof of algorithm optimality

Heuristic search performance analysis

Relaxation problem

e-20211114160804112" style=“zoom:67%;” />