A bit of a maths question

DevilWAH

Any maths geeks here?

Suppose I have a grid 100 by 100.

on the grid are 100 randomly placed points, your starting point is another random place on this grid.

what is the most efficient way to plot a path the that passes through all the 100 points. So not simply finding the shortest path, as this generally requires computing every possible path and comparing them. Does any one know any good ways to calculate a short path efficiently?

N2IT

Does these points have values?

I was thinking you could create your columns and rows with specific data relating to your array. Then create a chart in Excel (X Y Scatter). That will plot your data points. You can then go into the chart and select select data and then select hidden and empty cells. In there you could try the options in there. Maybe try Zero and make sure the show data in hidden rows and columns is checked.

DevilWAH

OK to make it a bit clearer see attachment.

Starting from the read square plot the shortest route through the orange points.

Now do the same for a grid 1000 X 1000 with 5000 points on it?

I know how to do it long hand, but I want to know if there is an algrathem that can do it efficiently, with out testing every possibility.

The long hand way to do it is to draw the shortest path between every single point and every other point.

Then create a list of possibly sequences that use these routes and take you through every point once. Starting at the Red Square

Compare this list and calculate the shortest one.

but for this to work there is an expodentioal increase in the number of possible paths each time you add a point. If n is the number of points minus 1, then number of links between all points is

(n²+n)/2

so for 500 points its about 12million paths.

then total possible routes!! I forget the equation but its going to be a fair few sever powers of 12.5 million. And all this is going to take some time to computer.

N2IT

Wouldn't the total number of paths from 500 points be 124750? I don't understand how you are getting 12.5 million.

DevilWAH

Cause I missed out a 0. I original put 5000 points in a 1000 square grid. But thenade a typo.

But the number are just examples. I just looking for ways to speed up working it out.

Suppose this is the classic traveling salesman issue. You c
an't be sure unless you test them all.

RobertKaucher

I would say that if the points cannot report in with their locations and neighbors then the only way to do it is test every possible path.

Having an algorithm figure things out is just not possible if the dots are in fact randomly placed. I'm not sure how one could mathematically derive order from random events.

nhpr

Anyone who has a good answer to this problem can make some money: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution

DevilWAH

nhpr wrote: »

Anyone who has a good answer to this problem can make some money: https://en.wikipedia.org/wiki/Travelling_salesman_problem#Computing_a_solution

that's what i wast thinking and could not think of the name of these types of issues. NP problems, you cant confirm you have the correct answer with out testing all possibility's.

I noted on that page "85,900 points was solved using Concorde TSP Solver, taking over 136 CPU-years"

However things like Sat NAvs' use algorithmins to find routes with out calculating ever possibility, I have been looking around and there do seem to be quick ways to get with in 1or 2% of the shortest path. going to look in to these a bit.

ChooseLife

DevilWAH wrote: »

Any maths geeks here?

Suppose I have a grid 100 by 100.

on the grid are 100 randomly placed points, your starting point is another random place on this grid.

what is the most efficient way to plot a path the that passes through all the 100 points. So not simply finding the shortest path, as this generally requires computing every possible path and comparing them. Does any one know any good ways to calculate a short path efficiently?

Off the top of my head...

The grid can be transformed into a complete graph with points as vertexes and shortest distances between pairs of points as edge weights. Then all possible Hamiltonian cycles can be calculated and their weights compared with each other.

This looks like the most intuitive approach, meaning that very likely less intuitive but more computationally efficient algorithms exist.