1CS 2710 Foundations of AICS 2710 Foundations of AILecture 3Milos [email protected] Sennott SquareUninformed search methodsCS 2710 Foundations of AIAnnouncements• Homework 1– Access through the course web pagehttp://www.cs.pitt.edu/~milos/courses/cs2710/– Two things to download:• Problem statement• C/C++ programs you will need for the assignment • Due date: September 14, 2005 before the lecture• Submission:– Reports: on the paper at the lecture– Programs: electronic submissionsSubmission guidelines:http://www.cs.pitt.edu/~milos/courses/cs2710/program-submissions.html2CS 2710 Foundations of AIFormulating a search problemMany challenging problems in practice require search• Search (process)– The process of exploration of the search space• Search space:– alternatives (objects) among which we search for the solution• The efficiency of the search depends on:– The search space and its size– Method used to explore (traverse) the search space– Condition to test the satisfaction of the search objective(what it takes to determine I found the desired goal object• Think twice before solving the problem by search:– Choose the search space and the exploration policyCS 2710 Foundations of AIProblem-solving as search• Many search problems can be converted to graph search problems• A graph search problem can be described in terms of:– A set of states representing different world situations – Initial state– Goal condition– Operators defining valid moves between states• Two types of search:– Path search: solution is a path to a goal state– Configuration search: solution is a state satisfying the goal condition • Optimal solution = a solution with the optimal value– shortest path between the two cities, or– a desired n-queen configuration3CS 2710 Foundations of AISearching for the solutionSearch: exploration of the state space through successive application of operators from the initial state and goal testingSearch tree: represents a trace of the search process and its exploration fringe, branches of the tree correspond to paths from the initial state that has been explored so farAradZerind Sibiu TimisoaraOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojCS 2710 Foundations of AISearch treeAradZerind Sibiu TimisoaraOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojA branch in the search tree= a path in the graph4CS 2710 Foundations of AIGeneral search algorithmGeneral-search (problem, strategy)initialize the search tree with the initial state of problemloop if there are no candidate states to explore return failurechoose a leaf node of the tree to expand next according to strategyif the node satisfies the goal condition return the solutionexpand the node and add all of its successors to the treeend loopCS 2710 Foundations of AIGeneral search algorithmGeneral-search (problem, strategy)initialize the search tree with the initial state of problemloop if there are no candidate states to explore return failurechoose a leaf node of the tree to expand next according to strategyif the node satisfies the goal condition return the solutionexpand the node and add all of its successors to the treeend loopAradZerind Sibiu TimisoaraOradea FagarasRimnicuVilceaArad OradeaArad Arad Lugoj5CS 2710 Foundations of AIGeneral search algorithm• Search methods differ in how they explore the space, that is how they choose the node to expand next !!!!!General-search (problem, strategy)initialize the search tree with the initial state of problemloop if there are no candidate states to explore return failurechoose a leaf node of the tree to expand next according to strategyif the node satisfies the goal condition return the solutionexpand the node and add all of its successors to the treeend loopCS 2710 Foundations of AIImplementation of search• Search methods can be implemented using the queue structure• Candidates are added to nodes representing the queue structureGeneral search (problem, Queuing-fn)nodes Make-queue(Make-node(Initial-state(problem)))loopif nodes is empty then return failurenode Remove-node(nodes)if Goal-test(problem) applied to State(node) is satisfied then return nodenodes Queuing-fn(nodes, Expand(node, Operators(node)))end loop←←←6CS 2710 Foundations of AIImplementation of the search tree structure•A search tree node is a data-structure constituting part of a search tree• Expand node function – applies Operators to the state represented by the search tree node. ST NodeStatestatechildrenparentOther attributes:- state value (cost)-depth- path cost CS 2710 Foundations of AIUninformed search methods• Many different ways to explore the state space (build a tree)Uninformed search methods: – use only information available in the problem definition• Breadth first search• Depth first search• Iterative deepening• Bi-directional searchFor the minimum cost path problem:• Uniform cost search7CS 2710 Foundations of AISearch methodsProperties of search methods :• Completeness.– Does the method find the solution if it exists? • Optimality.– Is the solution returned by the algorithm optimal? Does it give a minimum length path?• Space and time complexity.– How much time it takes to find the solution? – How much memory is needed to do this?CS 2710 Foundations of AIParameters to measure complexities.• Space and time complexity.– Complexities are measured in terms of parameters:• b – maximum branching factor• d – depth of the optimal solution• m – maximum depth of the state spaceBranching factorNumber ofoperators8CS 2710 Foundations of AIBreadth first search (BFS)• The shallowest node is expanded firstCS 2710 Foundations of AIBreadth-first search• Expand the shallowest node first• Implementation: put successors to the end of the queue (FIFO)AradAradqueueZerind SibiuTimisoaraOradea FagarasRimnicuVilceaArad OradeaArad Arad Lugoj9CS 2710 Foundations of AIBreadth-first searchAradZerind SibiuTimisoaraZerindSibiuTimisoaraqueueOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojCS 2710 Foundations of AIBreadth-first searchAradZerind SibiuTimisoaraOradeaAradSibiuTimisoaraAradOradeaqueueFagarasRimnicuVilceaOradeaArad Arad Lugoj10CS 2710 Foundations of AIBreadth-first searchAradZerind Sibiu TimisoaraOradea FagarasRimnicuVilceaArad OradeaAradTimisoaraAradOradeaAradOradeaFagarasRomnicu VilceaqueueArad LugojCS 2710 Foundations of AIBreadth-first searchAradZerind Sibiu