4
$\begingroup$

So, this is the scenario I have a graph with 7 points (say A to G) all interconnected (full mesh), and I want the best path to traverse all points starting from A and ending on G, but there are a couple of... caveats:

1.- The weight from A to B is not necessarily the same as the weight from B to A, and

2.- Some weights can be negative

Is there an algorithm that could help solve this problem?

$\endgroup$
4
  • $\begingroup$ Maybe self organizing maps could be used to make a guess, but getting the optimal path is unlikely. $\endgroup$
    – Galen
    May 17 at 1:46
  • $\begingroup$ @Galen TSPs much larger than this are routinely solved to optimality. $\endgroup$
    – RobPratt
    May 17 at 2:42
  • $\begingroup$ @RobPratt I'm surprised. Globally? Or just local optima? $\endgroup$
    – Galen
    May 17 at 3:42
  • $\begingroup$ @Galen Yes, globally. $\endgroup$
    – RobPratt
    May 17 at 12:12

2 Answers 2

4
$\begingroup$

Unfortunately, you are dealing with an $\mathsf{NP}$-hard problem, which is called the Traveling Salesman Problem. This means there is no efficient way to solve your problem.

Thankfully, the graph is relatively small, so brute force can be done in realistic time.

A reduction which you need to do is make all the edges' weights nonnegative. This can be done by adding a constant to all edges.

$\endgroup$
2
  • $\begingroup$ I don't think he needs to add anything. Let the particle traverse the entire plot for 1000000 times, with the negative constants and find the minimum. $\endgroup$
    – C.Koca
    May 16 at 21:10
  • $\begingroup$ I forgot to add that vertices can be revisited at any time, so yeah, brute-forcing sounds like the way to go. That, plus negative weights, makes it a bit different from the TSP I guess. $\endgroup$ May 16 at 22:02
0
$\begingroup$

If you introduce a dummy node adjacent to only A and G, you have an asymmetric traveling salesman problem on a directed graph with 8 nodes, which can be converted to a symmetric traveling salesman problem on an undirected graph with 16 nodes.

For directed or undirected TSP, you can have negative weights.

If you post the data, I'll find an optimal solution.

$\endgroup$

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.