• Many AI problems can be solved by exploring the so called solution space. It contains all possible sequences of actions that might be applied by an agent. Some of these sequences lead to a solution.
  • The agent examines alternative sequence of actions that lead to known states and chooses, then, the best one.
  • The process of trying this sequence is called SEARCH.
  • It is useful to think about the search process like building a search tree whose nodes are states and whose branches are operators/actions.
• A search algorithm takes as input a problem and returns a solution in the form of a sequence of actions.
• Once the solution is found, the suggested actions can be performed.
  • This is called EXECUTION.

To Generate sequences of actions.

• Expansion: one starts from a state, and applying the operators (or successor function) will generate new states.
• [[#Search strategy]]: at each step, choose which state to expand.
• Search tree: It represents the expansion of all states starting from the initial state (the root of the tree).
• The leaves of the tree represent either states to expand or solutions or dead-ends

Search strategy

The choice on how to expand a search tree is called strategy.

Non informed strategies

Do not use any domain knowledge: apply rules arbitrarily and do an exhaustive search strategy

• Impractical for some complex problems.

The Strategies are evaluated according to four criteria:

• Completeness: does the strategy guarantees to find a solution if one exists?
• Time complexity: how long does it take to find a solution?
• Space complexity: how much memory is needed to carry out the search?
• Optimality: does the strategy find the best solution when there are more solutions?

breadth-first (at a uniform cost)

BFS, breadth first search. Expand nodes by FIFO, so BFS always expand less deep nodes.

If depth is $d$, the branching factor is $b$, in the the worst case, time and space complexity will be $b^d$.(all nodes be expanded).

This strategy ensures COMPLETENESS, but we don’t have EFFICIENT IMPLEMENTATIONS on single-processor systems (multi-processor architectures).

理论上BFS能找到最优解，但是吃内存和时间。

Breadth-first search always finds the min-cost path if the cost equals the depth (otherwise we should use another strategy that always expands the least cost node a uniform cost strategy).

The uniform-cost strategy is comprehensive and, unlike the breadth-first search, ideal when operators have not uniform costs. (Same temporal and spatial complexity as breadth-first search).

depth-first

DFS, depth first search. LIFO. Space complexity is $b\ast d$, time complexity is $b^d$.

Depth-first search can be NON-COMPLETE with possible loops in the presence of infinite branches.

depth-first limited depth;

DFS with a maximum depth parameter to avoid infinite branches.

iterative deepening.

DFS with iterative maximum depth parameter.

Informed strategies

Use domain knowledge: apply rules following a heuristics

• If we had a perfect heuristics you do not need search

Best first search

Best first search uses evaluation functions that compute a number that represents the desirability of the node expansion.

Evaluation Function $f(n)=h(n)$ (heuristic) 只考虑节点到root的估测成本。

• $h(n)$ = Estimate of the cost from n to the goal

不保证全局最优，只找当前最优解。

A-star

• Instead of only considering the distance to the goal, also consider the "cost" in reaching the node n from the root.

• We expand nodes for increasing values of $f(n)=g(n)+h^{\prime }(n)$

• Where $g(n)$ is the depth of the node, and $h^{\prime }(n)$ the estimated distance from the goal.

• We choose the node to expand as the one for which this sum is smaller.

• 不保证全局最优。

• If h '= 0 we always obtain a feasible heuristic function BFS

• 在 graph search 的时候，每个节点的f等于该节点相对于root的h，加上从root到此节点所有路径的cost g。

• A heuristic function h(n) is consistent (monotone) if, for each node n for every successor n’ of n applying operator a, the following holds:h(n) <= c(n, a, n’) + h(n’)

  在启发式搜索（如 A* 算法）中，如果一个启发式函数 h(n) 满足该不等式，即意味着：从当前节点 n 到目标的估计代价，不能大于“从 n 到后继节点 n′ 的实际代价”加上“从 n′ 到目标的估计代价”,。

  • h(n)：从当前节点 n 到达目标的预估代价。
  • c(n,a,n′)：应用操作 a 从节点 n 移动到后继节点 n′ 的实际成本。
  • h(n′)：从后继节点 n′ 到达目标的预估代价。