AI DFS, Depth-Limited-Search

Depth-first search

가장 깊은 노드부터 expand 하는 기법으로, 일반 알고리즘에서 동작하는 방식과 동일합니다.

AI에서는 frontier 를 LIFO 큐로 구성하여 Grpah search 하는 방식입니다.

BFS = FIFO, Uniform-Cost Search = Priority queue, DFS = LIFO(Stack)

 

평가

• Completeness

• Grpah search : Yes : 단 state space 이 유한한 크기일 때

• Tree search : No : 방문했던 노드를 재방문 가능하므로 cycle 이 생길 수 있기 때문

• Optimality

• No : 항상 최적은 아님

• Time complexity

• Graph search : state space의 최대 사이즈

• Tree search : O(b^m)

• Space complexity

• Grpah search : state space 의 최대 사이즈

• Tree search : O(bm)
  매우 작은 공간만 필요해서 과거 AI 개발자들이 애용했던 서치 방법

 

 

Depth Limited Search

DFS Tree 버전의 시간복잡도를 줄이기 위해 등장한 아이디어입니다. DFS Tree 버전은 매우 뛰어난 공간복잡도를 지녔지만 지나치게 큰 시간 복잡도로 효율적으로 사용되기 어려웠습니다. DFS는 정답을 발견하지 못하면 밑도 끝도 없이 tree 의 밑부분까지 파고드는 것이 시간복잡도 증가의 큰 원인 중 하나였습니다. 따라서 파고들 수 있는 depth에 제한을 두어 시간복잡도를 개선했습니다.

 

fucntion DEPTH-LIMITED-SEARCH(problem, limit) returns a solution, or failure/cutoff
	return RECURSIVE-DLS(MAKE-NODE(problem.INITIAL-STATE), problem, limit)

function RECURSIVE-DLS(node, problem, limit) returns a solution, or failure/cutoff
	if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)	
	else if limit = 0 then return cutoff
	else
		cutoff_occurred ←  false
		for each action in problem.ACTIONS(node.state) do
			child ←  CHILD-NODE(problem, node, action)
			result ← RECURSIVE-DLS(child, problem, limit - 1)
			if result = cutoff then cutoff_occurred ← true
			else if result != failure then return result
		if cutoff_occurred then return cutoff else return failure

 

평가

l = depth limit

• Completeness

• No : l < d : 즉 Limit depth 으로 지정한 값보다 더 깊은 곳에 최초의 답이 있다면 답을 찾지 못함

• Optimal

• No

• Time complexity : O(b ^ l)

• Space complexity : O(bl)

 

l 값은 잘 지정해야합니다. l이 너무 얕으면 답을 찾지 못하고 깊으면 시간이 오래걸리기 때문입니다.