清大松山机场.ppt

假設我們要到澎湖玩 由松山機場搭機前往 如何由清大到松山機場? 清大 ? 松山機場 How Did We Derive the Solution? Problem solving as state space search What is “state”? States: location of you Transitions: transportation (客運、高鐵、台鐵、捷運、公車、計程車、走路) Consider a More Complex Problem Consider the problem: Astronaut carries Grain, Goose, Fox across river Astronaut + 1 item allowed in the boat Goose alone eats Grain Fox alone eats Goose Problem Solving as State Space Search Goal: Astronaut, Fox, Goose and Grain across river Problem representation: States: location of Astronaut, Fox, Goose and Grain at top or bottom river bank Operators: move boat with astronaut and 1 or 0 items to other bank Generate solution: Sequence of states: Move(goose,astronaut), Move(astronaut), . . . Representing the Problem The problem space consists of: A state space which is a set of states representing the possible configurations of the world A set of operators which can change one state into another Initiate state and goal state Path: sequence of states produced by the valid application of operators from an old state to a new state The problem space can be viewed as a graph where the states are the nodes and the arcs represent the operators The 8-Puzzle Problem Operator: “move blank” State Space of 8-Puzzle 目前為止我們只到一個解答 但做為資工系的學生，我們不但要知道一個解答，我們更想知道一個更好的解答，甚至 最佳解 (optimal solution) 例如：sorting Bubble sort, selection sort, insertion sort, merge sort, heapsort, quicksort, ... 問題是... 何謂「最佳」? 時間最短 記憶體用最少 最便宜 耗電最低 最環保 最容易使用 最漂亮 還有更複雜的目標 ... 又快又便宜 功能又強又省電 如何計算目標值? 時間： 其他方法： 步數、運算數 如何計算目標值? 成本： 其他方法： 元件成本、售價 如何計算目標值? 路上風景最好： 常用方法：專家評分、民意調查 Cost-directed Problem Solving In many search problem, we are interested not only in reaching a goal state, but also in reaching it with the lowest cost (or the maximum profit) We can compute a cost as we apply operators and transit from state to state Traveling Salesperson Problem State Space of TSP Nearest Neighbor Path Finding Solutions Some problems have only one solution