Hi,
First of all, this is a school assignment.
6a. Write a function
(flightConnect C1 Cn L)
where C1 and Cn are cities, and the function returns a pair (Cost (C1 C2 ...
Cn)) where (C1 C2 ... Cn) represents a flight connection from C1 to C2, C2
to C3, and so on, to arrive at Cn at the end, and Cost is the total cost for
flying from C1 to Cn. If there is more than one way of flying from C1 to Cn,
your function may return any solution.
6b. Write a function
(booking C1 Cn L)
which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) is a flight
connection with the minimal cost Cost for flying from C1 to Cn.
I can tackle this problem in other programming languages. However, I am new
to lisp so I need your advice on how to structure my program in lisp.
thx a lot!
Sorry, in my previous posting I omitted the definition of L.
"We will use a triple (A B C) to represent a direct flight from city A to
city
B with the cost C. In the following suppose L is such a list of triples
(note
that there could be different flights between two cities). "
"james" <·········@hotmail.com> д����Ϣ����
·······················@news0.telusplanet.net...
> Hi,
> First of all, this is a school assignment.
>
> 6a. Write a function
>
> (flightConnect C1 Cn L)
> where C1 and Cn are cities, and the function returns a pair (Cost (C1 C2
...
> Cn)) where (C1 C2 ... Cn) represents a flight connection from C1 to C2, C2
> to C3, and so on, to arrive at Cn at the end, and Cost is the total cost
for
> flying from C1 to Cn. If there is more than one way of flying from C1 to
Cn,
> your function may return any solution.
> 6b. Write a function
>
> (booking C1 Cn L)
> which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) is a
flight
> connection with the minimal cost Cost for flying from C1 to Cn.
>
> I can tackle this problem in other programming languages. However, I am
new
> to lisp so I need your advice on how to structure my program in lisp.
>
> thx a lot!
>
>
"james" <·········@hotmail.com> writes:
> Sorry, in my previous posting I omitted the definition of L.
>
> "We will use a triple (A B C) to represent a direct flight from city A to
> city
> B with the cost C. In the following suppose L is such a list of triples
> (note
> that there could be different flights between two cities). "
AFAICR, Peter Norvig's "Paradigms of Artificial Intelligence
Programming" has code for this problem. See
http://www.norvig.com/paip/search.lisp
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
From: Marco Antoniotti
Subject: Re: single shortest path implementation in lisp
Date:
Message-ID: <3E2C2DCC.4080605@cs.nyu.edu>
(Shameless plug)
In the AI.Repository there is an implementation of HEAPS in CL.
You need it for the SSSP problem.
Cheers
james wrote:
> Sorry, in my previous posting I omitted the definition of L.
>
> "We will use a triple (A B C) to represent a direct flight from city A to
> city
> B with the cost C. In the following suppose L is such a list of triples
> (note
> that there could be different flights between two cities). "
>
>
> "james" <·········@hotmail.com> д����Ϣ����
> ·······················@news0.telusplanet.net...
>
>>Hi,
>>First of all, this is a school assignment.
>>
>>6a. Write a function
>>
>>(flightConnect C1 Cn L)
>>where C1 and Cn are cities, and the function returns a pair (Cost (C1 C2
>
> ...
>
>>Cn)) where (C1 C2 ... Cn) represents a flight connection from C1 to C2, C2
>>to C3, and so on, to arrive at Cn at the end, and Cost is the total cost
>
> for
>
>>flying from C1 to Cn. If there is more than one way of flying from C1 to
>
> Cn,
>
>>your function may return any solution.
>>6b. Write a function
>>
>>(booking C1 Cn L)
>>which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) is a
>
> flight
>
>>connection with the minimal cost Cost for flying from C1 to Cn.
>>
>>I can tackle this problem in other programming languages. However, I am
>
> new
>
>>to lisp so I need your advice on how to structure my program in lisp.
>>
>>thx a lot!
>>
>>
>
>
>
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
715 Broadway 10th Floor fax +1 - 212 - 998 3484
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
On Sun, 19 Jan 2003 19:50:10 GMT, "james" <·········@hotmail.com>
wrote:
>6b. Write a function
>
>(booking C1 Cn L)
>which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) is a flight
>connection with the minimal cost Cost for flying from C1 to Cn.
>
>I can tackle this problem in other programming languages. However, I am new
>to lisp so I need your advice on how to structure my program in lisp.
Yeah. Sure. How stupid do you think we are? This problem is close to a
very classic problem, but a bit more complex. I doubt very much that
you could do this problem in any other language. Instead you lie so
that we may feel less like we are helping you cheat because you
understand the algorithm.
Tell you what. Come back next week after you've handed in the
assignment, and I'll be happy to advise.
"james" <·········@hotmail.com> wrote in message
···························@news0.telusplanet.net...
> Hi,
> First of all, this is a school assignment.
>
> 6a. Write a function
>
> (flightConnect C1 Cn L)
> where C1 and Cn are cities, and the function returns a pair (Cost (C1 C2
...
> Cn)) where (C1 C2 ... Cn) represents a flight connection from C1 to C2, C2
> to C3, and so on, to arrive at Cn at the end, and Cost is the total cost
for
> flying from C1 to Cn. If there is more than one way of flying from C1 to
Cn,
> your function may return any solution.
> 6b. Write a function
>
> (booking C1 Cn L)
> which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) is a
flight
> connection with the minimal cost Cost for flying from C1 to Cn.
>
> I can tackle this problem in other programming languages. However, I am
new
> to lisp so I need your advice on how to structure my program in lisp.
If you can solve it in another language, then you should be able to express
it in pseudo-code, if you can express it in pseudo-code then you can start
writing it in Lisp! Pseudo-code is probably a good approach when the
implementation language is unfamiliar.
You could also start working "bottom-up" and define your data structures and
some accessors and utility functions you think you will need. Lisp is very
good for that because you don't have to have a complete ap to start testing
it, or even a complete function. You can create a few city data structures,
create a small "map" and start testing some simple functions.
Get *something* down on paper and come back for comments/advice, then it
will be easier to help you.
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
From: Larry Clapp
Subject: Re: single shortest path implementation in lisp
Date:
Message-ID: <nb0g0b.9fd.ln@127.0.0.1>
"james" <·········@hotmail.com> wrote in message
> ···························@news0.telusplanet.net...
> Hi,
> First of all, this is a school assignment.
>
> 6a. Write a function
>
> (flightConnect C1 Cn L)
> where C1 and Cn are cities, and the function returns a pair
> (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) represents a flight
> connection from C1 to C2, C2 to C3, and so on, to arrive at Cn
> at the end, and Cost is the total cost for flying from C1 to
> Cn. If there is more than one way of flying from C1 to Cn, your
> function may return any solution.
> 6b. Write a function
>
> (booking C1 Cn L)
> which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ...
> Cn) is a flight connection with the minimal cost Cost for
> flying from C1 to Cn.
>
> I can tackle this problem in other programming languages.
> However, I am new to lisp so I need your advice on how to
> structure my program in lisp.
First of all, James, thanks for an interesting problem, from
another Lisp newbie. I spent the past several hours answering
it, and enjoyed it a lot.
In article <············@otis.netspace.net.au>, Coby Beck wrote:
[ good advice from Coby snipped ]
> You could also start working "bottom-up" and define your data
> structures and some accessors and utility functions you think
> you will need. Lisp is very good for that because you don't
> have to have a complete ap to start testing it, or even a
> complete function. You can create a few city data structures,
> create a small "map" and start testing some simple functions.
I'll second this advice. Once I figured out how I'd represent my
network, and how I'd keep track of the current list of candidate
paths, I didn't have tons of trouble writing the rest of the
code.
Some more advice, which might or might not apply to you: don't
worry too much at first about the efficiency of your data
structures or algorithms. (As a reasonably seasoned C & Perl
programmer, I have to fight this habit often.) Get it working,
/then/ look at how you might trim some unneeded code or data out
of it.
Something to start you off: given a node A, what cities can A
reach? What cities can /they/ reach? If you can define a
network, and write code to answer these questions, you've
achieved about half of your goal.
-- Larry
On 1/19/03 11:50 AM, in article
······················@news0.telusplanet.net, "james"
<·········@hotmail.com> wrote:
> Hi,
> First of all, this is a school assignment.
>
> 6a. Write a function
>
> (flightConnect C1 Cn L)
> where C1 and Cn are cities, and the function returns a pair (Cost (C1 C2 ...
> Cn)) where (C1 C2 ... Cn) represents a flight connection from C1 to C2, C2
> to C3, and so on, to arrive at Cn at the end, and Cost is the total cost for
> flying from C1 to Cn. If there is more than one way of flying from C1 to Cn,
> your function may return any solution.
> 6b. Write a function
>
> (booking C1 Cn L)
> which returns a pair (Cost (C1 C2 ... Cn)) where (C1 C2 ... Cn) is a flight
> connection with the minimal cost Cost for flying from C1 to Cn.
>
> I can tackle this problem in other programming languages. However, I am new
> to lisp so I need your advice on how to structure my program in lisp.
>
> thx a lot!
>
>
The old maze-router problem...
The use of heaps and tree searches are great. They can be part of the
solution process. You can consider this problem to be one of working your
way thru a maze with many solution paths. Your want to "optimize" that path.
You have a network of airports (nodes) connected by their (great circle)
distances (sub-path). You have a cost function that is applied (a) to the
distances and (b) to the airports. From the starting node, proceed to each
connecting node, measuring the cost as you traverse to the distance (and
node). Repeat this process at each new node accumulating your sub-paths and
checking to be sure that you don't circle back or dead-end, verifying that a
particular path has not already become too expensive, and determining if you
have arrived at your destination. I've seen this referred to as the "Lee
Algorithm" in some circuit path tracing tech papers. I've recently
implemented something like this for tracing wire routes.
Some special data structures will help you keep from running out of memory
as you build your paths in very large networks.
steve long