我正在尝试实现一种简单高效的算法来解决旅行者问题（但这不是“旅行推销员”问题）：
A traveller has to visit N towns, and:
1. each trip from town X to town Y occurs once and only once
2. the origin of each trip is the destination of the previous trip
因此，如果您有A、B、C三个城镇，
A->B, B->A, A->C, **C->A, B->C**, C->B
这不是一个解决方案，因为您不能直接进行C->A和B->C的操作（需要在中间进行A->B的操作），而:
A->B, B->C, C->B, B->A, A->C, C->A
这是一个可行的解决方案（每个目的地都是下一次旅行的起点）。
以下是一个Java示例，有4个城镇。
ItineraryAlgorithm 是要实现的接口，用于提供回答问题的算法。如果您将 new TooSimpleAlgo() 替换为 new MyAlgorithm()，则 main() 方法将测试您的算法是否存在重复。
package algorithm;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Traveller {
private static final String[] TOWNS = new String[] { "Paris", "London", "Madrid", "Berlin"};
public static void main(String[] args) {
ItineraryAlgorithm algorithm = new TooSimpleAlgo();
List<Integer> locations = algorithm.processItinerary(TOWNS);
showResult(locations);
}
private static void showResult(List<Integer> locations) {
System.out.println("The itinerary is:");
for (int i=0; i<locations.size(); i++) {
System.out.print(locations.get(i) + " ");
}
/*
* Show detailed itinerary and check for duplicates
*/
System.out.println("\n");
System.out.println("The detailed itinerary is:");
List<String> allTrips = new ArrayList<String>();
for (int m=0; m<locations.size()-1; m++) {
String trip = TOWNS[locations.get(m).intValue()] + " to "+TOWNS[locations.get(m+1).intValue()];
boolean duplicate = allTrips.contains(trip);
System.out.println(trip+(duplicate?" - ERROR: already done this trip!":""));
allTrips.add(trip);
}
System.out.println();
}
/**
* Interface for interchangeable algorithms that process an itinerary to go
* from town to town, provided that all possible trips are present in the
* itinerary, and only once. Note that after a trip from town A to town B,
* the traveler being in town B, the next trip is from town B.
*/
private static interface ItineraryAlgorithm {
/**
* Calculates an itinerary in which all trips from one town to another
* are done. Trip to town A to town B should occur only once.
*
* @param the
* number of towns to visit
* @return the list of towns the traveler visits one by one, obviously
* the same town should figure more than once
*/
List<Integer> processItinerary(String[] towns);
}
/**
* This algorithm is too simple because it misses some trips! and generates
* duplicates
*/
private static class TooSimpleAlgo implements ItineraryAlgorithm {
public TooSimpleAlgo() {
}
public List<Integer> processItinerary(String[] towns) {
final int nbOfTowns = towns.length;
List<Integer> visitedTowns = new ArrayList<Integer>();
/* the first visited town is town "0" where the travel starts */
visitedTowns.add(Integer.valueOf(0));
for (int i=0; i<nbOfTowns; i++) {
for (int j=i+1; j<nbOfTowns; j++) {
/* travel to town "j" */
visitedTowns.add(Integer.valueOf(j));
/* travel back to town "i" */
visitedTowns.add(Integer.valueOf(i));
}
}
return visitedTowns;
}
}
}
这个示例程序的输出如下，第一部分是旅行者按顺序访问城镇的索引列表（0表示“巴黎”，1表示“伦敦”，2表示“马德里”，3表示“柏林”）。
The itinerary is:
0 1 0 2 0 3 0 2 1 3 1 3 2
The detailed itinerary is:
Paris to London
London to Paris
Paris to Madrid
Madrid to Paris
Paris to Berlin
Berlin to Paris
Paris to Madrid - ERROR: already done this trip!
Madrid to London
London to Berlin
Berlin to London
London to Berlin - ERROR: already done this trip!
Berlin to Madrid
你如何建议实施行程算法？
编辑：如果您愿意，您可以根据自己的喜好提出最多4、5、...、最多10个城镇的解决方案。