Skip to main content
replaced http://upload.wikimedia.org/ with https://upload.wikimedia.org/
Source Link

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNGgraph

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNG

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

Tweeted twitter.com/#!/StackProgrammer/status/519156110620508160
Post Reopened by Bart van Ingen Schenau, Dan Pichelman, maple_shaft
added 32 characters in body
Source Link
Sundae
  • 133
  • 7

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNG

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above, and. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNG

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above, and be on the road as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNG

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above. He must be on the road between all nodes he visits as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

added 837 characters in body
Source Link
Sundae
  • 133
  • 7

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNG

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above, and be on the road as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

I'm looking for an algorithm that gives me the n nodes that are the farthest away from each other.

Can this be accomplished relatively efficiently?

To clarify my question: I think of the problem as a variant of the opposite of the travelling salesman problem. We have this graph:

graph http://upload.wikimedia.org/wikipedia/commons/c/ce/Clusters.PNG

The distance matrix looks like this:

    a   b   c   d   e   f
a   0   184 222 177 216 231
b   184 0   45  123 128 200
c   222 45  0   129 121 203
d   177 123 129 0   46  83
e   216 128 121 46  0   83
f   231 200 203 83  83  0

For example, the salesman needs to visit any 4 nodes shown above, and be on the road as long as possible. Which nodes would he visit?

My guess is we're looking for the 4 nodes with the maximum average distance between them. Is there a reasonably efficient, preferably non-exponential, way to do this? What if I don't need an exact solution to the problem?

Post Closed as "Needs details or clarity" by user53019, kevin cline, James McLeod, user40980, gnat
deleted 177 characters in body
Source Link
Sundae
  • 133
  • 7
Loading
Source Link
Sundae
  • 133
  • 7
Loading