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?