Isn't he just explaining a greedy search without backtracking?
Also, this algorithm seems to go wrong even on the small map:
##^^^
~~#~.
**.#.
^..*~
~~*~X
##^^^
~~#~.
**.##
^..*~
~~*~X
On 10/13/06, Jacob Fugal <lukfugl@gmail.com> wrote:
Actually, the basic algorithm he explained isn't quite A-star (I'm
guessing on purpose). There's lots of room for improvement in both
algorithm and heuristic. I'm guessing that's where the fun and variety
of this quiz will be.Jacob Fugal
I wrote:
Well, A* is a _dreadful_ algorithm for route finding, so there's plenty
of scope for finding a way better approachField Guidance, Ho!
If no one minds too much, I'd like to reject what I said about 20
minutes ago about A*. I said it from an uninformed position.
It sounds like it's more of a general search algorithm for finiding
optimal paths. It may be applied to route finding, but can be used for
other search problems. The huristic (in the quiz, the Manhaton distance
is suggested) is very important and has a great impact on its
performance (it can also break the algorithm if it over estimates cost).
It's discussed on wonderful wikipedia:
http://en.wikipedia.org/wiki/A-star_search_algorithm
Field guidance is also a wonderful approach, and can give much more
"human" route planning. It's also great for allowing incomplete
knowledge to be handled, and it's nice at doing things like having a
unit of troops march in formation, but gracefully avoiding tree stumps,
and breaking formation near a wall, etc.
Cheers,
Benjohn
The problem of my *1 version is how the choice among tiles with the
same price is done. The *2 is really rubbish and was just based on a
specific map, sorry.
to have a better view of what happens is interesting to print out all
the costs of the points on the map, here's a diff to avoid the *2 and
print the final result with cost.
59c59
< (point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max
On 16/10/06, Daniel Martin <martin@snowplow.org> wrote:
"Paolo Negri" <hungrylist@gmail.com> writes:
> Here's my solution, first submission to ruby quiz, I hope is not 100%
> rubbish. I use a * 2 calculating the distance to avoid some noisy
> movements when approaching the ending point (so when the simple cost
> of terrain is about the same dimension of the distance).
> You can try the small map of the quiz without the *2 to see this
> behaviour. When the distance from the end point is >> than the terrain
> costs the *1 and *2 version act more or less the same way
> whell, here's the code.
>
> http://pastie.caboo.se/17815Unfortunately, the A* algorithm depends on the fact that the estimate
of cost being added to each point (in this case, distance to goal) is
always less than or equal to the actual cost of getting to the goal
from that point.By doubling the distance you violate this constraint, and so your
solution computes the wrong path given this map:@..*...
...~...
...~~~*
.....^XYour solution with the *2 in it does this:
####...
...~##.
...~~~#
.....^XFor a total cost of 10 (counting both the start and goal, and going
over two forests)Your solution with the *2 bit removed gets closer to the correct path,
but there's still something off:###*...
..#~...
..#~~~*
...###XLooking over your solution, I think you've fallen victim to the fact
that the quiz author failed to explain A* clearly. The excellent
online tutorials and wikipedia article already cited here on the list
are a better introduction.On the plus side, yours is the only solution besides mine posted so
far that manages to get this path right:@.*..
..~..
..^.XThat's because you wisely didn't use the manhattan distance quoted in
the puzzle statement.--
s=%q( Daniel Martin -- martin@snowplow.org
puts "s=%q(#{s})",s.map{|i|i}[1] )
puts "s=%q(#{s})",s.map{|i|i}[1]
---
(point1.zip(point2).map {|c| (c[0] - c[1]).abs}).max*2
103d102
< (0..(line.size - 1)).each {|n| out << cost([n, line_n]).to_s}
If I'll have the time to work on it I'll submit some improvements.
Thanks
Paolo
Pretty much, yes. Hoping it's not a spoiler, here's how you really do A*:
1) use a priority queue (prioritized by estimated cost)
2) initialize the queue with the start state(s)
3) while the queue is not empty
a) shift the head off the queue (cheapest state found so far)
b) return the path to the current state if the state is a goal state
b) expand that state by finding neighbors and calculating their costs
c) push each neighbor onto the queue
4) if the queue emptied without finding a solution, there is no solution
For the sake of both brevity and challenge, I've left some details out, such as:
* How do you prevent cycles and backtracking?
* How do you calculate costs for a new state?
* How do you manage your priority queue?
* How do you keep track of the path so you can return it when you hit a goal?
Happy hacking!
On 10/13/06, Sander Land <sander.land@gmail.com> wrote:
On 10/13/06, Jacob Fugal <lukfugl@gmail.com> wrote:
> Actually, the basic algorithm he explained isn't quite A-star (I'm
> guessing on purpose). There's lots of room for improvement in both
> algorithm and heuristic. I'm guessing that's where the fun and variety
> of this quiz will be.
>
> Jacob FugalIsn't he just explaining a greedy search without backtracking?
Also, this algorithm seems to go wrong even on the small map:
The priority queue is the major aspect not really touched on by the quiz, yes. If you need help with this, a past Ruby Quiz about heaps had code you could borrow:
http://www.rubyquiz.com/quiz40.html
Just be sure to read the summary where I fix a couple of bugs in the code.
James Edward Gray II
On Oct 13, 2006, at 11:15 AM, Jacob Fugal wrote:
Hoping it's not a spoiler, here's how you really do A*:
1) use a priority queue (prioritized by estimated cost)
2) initialize the queue with the start state(s)
3) while the queue is not empty
a) shift the head off the queue (cheapest state found so far)
b) return the path to the current state if the state is a goal state
b) expand that state by finding neighbors and calculating their costs
c) push each neighbor onto the queue
4) if the queue emptied without finding a solution, there is no solution
James Edward Gray II wrote:
> Hoping it's not a spoiler, here's how you really do A*:
>
> 1) use a priority queue (prioritized by estimated cost)
> 2) initialize the queue with the start state(s)
> 3) while the queue is not empty
> a) shift the head off the queue (cheapest state found so far)
> b) return the path to the current state if the state is a goal state
> b) expand that state by finding neighbors and calculating their
> costs
> c) push each neighbor onto the queue
> 4) if the queue emptied without finding a solution, there is no
> solutionThe priority queue is the major aspect not really touched on by the
quiz, yes. If you need help with this, a past Ruby Quiz about heaps
had code you could borrow:Ruby Quiz - Drawing Trees (#40)
Just be sure to read the summary where I fix a couple of bugs in the
code.James Edward Gray II
My solution for last week's quiz used an A* search with a priority
queue if anybody wants to see some live code. The queue was, however,
designed for adding large numbers of new states in batches and would
need to be adapted.
By complete coincidence I've actually attempted something almost
identical to this before, attempting top move from any cell on the left
side to any cell on the right. I found that for larger grids an A*
search cell-by-cell becomes unacceptably slow.
I think the real challenge in this quiz will be forming intelligent
methods of reducing the number of states that must be searched. I never
actually did this for the left-to-right problem but have several ideas
for this quiz. Don't worry, they haven't given us the answers to the
real problems
On Oct 13, 2006, at 11:15 AM, Jacob Fugal wrote: