3
$\begingroup$

Problem:

Consider $[k] = \{ 1, 2, \dots, k \}$ and function (of two arguments) $f: [k]^{2} \rightarrow \mathbb{N}$ that is defined for all $(n, m) \in [k]^{2}$ (all ordered pairs of numbers from $[k]$). Also, we know that for all $n, m \in [k]$ $$f(n, m) = f(m, n) .$$

Also, consider the set $S_{k}$ of all permutations on $[k]$ and function $g: S_{k} \rightarrow \mathbb{N}$ defined as follows $$ \sigma = \sigma_{1} \sigma_{2} \dots \sigma_{k} \quad \Rightarrow \quad g(\sigma) = \sum_{i = 1}^{k - 1} f(\sigma_{i}, \sigma_{i + 1}) .$$

The problem is to find at least one permutation $\sigma \in S_{k}$ such that $g(\sigma)$ is minimal.

Question:

How can we find the desired permutation faster than brute force?

$\endgroup$
  • $\begingroup$ A knight's tour is a very special permutation.... I'd try backtracking. It is very unlikely that there is a "nice" algorithm. There isn't for the plain knight tour, for one. $\endgroup$ – vonbrand Mar 4 '20 at 0:24
2
$\begingroup$

Hamiltonian path is a special case of your problem. Given a graph $G$, let $f(n,m) = 1$ if the edge $(n,m)$ exists, and $f(n,m) = 2$ otherwise. The minimum value of $g(\sigma)$ equals 1 iff $G$ contains a Hamiltonian path.

$\endgroup$

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.