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, 2004 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 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 search3CS 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 ofoperators4CS 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 Lugoj5CS 2710 Foundations of AIBreadth-first searchAradZerind SibiuTimisoaraZerindSibiuTimisoaraqueueOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojCS 2710 Foundations of AIBreadth-first searchAradZerind SibiuTimisoaraOradeaAradSibiuTimisoaraAradOradeaqueueFagarasRimnicuVilceaOradeaArad Arad Lugoj6CS 2710 Foundations of AIBreadth-first searchAradZerind Sibiu TimisoaraOradea FagarasRimnicuVilceaArad OradeaAradTimisoaraAradOradeaAradOradeaFagarasRomnicu VilceaqueueArad LugojCS 2710 Foundations of AIBreadth-first searchAradZerind Sibiu TimisoaraOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojAradOradeaAradOradeaFagarasRomnicu VilceaAradLugojqueue7CS 2710 Foundations of AIProperties of breadth-first search• Completeness: ?• Optimality: ?• Time complexity: ?• Memory (space) complexity: ?– For complexities use:• b – maximum branching factor• d – depth of the optimal solution• m – maximum depth of the search treeCS 2710 Foundations of AIProperties of breadth-first search• Completeness: Yes. The solution is reached if it exists.• Optimality: Yes, for the shortest path.• Time complexity: ?• Memory (space) complexity: ?8CS 2710 Foundations of AIBFS – time complexitybddepth number of nodes01121=223d22=423=82d(bd)Total nodes:)(1+dbOd+12d+1(bd+1)Expanded nodes:)(dbOCS 2710 Foundations of AIProperties of breadth-first search• Completeness: Yes. The solution is reached if it exists.•Optimality: Yes, for the shortest path.•Time complexity:exponential in the depth of the solution d• Memory (space) complexity: ?)(12 ddbObbb =++++ K9CS 2710 Foundations of AIBFS – memory complexitybddepth number of nodes01121=223d22=423=82d(bd)Total nodes:)(1+dbOd+12d+1(bd+1)Expanded nodes:)(dbO• Count nodes kept in the tree structure or in the queueCS 2710 Foundations of AIProperties of breadth-first search• Completeness: Yes. The solution is reached if it exists.•Optimality: Yes, for the shortest path.•Time complexity:exponential in the depth of the solution d• Memory (space) complexity:nodes are kept in the memory)(12 ddbObbb =++++ K)(dbO10CS 2710 Foundations of AIDepth-first search (DFS)• The deepest node is expanded first• Backtrack when the path cannot be further expandedCS 2710 Foundations of AIDepth-first search• The deepest node is expanded first• Implementation: put successors to the beginning of the queueAradAradqueueZerind SibiuTimisoaraOradea FagarasRimnicuVilceaArad OradeaArad Arad Lugoj11CS 2710 Foundations of AIDepth-first searchAradZerind SibiuTimisoaraZerindSibiuTimisoaraqueueOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojCS 2710 Foundations of AIDepth-first searchAradZerindSibiu TimisoaraOradeaAradOradeaSibiuTimisoaraqueueFagarasRimnicuVilceaArad OradeaArad Arad Lugoj12CS 2710 Foundations of AIDepth-first searchAradZerindSibiu TimisoaraSibiu TimisoaraZerindNote: Arad – Zerind – Arad cycleZerindSibiuTimisoaraOradeaSibiuTimisoaraqueueOradea FagarasRimnicuVilceaArad OradeaArad Arad LugojCS 2710 Foundations of AIProperties of depth-first search• Completeness: Does it always find the solution if it exists?• Optimality: ?• Time complexity: ?• Memory (space) complexity: ?13CS 2710 Foundations of AIProperties of depth-first search• Completeness: No. Infinite loops can occur. Infinite loops imply -> Infinite depth search tree. •Optimality: does it find the minimum length path ?• Time complexity: ?• Memory (space) complexity: ? CS 2710 Foundations of AIProperties of depth-first search• Completeness: No. Infinite loops can occur. •Optimality: No. Solution found first may not be the shortest possible.•Time complexity: ?• Memory (space) complexity: ?14CS 2710 Foundations of AIProperties of depth-first search• Completeness: No. Infinite loops can occur. •Optimality: No. Solution found first may not be the shortest possible.•Time complexity: ?• Memory (space) complexity: ? CS 2710 Foundations
View Full Document