Computer Science Canada Help neede regarding heuristic algorithms |
| Author: | A.J [ Wed Jan 30, 2008 1:47 pm ] |
| Post subject: | Help neede regarding heuristic algorithms |
I needed help regarding the A* algorithm and its implementation. I needed it to make a 8 puzzle solver for a game i am making. Although I sort of understand how the heuristic cost is calculated, i still need help since i heard that the 8 puzzle uses a hard to implement A* algorithm (and i could only find non-turing related implementation, and they are hard to read) |
|
| Author: | Skynet [ Wed Jan 30, 2008 2:55 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
The only thing that changes between different implementations of the A* algorithm is the heuristic. For A*, you have your current state, a list of possible next states, and a list of previously visited states. As I'm sure you're aware, you use the heuristic to determine which state to explore next. The A* heuristic is defined as f(x) = g(x) + h(x), where g(x) is the actual cost incurred to get to the current state and h(x) is the estimated cost from the current state to the goal. I'll use something a bit easier to visualize. If you are at a certain (x,y) location on a map, and you wish to get to another (x,y) location, you can only take discrete steps. You wish to get to your goal in the fewest steps. If you take one step, your state after taking that step with have a g(x) value which is higher than the g(x) value at your previous state by "one step". As well, you'll have a new estimate of h(x) from your new state. (Euclidean distance would be a good cost estimate) Each state you "visit" with have a different f(x) value, and you use this value to sort a list of states you've visited. If, when you get to a state, every possible move from that state involves a higher cost, those moves will be added low on the list and you will instead choose another move to make. Since you store what your origin state was when you arrive at a new state, you can backtrack all the way back to the start once you reach your goal. (and in backtracking, reconstruct the optimal path) Now, if you were writing a MapQuest-type navigation algorithm, your heuristics are very well defined. You know how far each state is from each other, and you can estimate how far each state is from the goal. For this puzzle solver, my uninformed suggestion would be to use the "amount of moves you've made up to this point" as g(x) and some sort of combination of how far each number is from their correct position as h(x). Can't help you with Turing - last time I looked at it was in 2003. |
|
| Author: | A.J [ Wed Jan 30, 2008 3:09 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
Thanks a lot skynet! by the way, are you at UW for Mechatronics? cause my brother's at UW Mechatronics too. His name is Abhilash Jayakumar (2nd year) I also need help in the coding in turing I attached a program I made in turing using (what I think) is the A* algorithm (And the test case it reads from). Please tell me if I am WAY off or not. thx |
|
| Author: | Skynet [ Wed Jan 30, 2008 11:15 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
Yep, I know Abhi. I can look at that code, but adding comments for what each section is supposed to do would be helpful. |
|
| Author: | Saad [ Thu Jan 31, 2008 12:15 am ] |
| Post subject: | RE:Help neede regarding heuristic algorithms |
That code like Skynet said could have comments to help. From the code it seems you have no Open List and Closed List which is an important part of A-Star. Also if you really need efficiency look into binary heaps or if your grid is really big I suggest using a sorted linked list. But to answer your original question, a 2D distance should do the job. |
|
| Author: | A.J [ Thu Jan 31, 2008 1:12 am ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
Sry guys, the previous version was sort of weird, since i forgot to attach the updated one. So, here it is (it is very poorly commented cause i have to go to bed (it is 1 A.M), so ask me questions if you're unsure of anything (I also attached a different test case, since the last one was impossible to solve) It will be really helpful if you could show me an example of the A* algorithm coded in turing. thanks again for helping me guys By the way, skynet, what's your real name? My brother wanted to know who you are and what year you are in. |
|
| Author: | Skynet [ Thu Jan 31, 2008 10:10 am ] | ||
| Post subject: | Re: Help neede regarding heuristic algorithms | ||
Regarding your "open" list - it's kept sorted according to increasing f(x), not as a LIFO. Also, something that I usually do with this sort of algorithm - create a section that lets you keep this code:
in one spot only, so you can edit as necessary. When I did this in Java, I created a function which looked at my state and returned a list of possibilities. Then it's just a matter of iterating over the list. When you're going to test this, try making the width of the maze wider then just one cell - it'll make determining if it's working or not easier. Tell Abhi that though I don't go to his Sunday meetings, I know plenty of people who do. |
|||
| Author: | A.J [ Thu Jan 31, 2008 11:40 am ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
how do you keep that code in one spot only? and g(n) (or the cost) in this case is merely the number of steps it takes to reach any particular node and g(n) cannot be determined before hand unless you already checked through every node once. (I am sort of a noob to turing, since i only started it a couple of months back, so i don't understand everything you just said there, but i do understand a bit of it  )
Thanks a lot skynet for helping albeit your university demands a lot of you.  |
|
| Author: | Skynet [ Fri Feb 01, 2008 6:42 pm ] | ||
| Post subject: | Re: Help neede regarding heuristic algorithms | ||
|
|||
| Author: | A.J [ Fri Feb 01, 2008 7:12 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
so what you're saying is that while visiting every node, sort it into a heap (or some sort of list) according to f(n) ? but how does that help (cause if you have already gone through all the nodes once, can't i just use BFS?) |
|
| Author: | A.J [ Mon Feb 04, 2008 1:46 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
If anyone has any examples of a heuristic algorithm in turing, could you please post it cause I am currently trying to solve the sliding puzzle with outputting every move in solving it. (It is not a school homework or anything. I am just doing it for fun) I tried searching everywhere on how to do it, and I could not find anything. |
|
| Author: | Skynet [ Mon Feb 04, 2008 3:35 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
A.J @ Fri Feb 01, 2008 7:12 pm wrote: so what you're saying is that while visiting every node, sort it into a heap (or some sort of list) according to f(n) ?
but how does that help (cause if you have already gone through all the nodes once, can't i just use BFS?) But you haven't gone through all of the nodes once, you've only examined the ones which "appear to be promising". You determine "appear to be promising" by f(n). This is also referred to as your open list. At the beginning, the open list has one node- your start state. If you can reach two other states from here, you'll add them both to the list, and sort the list by f(n). You then examine the best of the now-updated list. "Explore" the top state, look at the states you can reach from it, and add them all to the list. Repeat until the top state is the same as your goal state. The key thing here is the f(n) and the sorted list. The f(n) (your heuristic) guides your search, and you use the sorted list to efficiently order the best states to explore next. I'd like to provide some sort of visual example here, but school is somewhat busy at the moment. |
|
| Author: | A.J [ Mon Feb 04, 2008 7:16 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
thx skynet! I know that university can be demanding this time of year. I still have one question though. I understand that you sort according to f(n), but isn't f(n)=g(n)+h(n)? Calculating h(n) beforehand is not hard (just calculate the Manhattan distance from every point to the goal) but what is the g(n)? Is it merely the distance from the starting node to the node you are visiting, or is it 0 (in the case of a mazesolver like the one I posted)? Thanks for helping me out. You have been very helpful!  |
|
| Author: | Skynet [ Mon Feb 04, 2008 10:20 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
Quick g(n): g(current node) = g(previous node) + distance(previous node to current node) If you're using Manhattan distance, then that's your distance function. Euclidean is better if you're going to allow diagonal motion in your mazesolver. (won't get into why) |
|
| Author: | A.J [ Tue Feb 05, 2008 5:50 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
So, as visiting the neighbour nodes, I insert the nodes into a min heap (according to f(n), returning the best f(n) ) and I just follow the neighbour node with the best f(n). Is that basically what A* is? |
|
| Author: | Saad [ Tue Feb 05, 2008 7:12 pm ] |
| Post subject: | RE:Help neede regarding heuristic algorithms |
In essence yes, A-Star can basically be defined as the following instructions 1. Add your starting node to the open list 2. For each of your traversable node thats not on the closed list, compute f(n) for that node and set the parent of that node to our current square into the open list which is a sorted list (or Heap or what ever your using to store the f(n) values in order). Note: If your node was already in the open list then check too see if the g(n) cost is lower to go to that block, if it is replace that node's parent with the current one. 3. Travel to the node with the lowest f(n), Add the block you just traveled to into the closed list. 4. Repeat steps 2-4 until your at the Target 5. Track back to your starting node by visiting the parent of the nodes |
|
| Author: | A.J [ Sun Feb 10, 2008 5:23 pm ] |
| Post subject: | Re: Help neede regarding heuristic algorithms |
If anyone could code a program implementing the A* algorithm and post it, I'll be thankful (I get the algorithm, but I am still finding it kind of hard to code it) |
|