java - 尝试用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 是提供回答问题的算法时要实现的接口(interface)。如果您将 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

您建议如何实现 ItineraryAlgorithm？
编辑:如果您愿意，您可以根据需要提出最多 4 个、5 个……最多 10 个城镇的解决方案。

Answer 1

这不是旅行商问题，恕我直言，它不是 NP 完备的，可以在 O(N^2) 时间内完成。

您可以执行从任何节点到所有节点的简单递归 DFS (带回溯)。

例如，如果节点是abcde，

路线应该是

abcde-dce-cbdbe-bacadaea

(Total C(5,2) * 2 = 20 edges)

复杂度的阶数是 O(n^2) 因为边数 = 2*C(n,2)

C++ 中的完整工作代码:(抱歉，我不熟悉 Java。您可以相应地修改它)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>


using namespace std;

string cities;

void recurRoute( int prevIndex, int currIndex, vector<pair<int,int> > &traversed ) {

    // For each i > currIndex, if edge (currindex to i) not in traversed, 
    // then add the edge and recur on new index i.
    for ( int i = currIndex+1; i < cities.size(); i++ ) {

        pair<int,int> newEdge( currIndex, i );
        if ( find( traversed.begin(), traversed.end(), newEdge ) == traversed.end() ) {
            traversed.push_back( newEdge );
            recurRoute( currIndex, i, traversed );
        }
    }

    // if there is a previous index, 
    // then add the back edge (currIndex to prevIndex) and return.
    if ( prevIndex >= 0) {
        pair<int,int> prevEdge( currIndex, prevIndex );
        traversed.push_back( prevEdge );
    }
    return;
}

int main()
{
    cin >> cities;

    vector<pair<int,int> > edges;

    recurRoute( -1, 0, edges );

    for ( int i = 0; i < edges.size(); i++ ) {
        cout << cities[ edges[i].first ] << cities[ edges[i].second ] << endl;
    }

    return 0;
}

输入:

abc

输出:

ab
bc
cb
ba
ac
ca

输入:

abcde

输出:(将新行更改为空格)

ab bc cd de ed dc ce ec cb bd db be eb ba ac ca ad da ae ea
( abcde-dce-cbdbe-bacadae as noted previously )