I hava an interesting problem related with GIS / MATH / TSP.

If I calculate the distance between A and B on a x/y-style coordinate system it is obvious to use the following formula:

sqrt((Ax-Bx)^2+(Ay-By)^2) = Distance

If I compare now 2 distances AB and CD it's obvious to do this with the formula on top:

sqrt((Ax-Bx)^2+(Ay-By)^2) = Distance
sqrt((Cx-Dx)^2+(Cy-Dy)^2) = Distance

Now if you need to do a lot of distance calculation, each SQRT() operation eats up valuable CPU time. And as we know 2<3 and 2^2<3^2 you can leave the sqrt() command away - just to enhance performance! SQRT is very expensive!

And now where it starts to get complicated for me. WHY doesn't this work with ABCDEF paths? Here is a classical TSP 3-opt optimization on these points.(example ABCDEF, ABCDFE, ABCFED, etc. permutations...). It's obvious that:

sqrt((Ax-Bx)^2+(Ay-By)^2) + sqrt((Cx-Dx)^2+(Cy-Dy)^2)

is not the same

(Ax-Bx)^2+(Ay-By)^2 + (Cx-Dx)^2+(Cy-Dy)^2

is obvious, but it should be proportional, or is this a wrong assumption?

I have the following log which shows that my theory is wrong!

Distanz without SQRT(): 2423932.0 - Distanz SQRT(): 24131.530843013228
Distanz without SQRT(): 2421100.0 - Distanz SQRT(): 24124.90131901531
Distanz without SQRT(): 2419674.0 - Distanz SQRT(): 24126.12515189262
Distanz without SQRT(): 2414714.0 - Distanz SQRT(): 24117.38148735822
Distanz without SQRT(): 2414304.0 - Distanz SQRT(): 24112.91523442742
Distanz without SQRT(): 2409924.0 - Distanz SQRT(): 24117.550376378276
Distanz without SQRT(): 2403676.0 - Distanz SQRT(): 24114.96478009344

The fact is that

 sqrt((Ax-Bx)^2+(Ay-By)^2) + sqrt((Cx-Dx)^2+(Cy-Dy)^2)

is not proportional to

 (Ax-Bx)^2+(Ay-By)^2 + (Cx-Dx)^2+(Cy-Dy)^2

Let's simplify the problem, let α be (Ax-Bx)^2+(Ay-By)^2, and β be (Cx-Dx)^2+(Cy-Dy)^2 , then you are saying sqrt(α) + sqrt(β) is proportional to α + β, which of course a wrong assumption.

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.