in Education by
I quote from Artificial Intelligence: A Modern Approach: The properties of the depth-first search depend strongly on whether the graph-search or tree-search version is used. The graph-search version, which avoids repeated states and redundant paths, is complete in the finite state spaces because it will eventually expand every node. The tree-search version, on the other hand, is not complete [...]. Depth-first tree search can be modified at no extra memory cost so that it checks new states against those on the path from the root to the current node; this avoids infinite loops in the finite state spaces but does not avoid the proliferation of redundant paths. I don't understand how can graph-search be complete and tree-search be not, being a tree a particular graph. Besides, I don't clearly understand the difference between "infinite loops" and "redundant paths"... Can someone explain this to me? ps. For those who have the book, it's page 86 (3rd edition). Select the correct answer from above options

1 Answer

0 votes
by
 
Best answer
It depends on the search space. If the search space of your algorithm is finite, then Depth-First Search is complete. However, if there are infinitely many alternatives, it might not find a solution. For example, suppose you were coding a path-search problem on city streets, and every time your partial path came to an intersection, you always searched the left-most street first. Then you might just keep going around the same block indefinitely. Sometimes there are ways to bound the search to get completeness even when the search space is unbounded. For example, for the path-search problem above, if we prune the search whenever a path returns to a previous location on the path, then DFS will always find a solution if one exists. There are variants of DFS that are complete. One is iterative deepening: you set a maximum search depth for DFS, and the only search that far down the search tree. If you don’t find a solution, then you increase the bound and try again. (Note, however, that this method might run forever if there is no solution.) Now answering your second question, Basically, redundant links/paths are used to prevent nasty network failure. These are used to provide redundancy, i.e back up when a link fails, i.e a frame can be forwarded out through another path but it can cause problems also. Whereas an infinite loop (sometimes called an endless loop ) is a piece of coding that lacks a functional exit so that it repeats indefinitely. In computer programming, a loop is a sequence of instruction s that is continually repeated until a certain condition is reached. If you wish to know about Uninformed Search Algorithms and types of Uniformed Search Algorithms ( Breadth-first search, depth-first search, depth limited search, iterative deepening depth-first search, uniform cost search, bidirectional search ) then visit this Artificial Intelligence Course.

Related questions

0 votes
    I have a map stored as a multidimensional array ($map[row][col]) and I'd wish to create a path from ... path inside these values? Select the correct answer from above options...
asked Jan 30, 2022 in Education by JackTerrance
0 votes
    I'm trying to read an image from electrocardiography and detect each one of the main waves in it (P wave, QRS ... some ideas? Thanks! Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    In the MNIST beginner tutorial, there is the statement accuracy = tf.reduce_mean(tf.cast(correct_prediction, "float")) tf ... (x,1)? Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I know the basics of feedforward neural networks, and how to train them using the backpropagation algorithm, but I'm ... , even better. Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I am looking for an open source neural network library. So far, I have looked at FANN, WEKA, and OpenNN. Are the ... , and ease of use. Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    Suppose I have a Tensorflow tensor. How do I get the dimensions (shape) of the tensor as integer values? I ... 'Dimension' instead. Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I'm hoping to use either Haskell or OCaml on a new project because R is too slow. I need to be able to ... in either Haskell or OCaml? Select the correct answer from above options...
asked Feb 8, 2022 in Education by JackTerrance
0 votes
    I'm hoping to use either Haskell or OCaml on a new project because R is too slow. I need to be able to ... in either Haskell or OCaml? Select the correct answer from above options...
asked Feb 5, 2022 in Education by JackTerrance
0 votes
    The classifiers in machine learning packages like liblinear and nltk offer a method show_most_informative_features(), which ... lot! Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    What is the difference between informed and uninformed searches? Can you explain this with some examples? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    Like lots of you guys on SO, I often write in several languages. And when it comes to planning stuff, (or ... to this being possible? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    I'm looking for some examples of robot/AI programming using Lisp. Are there any good online examples available ... in nature)? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    I'm working through my AI textbook I got and I've come to the last homework problem for my section: "Implement the ... in C# or Java? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    It always amazed me how the Akinator app could guess a character by asking just several questions. So I wonder ... more about them? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
0 votes
    I am trying to implement an application that uses the AdaBoost algorithm. I know that AdaBoost uses a set of ... kind of algorithm? Select the correct answer from above options...
asked Feb 4, 2022 in Education by JackTerrance
...