a* question

This is a discussion on a* question within the Game Programming forums, part of the General Programming Boards category; if i wanted to build a program that solves simple puzzles using a* search algorithm, do i need to consider ...

  1. #1
    Registered User skyline's Avatar
    Join Date
    Dec 2001
    Posts
    49

    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.

  2. #2
    Registered User
    Join Date
    Feb 2002
    Posts
    591
    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.

  3. #3
    Registered User skyline's Avatar
    Join Date
    Dec 2001
    Posts
    49
    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.

  4. #4
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    would you mind explaining to us what a* search is? Just how it works, theory behind it, or something?

  5. #5
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,738
    A* is a search algorithm most commonly used for pathfinding. In fact, it is very popular in pathfinding. That is what A* is.
    My Website

    "Circular logic is good because it is."

  6. #6
    Pursuing knowledge confuted's Avatar
    Join Date
    Jun 2002
    Posts
    1,916
    any hints on how it works?

  7. #7
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM
  5. Question, question!
    By oskilian in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 12-24-2001, 12:47 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21