There is a series of complete undirected graphs $\Gamma$ with fixed starting points. Hamiltonian paths $c_\Gamma$ were obtained by a traveler who walked on $\Gamma$ and visited every vertex once. One needs to decide if the traveler's intention was more likely to minimize the total path length (TSP path) or visit the nearest unvisited vertex (NN algorithm).

My idea is

  1. Introduce two "metrics" on the Hamiltonian paths $a=A_0A_1\ldots A_n$: $$ \rho_T(a) = \sum_{i=0}^{n-1}|A_iA_{i+1}|,\quad \rho_N(a) =\sum_{i=0}^{n-1}\frac{|A_iA_{i+1}|}{\min\{|A_iA_j|, i+1\le j\le n\}}. $$ Clearly $\rho_T(a)$ is minimal if and only if $a$ is the shortest path, $\rho_N(a)$ is minimal if and only if $a$ is the NN path (one can assume that both are unique).
  2. For a given graph $\Gamma$ change the edge lengths L' <- rnorm (1,mean=L,sd=rL), $0<r<1$
  3. Find the shortest path and the NN path in the modified graph
  4. Calculate in the original graph $\rho_T$ of the shortest path and $\rho_N$ of the NN path from step 3.
  5. Repeat 2-4 and get two samples
  6. Calculate $p$-value of $t$-statistics for $\rho_T(c_\Gamma)$ and the first sample and $p$-value of $t$-statistics for $\rho_N(c_\Gamma)$ and the second sample. Denote them by $P_\Gamma$ and $P'_\Gamma$ respectively.
  7. Сompare the percentage of the graphs with $P_\Gamma<0.05, P'_\Gamma>0.05$ and the percentage of the graphs $\Gamma$ with $P_\Gamma'<0.05, P_\Gamma>0.05$. If the latter is greater than the former then the observed paths are more likely to be NN, i.e. the traveler's intention was local rather than global minimization.
  8. Adjust the deviation multiplier $r$ from step 2 so that the relation between the perсentages becomes clearer.

Is it a legitimate way to answer the question?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.