Java程序辅导

Comp24412 (2012-13) Lab 2
The Travelling Salesman Problem in Prolog
Preamble
The purpose of this lab is to give you some more serious practice in Prolog
programming. You will implement an exhaustive search algorithm for the Trav-
elling Salesman Problem (TSP). This algorithm is not competitive for large
problem instances; but it nicely illustrates how to use Prolog search in a tricky
way.
The main program
The algorithm uses depth-first search on a space whose nodes represent initial
segments of a tour, and whose edges represent extensions of these initial seg-
ments by a single city. Let n be the total number of cities in the TSP instance
under consideration. We identify the cities with the integers 0, . . . , (n−1), and
we assume that, for distinct integers i, j in this range, d(i, j) gives the distance
between cities i and j, where d : N2 → N is symmetric in its arguments.
We adopt the following terminology. A proper path is a non-empty list of
integers in the range 0, . . . , (n − 1), without repeats, and ending with 0. The
length of that path is number of integers in the list in question minus 1. An
improper path is a list of integers formed from a proper path of length n − 1,
preceded by an additional occurrence of 0. Any improper path is said to have
length n. A path is a proper or improper path. An improper path represents a
tour from city to city in the obvious way, but conventionally read from right to
left. The cost of a path [am, . . . , a1] is defined to be
i=m−1∑
i=1
d(ai, ai+1).
Note that the cost of the length-0 path, [0], is 0. We take a node to be a
triple [p, m, c], where p is a path, m is its length, and c is its cost. A node
[p′, m′, c′] is a child of a node [p, m, c] if p′ is the result of adding one
city to the start of the list p. The initial node of the search tree is [[0],0,0],
corresponding to the zero-length path [0].
The implementation features a predicate child/4, such that, when
child(N,N1,U,V) is called with N instantiated to n, N1 to n − 1 and u to
1
any node, v is instantiated to a child of u, with all children eventually found on
resatisfaction. Notice that, as a result of our definitions, if u = [p,m,c] where
m = n − 1, then there is only ever one possible child of u; and if m = n, then
there are no children of u.
Now suppose that there is a fact in the database of the form bsf(p∗,c∗),
where p is an improper path (i.e. tour) and c∗ is its length. Informally, we
interpret this fact as asserting that p∗ is the best improper path so far found,
and has length c∗. Initially, p∗ is set to some dummy value (say [ ]), and c∗
is set to a value which we know will be larger than any optimal tour. (This is
easy to calculate.) Calls to the predicate child(N,N1,U,V) have side-effects as
follows. When called with a node u = [p,m,c] where m = n, the value c is
compared with the length, c∗, of the best tour so far, as recorded by bsf/2. If
c∗ ≤ c, nothing happens, and the call to child/4 simply fails (because u has
no children). If, on, the other hand c∗ > c, the old fact bsf(p∗,c∗) is replaced
with bsf(p,c), representing the fact that p is a newly found minimal-cost tour,
before the call to child/4 fails as before.
We can then search for a tour of minimal length using the predicate
search(N,N1,U):-
child(N,N1,U,V),
search(N,N1,V),
fail.
search(_N,_N1,_U).
We simply call search(n,n− 1,[[0],0,0]), and, when it is finished, read the
best path off from bsf(p∗,c∗). Make sure you understand why this works.
Actually, child/4 needs to be a bit cleverer than that. Suppose that
bsf(p∗,c∗) is in the database, and we are about to call child(n, n − 1, u,
V), where u = [p,m,c], and m < n. If c ≥ c∗, there is no chance we will beat
the best tour so far by extending u, and so we might as well take u to have no
children. Thus, in this case, the call child(n, n− 1, u, V) simply fails.
To complete the code, we need a predicate to generate problem instances,
makeArray/2, which generates a random problem instance of size n, in the in the
form of a collection of assertions of the form distance(i,j,d) (0 ≤ i < j < n).
See Task 1, below, for details. The resources file lab2_source.pl contains a
handy predicate distanceSym/2 which allows us to look up distances without
worrying about ordering the arguments.
The predicate printArray/1, which is provided for you, prints out the ma-
trix of distances in a pretty format. Check you understand how it works. Inci-
dentally, it assumes all distances are integral in the range 0 to 99. You should
keep all distances between pairs of cities in this range.
The tasks
1. Write a predicate makeArray/2, such that, when makeArray(n,M) is
called, a fact of the form distance(i,j,d) is asserted to the database for
every i, j (0 ≤ i < j ≤ n), where d is an integer chosen (for each i, j)
2
randomly in the range 0 to M −1. You will need to experiment a bit with
the built-in function random/1.
2 ?- makeArray(4,20).
true.
3 ?- listing(distance).
:- dynamic distance/3.
distance(0, 1, 3).
distance(0, 2, 5).
distance(1, 2, 18).
distance(0, 3, 13).
distance(1, 3, 1).
distance(2, 3, 8).
distance(0, 4, 7).
distance(1, 4, 7).
distance(2, 4, 2).
distance(3, 4, 4).
true.
[10 marks]
2. Look at the code provided for tspMakeAndRun/2. The definition of child/4
is missing. Write this definition, as specified above, and get the whole code
working. The result should be something like this:
5 ?- tspMakeAndRun(10,20).
0 1 2 3 4 5 6 7 8
9: 0 4 19 7 19 16 7 13 19
8: 17 15 2 4 11 10 11 13
7: 18 11 14 7 10 4 10
6: 4 18 12 18 15 13
5: 2 4 17 18 1
4: 9 19 17 17
3: 7 5 6
2: 1 0
1: 15
Best path: [0, 6, 9, 1, 2, 8, 3, 7, 4, 5, 0]
Cost: 41
true.
[10 marks]
3
Evaluation
There are 20 marks in total for this lab exercise. For each task, you get 6 marks
for a fully working program, and a further 4 for using proper Prolog style,
commenting and presentation. Solutions falling short of the ideal will receive
marks proportionately.
Use the submit mechanism to submit your work, which should be in the file
ex2.pl.
Resources
The file lab2 source.pl can be found in the course lab code repository.
4