Hi!
I�ve the following problem:
Actualy I�m programming something like "traveling salesman".
I�ve a list of streets. Each element (street) is a list of two places.
Too find a way from A to B, I�ve to start with creating a tree
(represented by cascaded lists).
But I�ve no idea how to implement the procedure which creates the tree.
I hope someone can help me.
... code would be really great.
Ciao
Wolfgang
---
email:
········@fh-furtwangen.de
········@ai-lab.fh-furtwangen.de
In article <·················@darkstar.ghb.fh-furtwangen.de>,
Wolfgang Kleinertz <········@darkstar.ghb.fh-furtwangen.de> wrote:
>... code would be really great.
Yes, homework is much easier if someone else writes the answer for you.
I'm assuming this is a homework assignment, since fh-furtwangen.de is
Fachhochschule Furtwangen. I don't know much German, but I'm pretty sure
the "schule" suffix means "school".
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Barry Margolin wrote:
> Yes, homework is much easier if someone else writes the answer for you.
Sure ;), but this isn�t my homework. It�s just a piece of an AI (artificial
intelligence) project ...My problem is the rudimentary knowledge about
programming in lisp. I started learning lisp in the bounds of this projekt
(some day ago), but that�s not the goal ...
The goal is to understand, implement and develope AI-methods.
> I'm assuming this is a homework assignment, since fh-furtwangen.de is
> Fachhochschule Furtwangen. I don't know much German, but I'm pretty sure
> the "schule" suffix means "school".
That�s right. Its�s a school in common sence, but it�s more like an university
(there is no totally correct tranlation).
CU
Wolfgang
In article <·················@darkstar.ghb.fh-furtwangen.de>,
Wolfgang Kleinertz <········@darkstar.ghb.fh-furtwangen.de> wrote:
>Barry Margolin wrote:
>> I'm assuming this is a homework assignment, since fh-furtwangen.de is
>> Fachhochschule Furtwangen. I don't know much German, but I'm pretty sure
>> the "schule" suffix means "school".
>
>That�s right. Its�s a school in common sence, but it�s more like an university
>(there is no totally correct tranlation).
I'm sorry for jumping to a wrong conclusion. Many university students post
to newsgroups looking for easy answers to their homework problems, and your
request was like many of them.
With that said, it would help if you would describe what you're trying to
do better. We need to see the format of the input data and what type of
output you're trying to produce.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Barry Margolin wrote:
> I'm sorry for jumping to a wrong conclusion. Many university students post
> to newsgroups looking for easy answers to their homework problems, and your
> request was like many of them.
> With that said, it would help if you would describe what you're trying to
> do better. We need to see the format of the input data and what type of
> output you're trying to produce.
Our starting point is a list of starting and destination points, speeds, distances
and hindrances (e.g. traffic lights). We modified to the following lisp structure:
(setf Karte
(list
(list 'Stornoway 'Ullapool 15 80 0)
(list 'Stornoway 'Tolsta 40 13 4)
(list 'Stornoway 'Barvas 60 12 1)
(list 'Barvas 'Port-of-Ness 60 16 6)
(list 'Barvas 'Carloway 60 12 3)
(list 'Carloway 'Callanish 60 7 1)
(list 'Callanish 'Garynahine 60 2 0)
(list 'Garynahine 'Stornoway 60 13 1)
(list 'Garynahine 'Tobson 40 13 2)
(list 'Stornoway 'Tarbert 60 36 6)
(list 'Tarbert 'Leverburgh 60 21 2)
(list 'Leverburgh 'Rodel 60 3 0)
(list 'Tarbert 'Uig 15 50 0)
(list 'Tarbert 'Lochmaddy 15 50 0)
(list 'Leverburgh 'Newton15 15 15 0)
(list 'Lochmaddy 'a865b893 60 5 0)
(list 'a865b893 'Newton15 40 5 0)
(list 'a865b893 'Clachan-a-Luib 60 20 3)
(list 'Lochmaddy 'Clachan-a-Luib 60 9 0)
(list 'Gramsdale 'Clachan-a-Luib 60 9 2)
(list 'Gramsdale 'Nunton 40 9 1)
Syntax:
from
to
max. possible speed between "from" and "to"
distance
hindrances (multiplier of 30 minutes)
The goal is to find a possible (it can, but hasn�t to be the best) way from A
place to to another place B.
To use blind, heuristic or perfect methods like: Breadth-First, Depth-First,
Hill-Climbing, "British Museum", branch-and-bound, ....
... we have to start with building a tree.
e.g.: Barvas -> Tobson
Barvas
/ \
Port-of-Ness Carloway
|
Callanish
|
Garynahine
/ \
Tobson Stornoway
====== / | \
Ullapool Tolsta Barvas
| -----
...
root: starting point
nodes: stops (e.g. between Barvas and Tobson)
leafs: possible results, places which already has been reached (like Barvas),
other places with no connection
In lisp, this tree should be represented by a cascaded list like:
(Barvas (Port-of-Ness () Carloway (Callanish (Garynahine (Tobson () Stornoway
(Ullapool (...) Tolsta () Barvas ()))))))
This step is the problem. The knowledge about lisp and my blindness to write such
a recursiv procedure are the problems.
Till now, I wrote the following code:
;; global map
(load 'karte.lsp)
;; startingpoint
(defun get_from(l)
;(print l)
(first l)
)
;; destination
(defun get_to(l)
(second l)
)
;; returns the successors of l
(defun fad(from l)
(cond
((equal (first (get_from l)) from) (cons (get_to (first l)) (fad from (rest
l))))
((NOT (endp l)) (fad from (rest l)))
)
)
;; successors of the elements from list "l"
;; "landkarte" is the global map
(defun NachList(l landkarte)
(cond
((not (endp (rest l))) (cons (fad (first l) landkarte) (NachList (rest l)
landkarte)))
((not (endp l)) (list (fad (first l) landkarte)))
)
)
;; should create the tree
(defun make_tree( )
;???
)
I�hope it would be a bit clearer, despite my bad english ... :)
Ciao
Wolfgang
---
email:
········@fh-furtwangen.de
········@ai-lab.fh-furtwangen.de
I don't have the time to do a detailed answer, but here are some ideas:
Wolfgang Kleinertz <········@darkstar.ghb.fh-furtwangen.de> writes:
> Our starting point is a list of starting and destination points, speeds, distances
> and hindrances (e.g. traffic lights). We modified to the following lisp structure:
>
> (setf Karte
> (list
> (list 'Stornoway 'Ullapool 15 80 0)
> (list 'Stornoway 'Tolsta 40 13 4)
> (list 'Stornoway 'Barvas 60 12 1)
> (list 'Barvas 'Port-of-Ness 60 16 6)
> (list 'Barvas 'Carloway 60 12 3)
> (list 'Carloway 'Callanish 60 7 1)
>
> Syntax:
> from
> to
> max. possible speed between "from" and "to"
> distance
> hindrances (multiplier of 30 minutes)
IDEA #1: Don't build an explicit tree in the first place. Instead,
I would consider building a hash-table using the name of the place as the key.
The value of each hash table cell would be a list of the data values.
For example:
STORNOWAY : ((Ullapool 15 80 0) (Tolsta 40 13 4) (Barvas 60 12 1))
BARVAS : ((Port-of-Ness 60 16 6) (Carloway 60 12 3))
...
Each element in the hash table is a node in your graph, with the
accessible neighbors and associated information stored with it. You
will then need to modify the graph traversal algorithms to understand
your new structure.
IDEA #2: If you want or need to build a tree structure, I would still
use a hash table as an intermediate structure to combine all of the
children of a particular node. Then you can either write code that
traverses the hash table and builds a tree structure from its entries,
or else you can write something that uses destructive list operations to
construct a tree structure as you parse.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu