AI筆計
原來DFS有分兩種
一種是我們平常用recursive ,space complexity O(m),m是deepest depth
另一種就是
當遇到一個node如果它所有node都已expand過or沒有node可以expand,那就pop
不然就把它expand的所有node放入stack,直到找到答案
space complexity O(bm),b is branching factor(最大分支數)
第二種方法不需要做undo的動作
A*中
f(n) = g(n) + h(n)
// g(n) is cost so far to reach n
// h(n) is estimated cost to goal from n
當都讓g(n) = 0時,便是greedy
當都讓h(n) = 0,便是uniform-cost search
RBFS
這也是一種類似A*的方式
只是較節省memory
當此node I展開的node 中最好的值並不是全部當中最好的
就用這個值來取代此node I的值,並不把展開的所有node放進priority queue
所以節省很多記憶體,
space O(bd) ,b is 最大展開之node數,d is max depth
疊代加深Ａ*搜尋演算法
function IDA*(probelm) returns a solution sequence
inputs: problem, a problem
static: f-limit, the current f-Cost limit
root, a node
root <— Make-Node(Initial-State[problem])
f-limit <— f-Cost(root)
loop do
solution,f-limit <— DFS-Contour(root,f-limit)
if solution is non-null then retuen soluiton
if f-limit=INF then return failure; end
function DFS-Contour(node,f-limit) return a solution sequence and a new f-Cost l
imit
inputs: node, a node
f-limit, the current f-Cost limit
static: next-f, the f-Cost limit for the next contour, initially INF
if f_Cost[node]>f-limit then return null, f-Cost[node]
if Goal-Test[problem](State[node]) then return node,f-limit
for each node s in Successors(node) do
solution,new-f <— DFS-Contour(s,f-limit)
if solutin is non-null then return solution,f-limit
next-f <— Min(next-f,new-f); end
return null,next-f
logic:
A |= B :
iff A is true imply B is true.
iff (A and ~B ) is unsatisfiable.
A (|-)_i B :
B is derived from A by i.
i is sound:
if whenever A (|-)_i B,it is also true that A |= B.
(derive only entailed sentences.)
i is completeness:
if whenever A |= B, it is also true that A (|-)_i B.
the algorithm can derive any sentence that is entailed.
logical equivalence :
A ≡ B iff A |= B and B |= A
validity:
is true in all model.
satisfiablility:
is true in some model.
A ≡ B iff A |= B and B |= A
