Trying to implement a kind of traveller algorithm in Java

Question 1

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

Question 2

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 )

Question 3

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?).

Question 4

Like pointed out before, this is a serious research problem and can become quickly tedious to solve as the number of cities increase. There're however approximations available for the case where the distance between the graph nodes represent euclidean distance.

The approximation algorithms can provide you with solutions within polynomial time (as against exponential), but the catch is that there's an error bound associated. The solutions aren't simple and will need considerable effort to implement. Most of the algorithms are approach the problem geometrically instead of treating it as a graph, hence the assumption that the distance represent euclidean distance.

Question 5

This question looks like determining the Eulerian cycle in a directed graph[1].

Also it looks like in your cases, for the N towns, there always exist two symmetric roads between every two towns (e.g. A->B, B->A and so forth for all pairs). ~~If so, I don't think you need to write such an algorithm, if your job is to find only one of those cycles, because for 1,2...N, cycle 1,2..N-1,N,N-1..2,1 always meets the requirements.~~

~~But if there isn't always two symmetric roads between every two towns, things could be different and more complicated,~~ you may want to have a look at the eulerian path algorithm for directed graph (you should be able to find it in a discrete mathematics textbook, or the graph chapter of an algorithm textbook), and if there is such a path and the path has the same start point and terminal point, that means there is a solution for your problem.

[1] http://en.wikipedia.org/wiki/Eulerian_path

Question 6

This algorithm appears to generate an acceptable solution according to your constraints:

private static class Algorithm implements ItineraryAlgorithm {
    public List<Integer> processItinerary(String[] towns) {

        List<Integer> sequence = new ArrayList<>(towns.length*(towns.length+1));

        for(int idx1 = 0; idx < towns.length; idx1++){
            result.add(idx1);
            for(int idx2 = idx1+1; idx2 < towns.length; idx2++){
                sequence.add(idx2);
                sequence.add(idx1);
            }
        }

        List<Integer> segments = new ArrayList<>(result.length*2-2);
        for(int i: sequence){
            segments.add(i);
            segments.add(i);
        }
        segments.remove(0);
        segments.remove(segments.length-1);

        return segments;
    }
}