[seqfan] Re: 100 cities to visit

[D. S. McNeil]

>
> 8-18-1-11-12-2-22-23-3-13-14-4-24-25-5-15-16-6-26-27-7-17-10-20-21-19-9.
>
> This has a total cost of 253. I don't know that it is optimal. With 27 cities, 8 must be at one end and 9 at the other; if 27 was dropped, 7 would also have to be at an end.

I think the optimal solution (non-round trip) is

[8, 18, 17, 7, 27, 26, 6, 16, 15, 5, 25, 24, 4, 14, 13, 3, 23, 22, 21,
20, 2, 12, 11, 1, 10, 19, 9]
for a total cost of 235.

>> What is the minimal cost of a journey
>> visiting all 100 cities exactly once?

I think the minimal cost of a journey visiting all 100 cities exactly
once is 367:

100, 91, 92, 93, 94, 95, 96, 97, 98, 99, 90, 89, 88, 87, 86, 85, 84,
83, 82, 81, 80, 78, 79, 77, 76, 75, 74, 73, 72, 71, 70, 67, 68, 69,
66, 65, 64, 63, 62, 61, 60, 56, 58, 59, 57, 55, 54, 53, 52, 51, 50,
45, 47, 49, 48, 46, 44, 42, 40, 41, 43, 39, 38, 37, 36, 35, 34, 33,
31, 30, 32, 29, 9, 19, 18, 8, 28, 27, 7, 17, 16, 6, 26, 25, 5, 15, 14,
4, 24, 23, 22, 21, 20, 2, 12, 11, 1, 10, 13, 3


Doug