Trying to implement a kind of traveller algorithm in Java

Question

I'm trying to implement a simple and efficient algorithm for this kind of traveller problem (but this is NOT the "travelling salesman"):

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

So, if you have for example towns A, B, C,

A->B, B->A, A->C, **C->A, B->C**, C->B

is not a solution because you can't do C->A and then B->C (you need A->B in between), whereas:

A->B, B->C, C->B, B->A, A->C, C->A

is an acceptable solution (each destination is the origin of the next trip).

Here's below an illustration in Java, with 4 towns, for example.

ItineraryAlgorithm is the interface to implement when providing an algorithm that answers the question. The main() method will test your algorithm for duplicates if you replace new TooSimpleAlgo() by 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;
        }

    }

}

This example program gives the following output, the first part being the list of town indexes in the order the traveller visits them (0 for "Paris", 1 for "London", 2 for "Madrid", and 3 for "Berlin").

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

How would you suggest to implement ItineraryAlgorithm?
EDIT: if you prefer, you can propose a solution for a maximum of 4, 5, ..., up to 10 towns as you like.

Answer 1

This is not a Travelling Salesman Problem and IMHO it is not NP complete and can be done in O(N^2) time.

You can conduct a simple recursive DFS (with backtracking) from any node to all the nodes.

For example if the nodes are abcde,

The route shall be

abcde-dce-cbdbe-bacadaea

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

The Order of complexity is O(n^2) because the number of edges = 2*C(n,2)

Full working code in C++: (sorry I'm not familiar with Java. You can modify it accordingly)

#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;
}

Input:

abc

Output:

ab
bc
cb
ba
ac
ca

input:

abcde

Output: (changed new line to spaces)

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 )

Answer 2

Here is my Java solution (with Backtracking algorithm):

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class BobbelAlgo implements ItineraryAlgorithm {
    private final Stack<String> routes = new Stack<String>();

    public List<Integer> processItinerary(String[] towns) {
        routes.removeAllElements();
        final List<Integer> results = new ArrayList<Integer>();
        final int[] townIndexList = new int[towns.length];

        for (int i = 0; i < towns.length; i++) {
            townIndexList[i] = i;
        }

        // add starting town to list
        results.add(0);

        // start with route 'town 0' to 'town 1'
        visitTowns(townIndexList, townIndexList[0], townIndexList[1], results);

        return results;
    }

    public int visitTowns(final int[] towns, final Integer from, final Integer to, final List<Integer> results) {
        // 'from' is equals to 'to' or route already exists 
        if (from.equals(to) || routes.contains(from + "-" + to)) {
            return 2;
        }

        routes.push(from + "-" + to);
        results.add(to);

        if (routes.size() == towns.length * (towns.length - 1)) {
            // finished, all ways done
            return 0;
        }

        for (final int town : towns) {
            final int ret = visitTowns(towns, to, town, results);

            if (ret == 0) {
                // finished, all ways done
                return 0;
            } else if (ret == 1) {
                // no new way found, go back!
                routes.pop();
                results.remove(results.size() - 1);
            }
        }

        // no new way found, go back!
        return 1;
    }
}

For a benchmark, I've looped it through by a higher count of towns, see:

For 10 it took 1 ms.
For 15 it took 0 ms.
For 20 it took 0 ms.
For 25 it took 15 ms.
For 30 it took 15 ms.
For 35 it took 32 ms.
For 40 it took 93 ms.
For 45 it took 171 ms.
For 50 it took 328 ms.
For 55 it took 577 ms.
For 60 it took 609 ms.
For 65 it took 905 ms.
For 70 it took 1140 ms.
For 75 it took 1467 ms.
For 80 it took 1873 ms.
For 85 it took 2544 ms.
For 90 it took 3386 ms.
For 95 it took 4401 ms.
For 100 it took 5632 ms.

Here you can see the complexicity of O(n^2).
After about 100 towns, it gets a StackOverflowError, because the recursion calls are too deep for the default stack size configuration (see: Stack overflows from deep recursion in Java?).

Answer 3

I think I found what I was looking for:

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;
    }
}