试图用Java实现一种旅行者算法

Question

我正在尝试为这种旅行者问题实施一种简单而有效的算法(但这不是"旅行推销员"):

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是提供回答问题的算法时实现的接口.该main()如果更换方法将测试你对重复算法new TooSimpleAlgo()通过new MyAlgorithm().

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

您如何建议实施ItineraryAlgorithm？
编辑:如果您愿意,您可以根据自己的喜好提出最多4个,5个,......,最多10个城镇的解决方案.

Answer 1

我想我找到了我正在寻找的东西：

private static class SylvainSAlgo implements ItineraryAlgorithm {

    @Override
    public List<Integer> processItinerary(String[] towns) {

        List<Integer> itinerary = new ArrayList<Integer>();
        for (int i = 0; i<towns.length; i++) {
            for (int j = i + 1; j < towns.length; j++) {
                itinerary.add(Integer.valueOf(i));
                itinerary.add(Integer.valueOf(j));
            }
        }
        itinerary.add(Integer.valueOf(0));
        return itinerary;
    }
}