hello,
i am interested in learning the exhaustive BFS algorithm. using this algorithm some one has solved the "the game " problem.
So, please help me by providing useful resourses.
thanks.
Provide resource for exhaustive BFS algorithm
Moderator: Board moderators
Provide resource for exhaustive BFS algorithm
by
S M Shahed Nejhum
S M Shahed Nejhum
BFS
breadth first search(algorithm)
Definition: A search algorithm which considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. This is typically implemented with a queue
Get the idea?
More information at http://www.nist.gov/dads/HTML/breadthfirst.html
Definition: A search algorithm which considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. This is typically implemented with a queue
Get the idea?
More information at http://www.nist.gov/dads/HTML/breadthfirst.html
wieghted graph?:: I don't understand yuor question.
wieghted graph?:: I don't understand yuor question.
Here is something:
queue is first in, first out while
stack is first in, last out.
Generally, you make use of a queue to do bfs.
[cpp]
queue q;
q.push(INITIAL_STATE);
while (q.size()) {
STATE x=q.front(); q.pop();
process(x);
}[/cpp]
The function process must produce more states. We must ensure that states are not repeated and that varies from problem to problem. States must also be stored efficiently. That is also dependent on the problem.
BFS is usually used for maze problems like acm 429, 652.
Here is something:
queue is first in, first out while
stack is first in, last out.
Generally, you make use of a queue to do bfs.
[cpp]
queue q;
q.push(INITIAL_STATE);
while (q.size()) {
STATE x=q.front(); q.pop();
process(x);
}[/cpp]
The function process must produce more states. We must ensure that states are not repeated and that varies from problem to problem. States must also be stored efficiently. That is also dependent on the problem.
BFS is usually used for maze problems like acm 429, 652.
Yes, the BFS can be used to find the shortest path in a weight graph. However, if the graph contains no negative edges, it is probably easier and more efficient to consider using FloydWarshall.
BFS on a weight graph is basically.
Start at a vertex.
Are any of the vertices connected to this one the target vertex, if so, is the distance traveled less than the minimum distance?
Run BFS with each of the connected vertices as the starting vertex.
But, heed my advice, FloydWarshall is better.
BFS on a weight graph is basically.
Start at a vertex.
Are any of the vertices connected to this one the target vertex, if so, is the distance traveled less than the minimum distance?
Run BFS with each of the connected vertices as the starting vertex.
But, heed my advice, FloydWarshall is better.

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
Floyd vs. BFS
I do agree that Floyd is easier to implement than BFS, but the n^3 running time really makes it unsuitable in some occasions. For example, try solving 532 using floyd...you get my point.
By the way, I thought only Dijkstra cannot work with negative edges? Floyd cannot work too? I'm really not sure
[/i]
By the way, I thought only Dijkstra cannot work with negative edges? Floyd cannot work too? I'm really not sure
[/i]
DISCUSSION ON EXHAUSTIVE B.F.S.
Hi, I need to learn 'exhaustive bfs', any discussion on this topic will a great help... can you provide me with some good links? If the basic idea is presented with some pseudocode, I hope to fill the rest