There is no doubt that these three tours are distinct from the first set of three tours. And in each of these three
tours, every city is visited exactly once, as required in the problem. So they are valid tours as well. Why did
our formula give us 3 for the value of the number of possible valid tours, while we are able to find 6?
The answer lies in the fact that if two valid tours are symmetric and have the same energy level, because they
have the same value for the total distance traveled in the tour, one of them is in a sense redundant, or one of
them can be considered degenerate, using the terminology common to this context. As long as they are valid
and give the same total distance, the two tours are not individually interesting, and any one of the two is
enough to have. By simple inspection, you find the total distances for the six listed tours. They are 32 for tour
1, 32 also for tour 6, 45 for each of tours 2 and 4, and 39 for each of tours 3 and 5. Notice also that tour 6 is
not very different from tour 1. Instead of starting at city 1 as in tour 1, if you start at city 2 and follow tour 1
from there in reverse order of visiting cities, you get tour 6. Therefore, the distance covered is the same for
both these tours. You can find similar relationships for other pairs of tours that have the same total distance
for the tour. Either by reversing the order of cities in a tour, or by making a circular permutation of the order
of the cities in a tour, you get another tour with the same total distance. This way you can find tours. Thus,
only three distinct total distances are possible, and among them 32 is the lowest. The tour 1 − 2 − 3 − 4 − 1 is
the shortest and is an optimum solution for this traveling salesperson problem. There is an alternative
optimum solution, namely tour 6, with 32 for the total length of the tour. The problem is to find an optimal
tour, and not to find all optimal tours if more than one exist. That is the reason only three distinct tours are
suggested by the formula for the number of distinct valid tours in this case.
The formula we used to get the number of valid and distinct tours to be 3 is based on the elimination of such
symmetry. To clarify all this discussion, you should determine the energy levels of all your six tours identified
earlier, hoping to find pairs of tours with identical energy levels.
Note that the first term on the right−hand side of the equation results in 0 for a valid tour, as this term is to
ensure there is no more than a single 1 in each row. That is, in any summand in the first term, at least one of
the factors, x
ik
or x
ij
, where k ` j has to be 0 for a valid tour. So all those summands are 0, making the first term
itself 0. Similarly, the second term is 0 for a valid tour, because in any summand at least one of the factors, x
ki
or x
ji
, where k ` j has to be 0 for a valid tour. In all, exactly 4 of the 16 x’s are each 1, making the total of the
x’s 4. This causes the third term to be 0 for a valid tour. These observations make it clear that it does not
matter for valid tours, what values are assigned to the parameters A
1
, A
2
, and A
3
. Assigning large values for
these parameters would cause the energy levels, for tours that are not valid, to be much larger than the energy
levels for valid tours. Thereby, these tours become unattractive for the solution of the traveling salesperson
problem. Let us use the value 1/2 for the parameter A
4
.
Let us demonstrate the calculation of the value for the last term in the equation for E, in the case of tour 1.
Recall that the needed equation is
E = A
1
£
i
£
k
£
j`k
x
ik
x
ij
+ A
2
£
i
£
k
£
j`k
x
ki
x
ji
+ A
3
[( £
i
£
k
x
jk
) − n]
2
+ A
4
£
k
£
j`k
£
i
d
kj
x
ki
(x
j,i+1
+ x
j,i−1
)
The last term expands as given in the following calculation:
A
4
{
d
12[
x
12(
x
23 +
x
21) +
x
13(
x
24 +
x
22) +
x
14(
x
21 +
x
23)] +
d
13[
x
12(
x
33 +
x
31) +
x
13(
x
34 +
x
32) +
x
14(
x
31 +
x
33)] +
d
14[
x
12(
x
43 +
x
41) +
x
13(
x
44 +
x
42) +
x
14(
x
41 +
x
43)] +
d
21[
x
21(
x
12 +
x
14) +
x
23(
x
14 +
x
12) +
x
24(
x
11 +
x
13)] +
d
23[
x
21(
x
32 +
x
34) +
x
23(
x
34 +
x
32) +
x
24(
x
31 +
x
33)] +
d
24[
x
21(
x
42 +
x
44) +
x
23(
x
44 +
x
42) +
x
24(
x
41 +
x
43)] +
d
31[
x
31(
x
12 +
x
14) +
x
32(
x
13 +
x
11) +
x
34(
x
11 +
x
13)] +
d
32[
x
31(
x
22 +
x
24) +
x
32(
x
23 +
x
21) +
x
34(
x
21 +
x
23)] +
d
34[
x
31(
x
42 +
x
44) +
x
32(
x
43 +
x
41) +
x
34(
x
41 +
x
43)] +
d
41[
x
41(
x
12 +
x
14) +
x
42(
x
13 +
x
11) +
x
43(
x
14 +
x
12)] +
d
42[
x
41(
x
22 +
x
24) +
x
42(
x
23 +
x
21) +
x
43(
x
24 +
x
22)] +
d
43[
x
41(
x
32 +
x
34) +
x
42(
x
33 +
x
31) +
x
43(
x
34 +
x
32)] }
When the respective values are substituted for the tour 1 − 2 − 3 − 4 − 1, the previous calculation becomes:
1/2{10[0(0 + 1) + 0(0 + 0) + 1(1 + 0)] + 14[0(0 + 0) + 0(0 + 1) +
1(0 + 0)] +
7[0(1 + 0) + 0(0 + 0) + 1(0 + 1)] + 10[1(0 + 1) + 0(1 + 0) +
0(0 + 0)] +
6[1(1 + 0) + 0(0 + 1) + 0(0 + 0)] + 12[1(0 + 0) + 0(0 + 0) +
0(0 + 1)] +
14[0(0 + 1) + 1(0 + 0) + 0(0 + 0)] + 6[0(0 + 0) + 1(0 + 1) +
0(1 + 0)] +
9[0(0 + 0) + 1(1 + 0) + 0(0 + 1)] + 7[0(0 + 1) + 0(0 + 0) +
1(1 + 0)] +
C++ Neural Networks and Fuzzy Logic:Preface
Example of a Traveling Salesperson Problem for Hand Calculation
339
12[0(0 + 0) + 0(0 + 1) + 1(0 + 0)] + 9[0(1 + 0) + 0(0 + 0) +
1(0 + 1)]}
= 1/2( 10 + 0 + 7 + 10 + 6 + 0 + 0 + 6 + 9 + 7 + 0 + 9)
= 1/2(64)
= 32
Table 15.1 contains the values we get for the fourth term on the right−hand side of the equation, and for E,
with the six listed tours.
Do'stlaringiz bilan baham: 
