DOC PREVIEW
Pitt CS 2710 - Uninformed search methods

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Pitt CS 2710 - Uninformed search methods

Documents in this Course
Load more
Download Uninformed search methods
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Uninformed search methods and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Uninformed search methods 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?