Artificial Intelligence: A Modern Approach
Artificial Intelligence: A Modern Approach
3rd Edition
ISBN: 9780136042594
Author: Stuart Russell, Peter Norvig
Publisher: Prentice Hall
Question
Book Icon
Chapter 3, Problem 21E
Program Plan Intro

Breadth-first search:

  • Breadth First Search (BFS), is the algorithm that traverses or searches tree or graph data structures.
  • The search starts with the tree root, and then explores all the neighbor nodes at the present depth before moving to the nodes at the next depth level.
  • The strategy used in this is quite opposite to depth-first search.

Depth First Search:

  • Depth First Search (DFS), is the algorithm to traverse or search tree or graph data structures.
  • The search starts with the root node, and then explores as far as possible along each branch before backtracking.

Uniform Cost Search:

  • Uniform Cost Search (UCS) is the algorithm known to best for a search problem, and this does not include the use of heuristics.
  • It solves any general graph for an optimal cost.
  • Uniform cost search searches the branches which are more or less the same in cost.

Blurred answer
Students have asked these similar questions
Prove that Interpolation Search is better than Binary Search under certain conditions.
Which of the following statements are true ? Give reasons for your answers in the form of a short proof or a counter-example. (i) All comparison based sorting algorithms have the same worst case running time. (ii) A topological sort of a Directed Acyclic Graph (DAG) can be created by performing a depth-first-search on the DAG. (iii) o (p) = p\d primes p, where o is the Euler-phi function. (iv) There is a unique min binary heap on the set {1, 2, 9}. ..... (v) Two sequences can have several common subsequences of the length. same maximum
Exercise d. Coloring, with the oracle's help. (Textbook problem 4.2) Analogous to the previous problem, but a little trickier: suppose we have an oracle for the decision problem GRAPH k-COLORING. Show that by asking a polynomial number of questions, we can find a k-coloring if one exists. Hint: You want to iteratively compute a coloring, where partway through, some nodes have colors assigned already and others do not. You need to ask the oracle about a modified version of the original graph to learn if this partial coloring can be finished; if not, make a different choice when coloring the next node.
Knowledge Booster
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education