AI - Ch1 問題求解與搜尋 Problem Solving and Search

人工智慧名詞解釋

智慧代理 (intelligent agent)
智慧代理是一個可以針對環境的改變做出適當的動作及回應以達致目標的系統。

有限理性 (bounded rationality)
有限理性認為人類的認知受到記憶能力的限制，在決策時追求的不是最佳，而是滿意(satisfice)。

強人工智慧和弱人工智慧
強人工智慧觀點認為有可能製造出真正能推理和解決問題的智慧機器，並且，這樣的機器能將被認為是有知覺的，有自我意識的。
弱人工智慧觀點認為不可能製造出能真正地推理和解決問題的智慧機器，這些機器只不過看起來像是智慧的，但是並不真正擁有智慧，也不會有自主意識。



Problem Solving by Search
An important aspect of intelligence is goal-based problem solving. The solution of many problems (e.g. noughts and crosses, timetabling, chess) can be described by finding a sequence of actions that lead to a desirable goal. Each action changes the state and the aim is to find the sequence of actions and states that lead from the initial (start) state to a final (goal) state.



搜尋問題的正式定義

• 狀態集合 : S
• 操作 : O::S ‐> S
• 初始狀態 : s0
• 目標測試 : S ‐> {T,F}
• 路徑花費 : {S,O}* ‐> R

More Definitions for search

• Expand Node  : Generate children by applying operators.
• Branching Factor : number of possible operatorsor children at each node.
• Average BF : average BF of all nodes but leaves.
• Fringe or Frontier : nodes waiting to be expanded.

General Search Algorithm

NODES <‐ InitialState
LOOP DO
IF NODES is empty THEN RETURN failure.
Node <‐ Get a node from NODES
IF GoalTest(Node) THEN RETURN Node.
NODESMerge( ExpandNode(Node), NODES )
END DO

How we Get and Merge the nodes defines the type of search, and affects the search performance.



State Space and a Search Tree

• A State Space and a Search Tree are different
• State Space : represents all states and operators for the problem
• Search Tree : what an algorithm constructs as it solves a search problem

Search Issues

• Quality of the result
• 完備性 (Completeness) : 若有解存在，是否一定找的到
• 最佳性 (optimality) : 是否總是能找到最佳解(最低成本)
• 複雜度 (Complexity) 
• 時間複雜度(time complexity) – 總共擴展(生成)多少搜尋樹的節點
• 空間複雜度(space complexity) – 在搜尋時，總共有多少的節點儲存在記憶體中
• Search Control or Strategy
• Which node to get next for expansion?
• Avoid loops?
• Avoid expanding the same node twice? ...