kleinwolf
Nov23-05, 02:10 AM
There are two famous NP optimization problems :
1) traveling salesman : find the shortest path in a graph, through all vertices. Without boundary conditions, this is : min_{\sigma\in Perm(\mathbb{N}_n)}\sum_{i=1}^{N-1}a_{\sigma(i),\sigma(j)} where there are n cities, and the distance between cities i and j is a_{ij}..and \sigma is just a permutation of the cities order.
2) coin-changing problem : the less coins you need to make up to a given sum S in a given coin system \left(v_i\right)_{i=1}^k : \tilde{\min}_{n} \left(\sum_{i=1}^n v_{f(i)}=S\right) where f : \mathbb{N}_n\rightarrow \mathbb{N}_k with v_f(i) is giving the index of the ith coin needed. \tilde{min} gives the minimal n, If n does not exist, then it is \infty.
I thinnk there should exist a forumla betwen those two problems : the coin system is equivalent to the distances between cities (kind of constraint), but I cannot firgure it out..could somebody help ?
1) traveling salesman : find the shortest path in a graph, through all vertices. Without boundary conditions, this is : min_{\sigma\in Perm(\mathbb{N}_n)}\sum_{i=1}^{N-1}a_{\sigma(i),\sigma(j)} where there are n cities, and the distance between cities i and j is a_{ij}..and \sigma is just a permutation of the cities order.
2) coin-changing problem : the less coins you need to make up to a given sum S in a given coin system \left(v_i\right)_{i=1}^k : \tilde{\min}_{n} \left(\sum_{i=1}^n v_{f(i)}=S\right) where f : \mathbb{N}_n\rightarrow \mathbb{N}_k with v_f(i) is giving the index of the ith coin needed. \tilde{min} gives the minimal n, If n does not exist, then it is \infty.
I thinnk there should exist a forumla betwen those two problems : the coin system is equivalent to the distances between cities (kind of constraint), but I cannot firgure it out..could somebody help ?