Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Optimization problems

  1. Nov 23, 2005 #1
    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 : [tex] min_{\sigma\in Perm(\mathbb{N}_n)}\sum_{i=1}^{N-1}a_{\sigma(i),\sigma(j)}[/tex] where there are [tex]n[/tex] cities, and the distance between cities [tex]i[/tex] and [tex]j[/tex] is [tex]a_{ij}[/tex]..and [tex]\sigma[/tex] 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 [tex] \left(v_i\right)_{i=1}^k[/tex] : [tex]\tilde{\min}_{n} \left(\sum_{i=1}^n v_{f(i)}=S\right)[/tex] where [tex] f : \mathbb{N}_n\rightarrow \mathbb{N}_k [/tex] with [tex]v_f(i)[/tex] is giving the index of the ith coin needed. [tex]\tilde{min}[/tex] gives the minimal n, If n does not exist, then it is [tex]\infty[/tex].
    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 ?
    Last edited: Nov 23, 2005
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?