Solving problems by searching Chapter 3 14Jan2004 CS 3243-Blind Search 1
14 Jan 2004 CS 3243 - Blind Search 1 Solving problems by searching Chapter 3
Outline Problem-solving agents Problem types Problem formulation Example problems Basic search algorithms 14]an2004 CS 3243-Blind Search 2
14 Jan 2004 CS 3243 - Blind Search 2 Outline ◼ Problem-solving agents ◼ Problem types ◼ Problem formulation ◼ Example problems ◼ Basic search algorithms
Problem-solving agents function SIMPLE-PROBLEM-SOLVING-AGENT(percept)returns an action static:seg,an action sequence,initially empty state,some description of the current world state goal,a goal,initially null problem,a problem formulation stateUPDATE-STATE(state,percept) if seg is empty then do goal+FORMULATE-GOAL(state) problem+FORMULATE-PROBLEM(state,goal) seg+SEARCH(problem) action←-FIRST(seq) seq←REsT(seq return action 14]an2004 CS 3243 Blind Search 3
14 Jan 2004 CS 3243 - Blind Search 3 Problem-solving agents
Example:Romania On holiday in Romania;currently in Arad. Flight leaves tomorrow from Bucharest ■Formulate goal: ■be in Bucharest Formulate problem: states:various cities actions:drive between cities ■ ■Find solution: 14 Jan zosequence of cities,ceng3,AracarSibiu,Fagaras,Bucharest 4
14 Jan 2004 CS 3243 - Blind Search 4 Example: Romania ◼ On holiday in Romania; currently in Arad. ◼ Flight leaves tomorrow from Bucharest ◼ ◼ Formulate goal: ◼ be in Bucharest ◼ ◼ Formulate problem: ◼ states: various cities ◼ actions: drive between cities ◼ ◼ Find solution: ◼ sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest ◼
Example:Romania Oradea 71 Neamt Zerind ▣ 87 75 151 ▣si Arad 140 92 Sibiu 99 Fagaras 18 ▣ 80 白Vaslui Timisoara Rimnicu Vilcea 142 11 211 口Lugj Pitesti 97 70 98 Hirsova Mehadia 146 101 85 Orziceni 的 ■ 138 86 Bucharest Dobreta自 120 Craiova 90 Efo rie Giu rgiu 14]an2004 CS 3243 Blind Search 5
14 Jan 2004 CS 3243 - Blind Search 5 Example: Romania