Statistical method for comparing fitting of TSP and Nearest Neighbour algorithms In Travelling Salesman Problem setting, a dataset of observed paths that visit each vertex once with a fixed starting point is given. The shortest paths (TSP paths) and Nearest Neighbour paths are considered and my task is to decide which algorithm describes the observed paths better. My only idea is to compare the percentage of TSP paths and NN paths in the given dataset. Is there a statistical method applicable to this problem?
UPDATE
Let us consider two "closeness" of the given path starting from the fixed vertex $O$ to the TSP and NN paths respectively
$$
\rho_{TSP}={\rm  the\, length\, of\, the\, given\, path - the\, length\, of\, the\, shortest\, TSP\, path}
$$
and
$$
\rho_{NN}=\# {\rm edges}\, AB\, {\rm on\, the\, given\, path\, such\, that}\, B\, {\rm is\, the\, nearest\, vertex\, to}\, A\, {\rm among\, the\, unvisited\, vertices} - \# {\rm all\, vertices}
$$
Then one can consider the set of the points on the plane with coordinates $(\rho_{TSP}({\rm path}),\rho_{NN}({\rm path}))$ for all possible paths and the distinguished point $(\rho_{TSP}({\rm given\, path}),\rho_{NN}({\rm given\, path})$.
I think that this data somehow can allow one to determine if the given path is closer to the TSP path or the NN path.
 A: From your problem description, it sounds like you are most interested in the question "Are path costs for my algorithm more similar to what I would expect from the optimal traveling salesman solution or the nearest neighbour solution?" 
The underlying problem is that you want to resolve how similar the distributions of costs are and I can think of two statistics-based approaches to resolving this question:


*

*comparing their histograms using a metric like correlation or $\ell_2$. More metrics can be found in this answer.

*use a statistical goodness of fit test like the Kolmogorov–Smirnov  test, the $\chi^2$ test, or the Anderson-Darling test. Which test you use depends what your costs on the graph look like for instance are they integers, positive integers, or real-valued?


In general, I think this problem is a little tricky to put into a statistical setting because it depends on the structure of the graphs and how the edge weights are assigned. For instance you can imagine families of graphs for which the NN and optimal TSP solution always coincide. If these graphs are say exponential random graphs with some distribution over the edge weights it may be possible to say more.
In your case, if I wanted a quick answer I would a take representative sample of the class of graphs of interest with similar size of vertices and edges. Then I'd compute the total path cost for each different graphs and different algorithm then compare histograms from all the graphs I have in my sample (although this is not a statistically well-founded solution!).
Finally, if you are really interested in analysing the performance, it may be worth pulling out a copy of your favourite analysis of algorithms text and formally going through the process, but that's not possible here without a description of the algorithm in question.
