1
$\begingroup$

Given is a set of $n$ items: $x_1, x_2\ldots, x_n$. Additionally, we have a non-symmetrical evaluation function $f(x_i, x_j)$ that gives a cost value of two items. Note that $f(x_i, x_j)\neq f(x_j, x_i)$.

We want to find a list $y$ containing all items from $x$ exactly once such that the total cost of $y$, given by $F(y) = \sum_{i=1}^{n-1} f(x_i,x_{i+1})$, is minimal.

How can we do this?

$\endgroup$
  • 1
    $\begingroup$ What are the constraints on the sequence? Does the sequence have to contain all items? Is it a sequence of pairs? Otherwise, how is the total cost of a sequence determined? $\endgroup$ – Discrete lizard Mar 10 '18 at 10:39
  • $\begingroup$ @Discretelizard hi, the sequence should contain all the items in the set cuz we are seeking for an arrangement of these items in the set. The sequence is just an array contains all the items in ideal orders. Then the total cost is calculated by iterating all the items in the result sequence. i.e. sum of f(Xi, Xi+1) for i from 1 to n-1. Thanks :D $\endgroup$ – Microos Mar 10 '18 at 11:08
  • 2
    $\begingroup$ Do you really mean $f(x_i, x_j) \ne f(x_j, x_i)$, which states that these values must never be equal, or rather that it is possible for these values to be different? If the latter (and probably also if the former), this is essentially the Travelling Salesman Problem in disguise (just add one more vertex with a zero-cost edge to every vertex), so it's NP-hard unfortunately. $\endgroup$ – j_random_hacker Mar 10 '18 at 12:37
  • $\begingroup$ @j_random_hacker hi, according to the real world problem this question is modeled from, it's possible to make the $f$ symmetrical along with acceptable performance sacrifices. But it seems to be no big differences? $\endgroup$ – Microos Mar 10 '18 at 15:11
  • 1
    $\begingroup$ My question is what can we assume in trying to solve this problem. It sounds to me like what you're saying is "there is no guarantee that $f(x_i, x_j) = f(x_j, x_i)$", which means we can assume nothing. Contrast this with "We are guaranteed that $f(x_i, x_j) \ne f(x_j, x_i)$" -- this statement would give us (a very small amount of) structure to exploit in the problem that might enable a faster algorithm to be designed. $\endgroup$ – j_random_hacker Mar 10 '18 at 15:22
2
$\begingroup$

Unfortunately, this problem is NP-hard, which can be seen by transforming it into a question on graphs.

To see this, construct the graph $G=(V,E)$ with $V=\{x_1,x_2,\ldots,x_n\}$, $(v,w)\in E$ for all $v,w\in V$ and a cost function $c:E\rightarrow \mathbb{R}$ given by $c((x_i,x_j)) : =f(x_i,x_j)$. Observe that any path visiting all vertices in $V$ exactly once corresponds uniquely to an arrangement of the original set.

To show NP-hardness, we must first formulate a decision problem corresponding to the optimization problem. One such formulation is:

Given set $X$ of $n$ items and function $f:X\times X\rightarrow \mathbb{R}$ and an integer $T$, does there exist an arrangement such that the total cost of the arrangement is at most $T$?

By our discussion above, this problem is equivalent to

Given the full graph $G=(V,E)$ (i.e. $E=V\times V$) of $n$ vertices and cost function $c:E\rightarrow \mathbb{R}$ and an integer $T$, does there exist an Hamiltonian path such that the total cost of the edges of this path is at most $T$?

This problem is very similar to the traveling salesman problem (TSP), but isn't quite the same, as that problem requires a Hamiltonian cycle instead of a path.

However, as @j_random_hacker mentioned, this problem is in fact equivalent to the TSP problem on a different graph, namely $G'=(V',E')$ with $V' = V\cup \{z\}$, $E'=V'\times V'$ and $c'$ such that $c'(x,y)=c(x,y)$ for all $x,y\in V$ and $c(z,x)=c(x,z)=0$ for all $x\in V'$.

Therefore, the arrangement problem is indeed equivalent to TSP, which is NP-hard.


Although NP-hardness means that there are no efficient algorithms to find an exact solution, there are still heuristics that can find decent solution in reasonable time. There are many such approaches for the TSP problem.

The fact that we know that $f$ is 'fully' non-symmetric doesn't really help, it has the same use as knowing there is no guarantee for symmetry here, which only means some approaches won't work.

$\endgroup$
  • $\begingroup$ Thanks for your detailed explanations. Actually, there is a real-world problem that the question is modeled from. In view of the fact of its NP-hardness, I may consider another way to model the problem, e.g. a symmetrical evaluation function for reducing the complexity. And try a heuristics way to find a decent sub-optimal, maybe a reinforcement learning system can help, I guess. $\endgroup$ – Microos Mar 10 '18 at 15:11
  • 1
    $\begingroup$ @Microos Reinforcement learning sounds like a rather poor method to solve the problem currently stated. There are far better options to heuristically solve a TSP. Wikipedia provides a good introductory overview. $\endgroup$ – Discrete lizard Mar 10 '18 at 15:19

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.