[人工知能]検索

saerch를 하는 agent는 goal-based agent周囲環境が観察可能、静的、離散的、確定的であると仮定する.

problem solving agent

algorithm

ターゲット・エージェントに基づく問題の解決エージェントの定義は、次のとおりです.

function SIMPLE-PROBLEM-SOLVING-AGENT(percept)
    state = UPDATE_STATE(state, percept)
	if seq is empty
        goal = FORMULATE_GOAL(state)
        problem = FORMULATE_PROBLEM(state, goal)
        seq = SEARCH(problem)
    action = FIRST(seq)
    seq = REST(seq)
return action

問題解決エージェントは,まず現在の状態と感知された更新状態に基づいている.検索seqが空でない場合は、ターゲットと問題を定義して検索します.
seqの最初の要素はactionとして、シーケンスに残りの要素しか残っていません.
アクションを返します.

general step

目標を設定-目標を定義します.

問題式-問題を定義する場合.

search-目標に達する行動を探します.

execute-行動します.

problem formualation

問題解決エージェントの一般的なフェーズには問題-式があります.問題を定義するプロセス.具体的には以下のように定義する.

initial state

actions

transition model

goal-test

path cost

このとき、initial state、actions、transitionモデルをすべて組み合わせてstatespaceを作成します.

ステータススペースの参照

stateとactionをとり,移動したstateは最終的にstatespaceを構成する.このstatespaceをよく探して、目標を達成するのがsearchの目標です.

tree search

statespaceをtreeと考えてから探索する方法があります.ツリーなので、繰り返しの状態が許されます.

function treeSearch(problem){
	fringe.insert(initialstate);
  
  	while(!fringe.empty){
    	node = fringe.pop();
      	if(goal(node)) return solution;
      
      	for(child in node.successors){
        	fringe.insert(child);
        }
    }
}

ストライプに初期状態を加えます.
そしてエッジでpop,goal testを続け,後続stateをエッジに入れて探索する.

graph search

graph searchでは重複した状態は許可されません.したがって、closed listを使用して以前にアクセスしたノードにアクセスするためのデータ構造が必要です.

function graphSearch(problem){
	fringe.insert(initialState)
  	closed = {};
  
  	while(!fringe.empty()){
    	node = fringe.pop();
      	if(goal(node)) return solutionl
      	closed.insert(node);
      
      	for(child in node.successors){
        	if(child not in cloesd or fringe){
            	fringe.insert(child);
            }
        }
    }
}

uninformed search

uninformed searchは,現在の状態が他の状態より良いかどうかを評価するのではなく,愚かな探索のみを行い,目標状態を探す過程である.
bfs、統一コスト検索、dfs、dls、ids、双方向検索などがここに属する.

bfs

function bfs(problem){
	closed = {};
  	fringe.insert(intialState);
  
  	while(!fringe.empty()){
    	node = fringe.pop();
      	closed.insert(node);
      
      	for(child in node.successors){
          if(child not in fringe or cloesd){
              	if(goal(child)) return solution;
            	fringe.insert(child);
            }
        }
    }
}

完備性:分岐因子bが限られている場合、常に答えが見つかる

time complexity : O(b^d)

space complexity : O(b^d)

最適性:stepコストが1の場合.そうでなければベスト

ではありません
bfsは良いですがstepコストが同じ場合にのみ使用でき、メモリ消費量が大きい

uniform cost search

bfsステップコストが固定されていない場合に使用する方法

function ucs(problem){
    closed={};
    fringe.insert(intialstate);
  
    while(!fringe.empty){
    	node = fringe.pop();
      	if(goal(node)) return solution;
      	closed.insert(node);
      
      	for(child in node.successors){
            if(child not in fringe or cloesd){
                fringe.insert(child);
            }
          else if(child.cost < fringe[child].cost){
              fringe.replace(child);
          }
        }
    }
}

completeness : yes

time complexity : O(b^(c*/e))

space complexity : O(b^(c*/e))

optimality : yes

dfs

完全性:状態空間が限られている場合yes

time complexity : O(b^d)

space complexity : O(bd)

最適性:No.複数のソリューションがある場合に最初に発見されるのが答えです.(次のソリューションは、より低コストである可能性があります)

dls

dfsで深さをlに制限する方法

function dls(node, limit){
  cutoff_occured = false;
  
  if(goal(node)){
    return solution;
  }
  else if(limit == node.depth){
    return cutoff;
  }
  else{
    for(child in node.successors){
      res = dls(child, limit);
      
      if(res==cutoff){
        cutoff_occured = true;
      }
      else if(res!=failure){
        return solution;
      }
    }
  }
  if(cutoff_occured){
    return cutoff;
  }
  else{
    return failure;
  }
}

完全性:真解の深さがdの場合、d

time complexity : O(b^l)

space complexity : O(bl)

optimality : no

ids

dlsでlimitを0から1に増やす方法.

completeness : yes

time complexity : O(b^d)

space complexity : O(bd)

最適性:stepコストが一致するとyes

bidirection search

startとgoal stateから二人が会うまでの検索方法startから移動するのは簡単ですが、goal stateから後ろに移動するのは難しいです.したがって、変換モデルの反転が決定された場合にのみ使用できます.

completeness : yes

time complexity : O(b^(d/2))

space complexity : O(b^(d/2))

最適性:stepコストが一致する場合最適性