A* Algorithm 
Author Message
 A* Algorithm

Hello.

I'm really new to Prolog, and in my AI class we've suddenly been given
an assignment to write some puzzles using an A* algorithm for solving
them. This project is the only Prolog we have, and it won't be on the
exam, so I am not willing to use my short supply of cash to purchase a
Prolog book. What I really need is some examples of A* algorithms used
in puzzles (or any other similar programs), but the important thing is I
need the code  to be thoroughly commented (so that a newbie would
understand what's going on).

If anyone have something like this lying around, or could explain it
here, or have links to web-pages where this is thoroughly explained, I
would be eternally thankful!

Thanks,



Sun, 09 May 2004 18:31:53 GMT  
 A* Algorithm
G'day all.

Quote:

>I'm really new to Prolog, and in my AI class we've suddenly been given
>an assignment to write some puzzles using an A* algorithm for solving
>them.

FWIW...

http://groups.google.com/groups?selm=70c7ac%2432i%241%40mulga.cs.mu.O...

Cheers,
Andrew Bromage



Sun, 09 May 2004 19:07:19 GMT  
 A* Algorithm

Thanks for the help. Now I just need a week to figure out what it does. that
leaves 1 day for implementing something :)

Quote:

> G'day all.


> >I'm really new to Prolog, and in my AI class we've suddenly been given
> >an assignment to write some puzzles using an A* algorithm for solving
> >them.

> FWIW...

> http://groups.google.com/groups?selm=70c7ac%2432i%241%40mulga.cs.mu.O...

> Cheers,
> Andrew Bromage



Sun, 09 May 2004 21:55:16 GMT  
 A* Algorithm

Quote:

> Thanks for the help. Now I just need a week to figure out what it does.
that
> leaves 1 day for implementing something :)


> > G'day all.


> > >I'm really new to Prolog, and in my AI class we've suddenly been given
> > >an assignment to write some puzzles using an A* algorithm for solving
> > >them.

> > FWIW...

http://groups.google.com/groups?selm=70c7ac%2432i%241%40mulga.cs.mu.O...

Quote:

> > Cheers,
> > Andrew Bromage

See http://www.geocities.com/jheyesjones/astar.html

Daniel



Mon, 10 May 2004 05:07:26 GMT  
 A* Algorithm


Quote:
> Hello.

> I'm really new to Prolog, and in my AI class we've suddenly been given
> an assignment to write some puzzles using an A* algorithm for solving
> them. This project is the only Prolog we have...

This sounds unfair to me.

From what I remember of A*, it is not simple, and it must be
very difficult for any beginner in Prolog to code it in Prolog!

So don't be surprised if you can't do it,
this sounds like a hard assignment.

--
Martin Sondergaard,
London.



Mon, 10 May 2004 06:22:05 GMT  
 A* Algorithm
You are right, it is better to program yourself, given the
fact that you
understand how the algorithm works.

An author to check : Yoav Soham.

Quote:



> > Hello.

> > I'm really new to Prolog, and in my AI class we've
suddenly been given
> > an assignment to write some puzzles using an A*

algorithm for solving
Quote:
> > them. This project is the only Prolog we have...

> This sounds unfair to me.

> From what I remember of A*, it is not simple, and it must
be
> very difficult for any beginner in Prolog to code it in
Prolog!

> So don't be surprised if you can't do it,
> this sounds like a hard assignment.

> --
> Martin Sondergaard,
> London.



Mon, 10 May 2004 16:38:26 GMT  
 A* Algorithm
G'day all.

Quote:

>From what I remember of A*, it is not simple, and it must be
>very difficult for any beginner in Prolog to code it in Prolog!

It's straightforward if you understand how it works, and you
already have a priority queue implementation.  (A set implementation
also helps, but since only insertion and membership testing are
required, it's fairly easy to code an inefficient list-based one
yourself.)

So for some _real_ advice, I suggest starting by implementing a
priority queue.  It can be an inefficient one (e.g. using a list
and just inserting items using the standard linear-time algorithm),
but do it first.

BTW, my original post was made in the time-honoured comp.lang.prolog
tradition of answering homework requests with responses which are both
perfectly correct answers to the poster's question while also being
mostly useless.  Or has that gone out of fashion?

Cheers,
Andrew Bromage



Mon, 10 May 2004 22:46:13 GMT  
 A* Algorithm

Quote:

> BTW, my original post was made in the time-honoured comp.lang.prolog
> tradition of answering homework requests with responses which are both
> perfectly correct answers to the poster's question while also being
> mostly useless.  Or has that gone out of fashion?

It hasn't but only masters like you practice the art so skilfully !

Bart Demoen



Tue, 11 May 2004 20:15:09 GMT  
 A* Algorithm
I understand this principle of not overly helping others when it comes to
school projects and the like, but sometimes you feel totally helpless. (like
in this case).

Like I explained before, I've just started tampering with
Prolog, and even though everything you guys tell me here makes sense, The
entire A* algorithm written in Prolog looks like nothing more than weird
symbols placed in an 'orderly' fashion ,to me :)

I've seen code of generalized A* algorithms that are supposed to work for
'all' related problems. but my problem is fitting this algorithm into the
context of my program, and even worse ... adding my personal heurestic to
it.

Quote:
> It's straightforward if you understand how it works, and
>you  already have a priority queue implementation.  (A
>set implementation also helps, but since only insertion
>and membership testing are  required, it's fairly easy to
>code an inefficient list-based one  yourself.)
> So for some _real_ advice, I suggest starting by
>implementing a priority queue.  It can be an inefficient
>one (e.g. using a list and just inserting items using the
>standard linear-time algorithm),
> but do it first.

To the above. This is probably valuable information to someone who is
comfortable with Prolog already, but for someone like me, its just like:
Thats straightforward, just write Hello in chinese.

What I think I need help with is not an explanation of how the A* works,
because I know its theories. I just cannot put those theories into Prolog.
So if anyone could do their best to explain to me  what the algorithm does
(line for line would be excellent), I'd be very grateful. Also perhaps try
your best to explain how I fit it in with my program, and where in this
jungle which is my code, i add my additional heurestic.

Long note, and I ask alot, I know,
but I need to understand this much much faster than I would want to.

Regards,
Terje B.O



Wed, 12 May 2004 08:08:08 GMT  
 A* Algorithm

Quote:



>> Hello.
>> I'm really new to Prolog, and in my AI class we've suddenly been given
>> an assignment to write some puzzles using an A* algorithm for solving
>> them. This project is the only Prolog we have...
> This sounds unfair to me.
> From what I remember of A*, it is not simple, and it must be
> very difficult for any beginner in Prolog to code it in Prolog!

See Yoav Shoham, 1994, _Artificial Intelligence Techniques in Prolog_,
Morgan Kaufmann Publishers.

Relevant info is on pp38-39; the whole first part of the book is
about search strategies in Prolog. You'd probably want to look at
the immediately preceding section on best-first search. It doesn't
look all that hard, though I haven't compared Justin's A* tutorial
code to see which is more complex.

John C. Paolillo
SLIS and Informatics
Indiana University



Mon, 10 May 2004 07:20:18 GMT  
 A* Algorithm

Quote:

> I understand this principle of not overly helping others when it comes to
> school projects and the like, but sometimes you feel totally helpless. (like
> in this case).
[snip]
> What I think I need help with is not an explanation of how the A* works,
> because I know its theories. I just cannot put those theories into Prolog.
> So if anyone could do their best to explain to me  what the algorithm does
> (line for line would be excellent), I'd be very grateful. Also perhaps try
> your best to explain how I fit it in with my program, and where in this
> jungle which is my code, i add my additional heurestic.

Let me remind you that I wrote, in a previous follow-up:

Quote:
>See Yoav Shoham, 1994, _Artificial Intelligence Techniques in Prolog_,
>Morgan Kaufmann Publishers.
>Relevant info is on pp38-39; the whole first part of the book is
>about search strategies in Prolog. You'd probably want to look at
>the immediately preceding section on best-first search.

At most, to get through this part of the book, you'd have to read
40 pages. It's written very accessibly, with lots of code, and plenty
of prose explanation of the code. I was a beginner in Prolog when I
picked it up, and I highly recommend it.

Hope that helps,

John Paolillo
SLIS and Informatics
Indiana University



Wed, 12 May 2004 22:00:57 GMT  
 A* Algorithm
I've borrowed the last 3 books they had related to Prolog and AI from the
library.

The Art of Prolog: Advanced programming
Prolog programming and Applications
Artificial Intelligence through Prolog

I've found the A* algorithm there, with half a page explaining what it does.
But as soon as the book notes: % user-defined, they lose me :/
Remember, the biggest thing I've written before this project are things like
append and concatenate...  I'm in my 3rd or 4th week of Prolog now, and in
one week, I will never touch it again (I swear to LISP, just being forced to
write the project in Prolog), so my motivation for buying expensive books is
not present.

I guess I'm just asking for a helping hand to pass this project, because I
understand what the algorithm does, I just dont understand 2 pages of Prolog
Syntax, and I doubt I have time to learn it.
(project is due friday, which is the same day I have an exam in OOA/D).

I think I will extensive help, so if anyone wants to be more helpful than
the news-group ethics allow, please reply through email.

Regards,
T.



Quote:

> > I understand this principle of not overly helping others when it comes
to
> > school projects and the like, but sometimes you feel totally helpless.
(like
> > in this case).
> [snip]
> > What I think I need help with is not an explanation of how the A* works,
> > because I know its theories. I just cannot put those theories into
Prolog.
> > So if anyone could do their best to explain to me  what the algorithm
does
> > (line for line would be excellent), I'd be very grateful. Also perhaps
try
> > your best to explain how I fit it in with my program, and where in this
> > jungle which is my code, i add my additional heurestic.

> Let me remind you that I wrote, in a previous follow-up:
> >See Yoav Shoham, 1994, _Artificial Intelligence Techniques in Prolog_,
> >Morgan Kaufmann Publishers.

> >Relevant info is on pp38-39; the whole first part of the book is
> >about search strategies in Prolog. You'd probably want to look at
> >the immediately preceding section on best-first search.

> At most, to get through this part of the book, you'd have to read
> 40 pages. It's written very accessibly, with lots of code, and plenty
> of prose explanation of the code. I was a beginner in Prolog when I
> picked it up, and I highly recommend it.

> Hope that helps,

> John Paolillo
> SLIS and Informatics
> Indiana University



Wed, 12 May 2004 22:30:59 GMT  
 A* Algorithm

Quote:



>> I'm really new to Prolog, and in my AI class we've suddenly been given
>> an assignment to write some puzzles using an A* algorithm for solving
>> them. This project is the only Prolog we have...
> This sounds unfair to me.
> From what I remember of A*, it is not simple, and it must be
> very difficult for any beginner in Prolog to code it in Prolog!

Although in my experience you have to take what students say with
some caution. "We've suddenly been given an assignment on ..." can
sometimes mean "the prof has carefully worked up to the point where
this assignment can be done, with plenty of exercises, but I didn't
bother paying any attention until I was actually made to do a marked
assignment".

What you have to do is keep a list of states in best-first order,
and then repeatedly take the first state from the list, return it
if it is a solution state, otherwise generate its descendants and
add them to the list. For extra marks, use a heap rather than a
list (but this would be difficult in Prolog).

Actually, there is nothing here which really requires Prolog. The
whole point of this exercise is that the search is done best-first, so
you can't use Prolog's built-in search with backtracking. So I wonder
what is the point of using Prolog for it in the first place.

Matthew Huntbach



Fri, 14 May 2004 23:52:16 GMT  
 
 [ 13 post ] 

 Relevant Pages 

1. Converting recursive algorithms to tail recursive algorithms...???

2. Genetic Algorithms - practical applications?

3. Shortest Path algorithm needed

4. Shortest Path algorithm in APL

5. Looking for a quasi-newton or quadratic algorithm ...

6. simplex algorithm - R. Agnew function

7. Looking for good APL encrytion algorithms for WS proctection

8. Algorithm for datebase function

9. Wanted: algorithms/books on regression against Weibull distribution

10. APL for Parallel Algorithms

11. vsam algorithms?

12. MD5 algorithm

 

 
Powered by phpBB® Forum Software