Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualCuriosityKills

Posted 15 November 2012 - 10:58 AM

Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?


BFS deals with planning, and so is very much AI, even in the general sense. Posted Image

With BFS you're going to have to store at the very least the parent of each state you consider in your search. If BFS is too memory-intensive for your application, consider DFS with iterative deepening. Like BFS, this is an uninformed search that also finds the optimal path on an unweighted graph. If implemented with a stack, you would only need to remember a very few states, but that algorithm does require a bit more processor time than BFS. That's often the trade-off when you optimize for low memory usage.

(Note: If you're ascribing different weights to different steps via an influence map, you're not actually implementing a BFS.)

#7CuriosityKills

Posted 15 November 2012 - 10:58 AM

Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?


BFS deals with planning, and so is very much AI, even in the general sense. Posted Image

With BFS you're going to have to store at the very least the parent of each state you consider in your search. If BFS is too memory-intensive for your application, consider DFS with iterative deepening. Like BFS, this is an uninformed search that also finds the optimal path on an unweighted graph. If implemented with a stack, you would only need to remember a very few states, but that algorithm does require a bit more processor time than BFS. That's often the trade-off when you optimize for low memory usage.

(Note: If you're ascribing different weights to different steps via an influence map, you are not actually implementing a BFS.)

#6CuriosityKills

Posted 15 November 2012 - 10:52 AM

Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?


BFS deals with planning, and so is very much AI, even in the general sense. Posted Image

With BFS you're going to have to store at the very least the parent of each state you consider in your search. If BFS is too memory-intensive for your application, consider DFS with iterative deepening. Like BFS, this is an uninformed search that also finds the optimal path on an unweighted graph. If implemented with a stack, you would only need to remember a very few states, but that algorithm does require a bit more processor time than BFS. That's often the trade-off when you optimize for low memory usage.

#5CuriosityKills

Posted 15 November 2012 - 10:52 AM

Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?


BFS deals with planning, and so is very much AI, even in the general sense. Posted Image

With BFS you're going to have to store at the very least the parent of each state you consider in your search. If BFS is too memory-intensive for your application, consider DFS with iterative deepening. Like BFS, this is an uninformed search that also finds the optimal path on an unweighted graph. If implemented with a stack, you would only need to remember a very few states, but that algorithm does require a bit more processor time than BFS. There's often a trade-off when you optimize a single attribute!

#4CuriosityKills

Posted 15 November 2012 - 10:51 AM

Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?


BFS deals with planning, and so is very much AI, even in the general sense. Posted Image

With BFS you're going to have to store at the very least the parent of each state you consider in your search. If BFS is too memory-intensive for your application, consider DFS with iterative deepening. Like BFS, this is an uninformed search that also finds the optimal path on an unweighted graph. If implemented with a stack, you would only need to remember a very few states, but that algorithm does require a bit more processor time than BFS. There's almost always a trade-off with optimizations!

#3CuriosityKills

Posted 15 November 2012 - 10:51 AM

Second, its a question about BFS (not much an AI topic itself), theres any way to keep track of the steps without storing it in each node added to the open list, but on the algorithm itself?


BFS deals with planning, and so is very much AI, even in the general sense. Posted Image

With BFS you're going to have to store at the very least the parent of each state you consider in your search. If BFS is too memory-intensive for your application, consider DFS with iterative deepening. Like BFS, this is an uninformed search that also finds the optimal path on an unweighted graph. If implemented with a stack, you would only need to remember a very few states, but that algorithm does require a bit more processor time than BFS. There's always a trade-off!

PARTNERS