Thread: a* question

if i wanted to build a program that solves simple puzzles using a* search algorithm, do i need to consider avoiding repeated states when expanding frontier in state space? I ask this because obviously it would be important to avoid repeated states and take it into consideration when solving a problem using an uniformed-search method. but because a* uses information about the problem and tends to pick states to expand that are on the complete and optimal path to the goal, then maybe you do not need to worry about coding a mechanism to avoid repeated states using a* (i.e. a* will avoid the repeated states anyway)???

thanks for the help.

Can you please try to refrace your question. It didn't make sense to me. Try to explain it as if I was 7. What do you want to do. Do you have any code that can clearify what you try to do.

at this point i don't have any code, still in the design phase of things. i just wanted to ask a question about the a* search algorithm in general. actually i think i'm ok now. basically my end goal here is to build a program (problem-solving agent in particular) to be able to solve the "15 puzzle" using the ida* search algorithm (a kind of extension to a* that is supposed to conserve memory, which will give the ability to solve more complex problems). but before diving into such a program i wanted to start out with something simpler first, just to get a idea of the task at hand. so right now i'm working on a problem-solving agent that will just solve the "8 puzzle" using a* search, given some random initial state.

i.e.

the agent will go from solving:

4 7 8
2 6 _
1 5 3

to

1 2 3
4 5 6
7 8 _

(you know this game right? moving puzzle blocks around in order
to reach some state that is the goal.)

but in the end i would like to implement such an agent to solve the 15 puzzle, something like:

14 10 7 9
1 5 2 6
3 8 12 11
13 4 15 _

but doing this with regular old a* will exhaust the memory in your computer and the program will have to be killed.

but back to the original question, i wanted to know if it was important for me to implement a mechanism to avoid repeated states when expanding the frontier. in an uninformed search method this would be crucial to do; but maybe not with a*?

but none the less i'm going to check for repeated states but not in a really computationally expensive way as to search the entire tree of expanded states for existing states. i'm implementing the frontier as a priority queue that is organized using the cost function for a*. when i expand new states from a given state, then i will have to add them to this queue. i will search the queue ONLY for existing/repeated states. in fact i'm only keeping the frontier of states in memory, and not all states that have been expanded thus far (you could imagine all expanded states as a tree of states, and frontier as all the leaves; i will be removing all states that came before the frontier (all parents, grandparents etc.. of the leaves) from memory. this will save a lot of memory.

i think/hope this will work.

anyone implement a program like this before? let me know of some potholes to avoid.

Thanks.

would you mind explaining to us what a* search is? Just how it works, theory behind it, or something?

any hints on how it works?