How to compute number of possible paths in directed Traveling Salesman problem?

Question

If we have directed modification of TSP, so that some routes are possible in one direction, given directed graph, could you compute number of possible tours?

What if we have supercomputer, does it make dTSP more feasible?

edit:The number of different Hamiltonian paths in undirected graph is (n−1)!/2 in fully directed version it is (n−1)!, exact number could be computed from adjacency matrix

yes but if i delete city or two from connection like this example will not be fully and this is my case:

1 to 2,3

2 to 3

3 to 1,2,4,5

4 to 2,5,1

5 to 1

so i convert dTSP to simple graph my problem is to know how many paths can i create by my edited dTSP graph so if i have

1 to 2,3

2 to 1,3

3 to 1,2

i will have number 3!= 6 paths but if i edit it to be like that

1 to 2,3

2 to 3

3 to 1

i will have 3 paths only

i found that if one city is delete from connections can cut paths maybe by double as i try and error with small numbers of cities so i want to know if i possibly can calculate number of paths that created by this given connections

Answer 1

The way you have written your question makes it very difficult to understand, but let me try to answer one of your points as simply as I can.

Using a "super computer" (however you might define that) will not help us to make significant progress on the travelling salesman problem. The reason is that the time taken to solve a travelling salesman problem increases exponentially with the number of cities.

So suppose we can solve problems with up to 50 cities in a reasonable time on an "ordinary" computer (I have made this number up as an illustration). But let's also suppose that the running time of our most efficient algorithm is $O(2^n)$ - in other words, every time we add a city the time needed to find a solution doubles.

If we had a super computer that was a thousand times faster than an ordinary computer then it could solve problems with $60$ cities in the same time as an ordinary computer took for $50$ cities. This is because adding $10$ cities increases the problem difficulty by a factor of $2^{10} \approx 1000$.

So the super computer gives us a small improvement. But to solve problems with $100$ cities in a reasonable time we would need a computer that was a million million ($10^{12}$) times faster again.

Answer 2

What you're calling dTSP is no easier than ordinary TSP. You can simulate a two-way road between two cities by just having a one-way road in each direction. That means that being able to solve TSP with one-way roads means you can also solve TSP with two-way roads.

Supercomputers aren't really relevant because, with current TSP techniques, doubling the power of your computer only lets you deal with one more city in the same amount of time. So if your laptop can solve, say, 50 cities, then a computer that's 1024 times as powerful will only be able to solve 60.

Answer 3

The number of different Hamiltonian paths in undirected graph is $\frac{(n-1)!}{2}$ in fully directed version it is $(n-1)!$, exact number could be computed from adjacency matrix, but it is futile, according to definition:
The direction of cycle is irrelevant, both are exactly one tour, the equation reflects that, by discarding tours computed twice in bidirectional version.
So computing number of cycles is pointless, there are always $(n-1)!$ cycles in your graph.

To calculate number of paths: assume $K$ equal to $N$, and use matrix exponentation from adjacency matrix to obtain all results, keep in mind that some paths might be shorter, so there is no possible full tour. This solution counts cycles multiple times, but it is a good upper bound, efficiently computed.

For exact solution, you have to use backtracking and simply traverse them (it is unclear to me how you define path).