People who code: we want your input. Take the Survey

# Tag Info

16

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search. However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an ...

8

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are: inserting elements testing if elements are already in there Pretty much every programming language should already have support for a data ...

8

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here: http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf A few key points: In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM....

3

Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems, that it resolves this issue for you. Consider that your BFS requires you to keep a stack of unprocessed states. As you progress into the puzzle, the states ...

3

The primary reason is that Breadth-First Search requires much more memory (and this probably also makes it a little bit slower in practice, due to time required to allocate memory, jumping around in memory rather than working with what's still in the CPU's caches, etc.). Breadth-First Search needs memory to remember "where it was" in all the different ...

2

Welcome to AI.SE @GundamOfOasis! Your intuition is right: this is fundamentally a problem for combinatorial search. You're also right that problems are created by the fact that not every move is valid at state. To fix this, you need to add a function that can determine whether a given state is valid or not, in addition to the usual function that checks ...

2

The only general situation that comes to my mind where BFS could be preferred over A* is when your graph is unweighted and the heuristic function is $h(n) = 0, \forall n \in V$. However, in that case, A* (which is equivalent to UCS) behaves like BFS (except for the goal test: see section 3.4.2 of this book), i.e. it will first expand nodes at level $l$, then ...

1

There is an inherent assumption in heuristic search that the heuristic function points you in the right direction. A* largely depends on how good the heuristic function is. Two nice properties for the heuristic function are for it to be admissible and consistent. If the latter stands, I can't think of any case where BFS would outperform A*. However, this ...

1

Approaches to the Game It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and endless looping when searching a graph that may contain graph cycles. However, those trivial facts are not pertinent if the goal is to complete the puzzle in the ...

1

In general, the process of modelling a problem as a search problem consists in creating a graph which contains nodes, which represent the possible states in your problem, and edges, which represent the relations between these states (that is, you will have an edge between nodes $A$ and $B$ if it is possible to go from state $A$ to state $B$, and vice-versa, ...

1

We use the LIFO queue, i.e. stack, for implementation of the depth-first search algorithm because depth-first search always expands the deepest node in the current frontier of the search tree. The search proceeds immediately to the deepest level of the search tree, where the nodes have no successors. As those nodes are expanded, they are dropped from the ...

1

According to this article Breadth First Search (BFS) searches breadth-wise in the problem space. Breadth-First search is like traversing a tree where each node is a state which may a be a potential candidate for solution. It expands nodes from the root of the tree and then generates one level of the tree at a time until a solution is found. It is very ...

1

This is well covered in the corresponding chapters of Russell & Norvig (Ch. 3 & 4). It also depends on the distinction between TREE-SEARCH and GRAPH-SEARCH. First, note that Breadth-first search also can't handle cost functions that vary between nodes! Breath-first search only cares about the number of moves needed to reach a state, not the total ...

Only top voted, non community-wiki answers of a minimum length are eligible