0
$\begingroup$

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

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ thanks a lot there is the part that i want to know how to know number of possible ways in directed graph so i can know how much it will take to be solved by conclusions $\endgroup$ Jul 16 '19 at 11:29
  • $\begingroup$ because i am working on it but i have hard time to know when it will end not to finish it $\endgroup$ Jul 16 '19 at 11:32
  • $\begingroup$ edit it , is that more clearer $\endgroup$ Jul 16 '19 at 11:36
  • $\begingroup$ @MohamedAboALKear no, I still cannot understand the second part of your question - but perhaps someone else here will be able to help you. $\endgroup$
    – gandalf61
    Jul 16 '19 at 11:41
  • $\begingroup$ ok,i will make it , normal problem will have 25! ways if we have 25 cities so if i have directed graph can i know number of possible ways that i can create path $\endgroup$ Jul 16 '19 at 11:52
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ but i want to know the number of possible roads , as the problem that i have directed TSP that i want to know number of roads so i can stop program if it can not take the number $\endgroup$ Jul 17 '19 at 19:58
  • 1
    $\begingroup$ I don't understand what you mean by "know the number of roads". $\endgroup$ Jul 17 '19 at 20:04
  • $\begingroup$ number of roads like number of path or nodes in DTSP like " A-B-C-D" if we have 4 cities $\endgroup$ Jul 17 '19 at 20:53
0
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ you did not get the point , i can edit this directed graph so i can have city that can go to only one city and other can go two cities as example $\endgroup$ Jul 18 '19 at 1:00
  • $\begingroup$ sorry for not explain more the first edit cut one information i added it again $\endgroup$ Jul 18 '19 at 1:08
  • $\begingroup$ can you pls if you know the answer of edit i will be happy because it will always change as with each city you delete from connection will take many number of paths $\endgroup$ Jul 18 '19 at 1:10
  • $\begingroup$ @MohamedAboALKear I do not understand this constraint, could you give two examples? We are still talking about dTSP, but with really sparse setting? Yes, it will change the game, if you can set it with so low degree. $\endgroup$
    – Evil
    Jul 18 '19 at 4:27
  • $\begingroup$ ok,do you want me to add more examples like that i edit it in question up $\endgroup$ Jul 18 '19 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.