Name: Anonymous 2009-02-17 1:20
Hiya /prog/.
I need help on a question I have to do for an assignment. It has to be done in Scheme. Any pointers would be great. (It has to be done recursively, and using no controls (loops)).
"A road map consists of a set of cities, and a set of roads connecting them.
A road can be thought of as an (unordered) pair of cities. For example, here is a simple road map of Southern Ontario:
Cities = {Toronto, Ottawa, Kingston, Montreal}
Roads = {(Toronto, Montreal), (Toronto, Kingston),
(Kingston, Montreal), (Kingston, Ottawa),
(Ottawa, Montreal)}
Each road in a map is two-way, and it represents a direct connection between cities; i.e., it takes you from one city to another without passing through any other cities.
You are to write a Scheme function that helps a tourist to plan a vacation in which he visits each city exactly once.
Specifically, given a road map M, a path is a list of cities (C1,C2...Cn) such that there is a road from C1 to C2, another road from C2 to C3, etc. Your job is to define a Scheme function (path M C) that returns a path starting at C that mentions each city exactly once.1 For example, if M is the road map of Southern Ontario given above, then (path M ‘Toronto) might evaluate to the list (Toronto, Kingston, Montreal, Ottawa). If such a path does not exist, then return #f or the empty list, ()."
tl;dr: very simply traveling salesman problem. Function takes a map, and a starting city, and must visit each city once. Needs to be done in Scheme (similar to Lisp). I'm not asking for a full-blown solution, but some pointers would be nice. (also no loops, only recursion is allowed. the function looks like (path map city))
I need help on a question I have to do for an assignment. It has to be done in Scheme. Any pointers would be great. (It has to be done recursively, and using no controls (loops)).
"A road map consists of a set of cities, and a set of roads connecting them.
A road can be thought of as an (unordered) pair of cities. For example, here is a simple road map of Southern Ontario:
Cities = {Toronto, Ottawa, Kingston, Montreal}
Roads = {(Toronto, Montreal), (Toronto, Kingston),
(Kingston, Montreal), (Kingston, Ottawa),
(Ottawa, Montreal)}
Each road in a map is two-way, and it represents a direct connection between cities; i.e., it takes you from one city to another without passing through any other cities.
You are to write a Scheme function that helps a tourist to plan a vacation in which he visits each city exactly once.
Specifically, given a road map M, a path is a list of cities (C1,C2...Cn) such that there is a road from C1 to C2, another road from C2 to C3, etc. Your job is to define a Scheme function (path M C) that returns a path starting at C that mentions each city exactly once.1 For example, if M is the road map of Southern Ontario given above, then (path M ‘Toronto) might evaluate to the list (Toronto, Kingston, Montreal, Ottawa). If such a path does not exist, then return #f or the empty list, ()."
tl;dr: very simply traveling salesman problem. Function takes a map, and a starting city, and must visit each city once. Needs to be done in Scheme (similar to Lisp). I'm not asking for a full-blown solution, but some pointers would be nice. (also no loops, only recursion is allowed. the function looks like (path map city))