高级人工智能

摘要

国立*大学于天立教授的视频笔记

Search

For example:

Inital state :No queen on the board

Actions : Add a queen on the board where the square is empty

Transition model : return the board with a queen added to the spacified squere

Goal test : 8 queens are on the board ,none attacked

Path cost : numbers of trials

Different States space will be have different Solution space

b:maximum branching factor of the search tree

d:depth of the least-cost solution

m:maximum depth of the state space (may be $\infty$∞)

Uniformed Search 无信息搜索

Uniformed strategies use only the information available in the problem definition

Breadth-first search(BFS)

1,Expand the shallowest unexpanded node

2,FIFO queue

Completeness	Optimality	Time complexity	Space complexity
yes(if b is finite)	yes	$O(b^d)$O(bd)	$O(b^d)$O(bd)

Uniform-cost search

an special example of BFS

expand the unexpanded node with the lowest path cost

Priority queue orderd by $g(n)$g(n)

equivalent to BFS if step costs all equal

For TREE-SEARCH , priority queue gives the cheapest path first

For GRAPH_SEARCH , if the node is already in the frontier , need to find the minimum cost , and call DECREASEKEY as needed

Completeness	Optimality	Time complexity	Space complexity
yes	yes	$O(b^{1+\lfloor \frac{C^*}{\epsilon}\rfloor})$O(b1+⌊ϵC∗​⌋)	$O(b^{1+\lfloor \frac{C^*}{\epsilon}\rfloor})$O(b1+⌊ϵC∗​⌋)

Depth-first search(DFS)

1,expand the deepest unexpand node

2,stack

Completeness	Optimality	Time complexity	Space complexity
No	No	$O(b^m)$O(bm)	$O(m)$O(m) !!! linear

Depth-limited search

Iterative deepening search(IDS)

Call DLS iteratively with increasing depth limit

Seems to be wasteful , but actually not

Combine the benefits of BFS and DFS

for depth = 0 to $\infty$
    result = DLS(problem,depth)
    if result != cutoff
        return result

Completeness	Optimality	Time complexity	Space complexity
Yes	Yes only if step cost = 1	$O(b^d)$O(bd)	$O(bd)$O(bd)

Bidirectional Search

Summay

a:if b is finite

b:if b is finite and step cost >= $\epsilon$ϵ

c:unless $,$, >= d

d:if b is finite and both direction use complete search like BFS

e:if all steps cost are identical

Criterion	Breadth-first search	Uniform-Cost	Depth-first search(DFS)	Depth-limited search	Iterative deepening search(IDS)	Bi-Directional
Completeness	$Y^a$Ya	$Y^b$Yb	$N$N	$N^c$Nc	$Y^a$Ya	$Y^d$Yd
Optimality	$Y^e$Ye	$Y$Y	$N$N	$N$N	$Y^e$Ye	$Y^e$Ye
Time Complexity	$O(b^d)$O(bd)	$O(b^{1+\lfloor \frac{C^*}{\epsilon}\rfloor})$O(b1+⌊ϵC∗​⌋)	$O(b^m)$O(bm)	$O(b^)$O(b)	$b^d$bd	$O(b^{d/2})$O(bd/2)
Space Complexity	$O(b^d)$O(bd)	$O(b^{1+\lfloor \frac{C^*}{\epsilon}\rfloor})$O(b1+⌊ϵC∗​⌋)	$O(bm)$O(bm)	$O(b^)$O(b)	$O(bd)$O(bd)	$O(b^{d/2})$O(bd/2)

Graph search can be exponentially more efficient than tree search

Informed Search 有信息搜索(启发式搜索)

Best-First Search

use an evaluation function($h(n)$h(n)) for each node to estimate the desirability

$h(n)$h(n) estimates the cost from node n to the closest goal

(1),Greedy search

$f(n) = h(n)$f(n)=h(n)

(2),$A^*$A∗ search

$f(n) = h(n) + g(n)$f(n)=h(n)+g(n)

$f(n)$f(n):the total cost

$h(n)$h(n):

$g(n)$g(n):

$h^*(n)$h∗(n):

$A^* = \text{greedy} + \text{uniform cost}$A∗=greedy+uniform cost

idea:Avoid expanding paths that are already expensive

(3),Optimality of $A^*$A∗

Optimality of $A^*$A∗ search in tree search:

admissable:可容纳性:

$\text{for all n} ~ ,~ 0\leqslant h(n) \leqslant h^*(n)$for all n , 0⩽h(n)⩽h∗(n)
$0\leqslant h(G) \leqslant h(G^{\prime}) \leqslant 0 => h(G^{\prime}) = h(G) = 0$0⩽h(G)⩽h(G′)⩽0=>h(G′)=h(G)=0
$\text{Goal:}~:~f(G^{\prime}) > f(n)$Goal: : f(G′)>f(n)
$f(G^{\prime}) = g(G^{\prime}) + h(G^{\prime}) =$f(G′)=g(G′)+h(G′)=
$g(G^{\prime}) >=$g(G′)>=
$g(G) =$g(G)=
$g(n) + h^*(n) >=$g(n)+h∗(n)>=
$g(n) + h(n) = f(n)$g(n)+h(n)=f(n)

Optimality of $A^*$A∗ search in graph search:

consistent:一致性，三角不等式

$\text{consistent:}~h(n) \leqslant c(n,a,n^{\prime}) + h(n^{\prime})$consistent: h(n)⩽c(n,a,n′)+h(n′)
$\text{Goal:}~:~f(n^{\prime}) >= f(n)$Goal: : f(n′)>=f(n)
$f(n^{\prime}) = g(n^{\prime}) + h(n^{\prime}) =$f(n′)=g(n′)+h(n′)=
$g(n) + c(n,a,n^{\prime}) + h(n^{\prime}) >=$g(n)+c(n,a,n′)+h(n′)>=
$g(n) + h(n) =$g(n)+h(n)=
$f(n)$f(n)

Memory Bounded Search

(1),Ilerative deepending $A^*$A∗

(2),Recursive best-first search

(3),Simplified

Heuristic

(1),

(2),