1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Problem Mapping

  1. May 27, 2013 #1

    Zondrina

    User Avatar
    Homework Helper

    1. The problem statement, all variables and given/known data

    I wasn't sure where to post this in particular, so I apologize if this is in the wrong section.

    I've been getting interested in the topic of problem mapping lately. I came across this problem while reading and I'm not quite sure if I have the right idea or not.

    The Question :

    A problem mapping means to create an instance of one problem out of the details (or data)
    of another. Suppose you wanted to prove that a solution to the Traveling Salesman Problem would provide a solution to the Hamilton Cycle problem.

    What is the correct mapping to use given the current information?

    2. Relevant equations

    Traveling Salesmen Problem ( TSP ) : http://gyazo.com/8944e64b668d3ea898662b083450d3d5

    Hamiltonian Cycle Problem ( HCP ) : http://gyazo.com/865cb36a67f72cbd9db71913e1a4e076

    3. The attempt at a solution

    Well, the way I thought about this was to recognize the important details of the problems and create a map from one problem to the other. The reason this would work is because we already have a solution to one of the problems, namely the TSP ( Barring its computational limits which are exponential, i.e ##2^n## ).

    So first things first. I map the cities to the nodes so ##C = V##.

    Now I need a way to tell the distances between the cities, but since I'm trying to map the problem, it reduces to finding distances between nodes. Suppose I denote this distance by ##d_{i,j} ≥ 0##. The distance between cities is zero only when we are already at the destination of course.

    So presume we have to travel some ##n > 0## number of nodes to reach our destination, and we have a distance function ##d(v_i, v_j)## which can tell the distance between two vertices which depend on ##i## and ##j##.

    Let :

    ##d(v_i, v_j) = 1## if ##v_i, v_j \in E##.
    ##d(v_i, v_j) = 2## if ##v_i, v_j \notin E##.

    We can now travel along each node and find a path with a positive distance to the destination.

    If the minimum length found from the start to the destination is ≤ n, then the set of cities has a Hamilton Cycle, otherwise it does not.

    So the proper mapping is :

    ##C = V##
    ##d(v_i, v_j) = 1## if ##v_i, v_j \in E##.
    ##d(v_i, v_j) = 2## if ##v_i, v_j \notin E##.
    ##B = n##
     
  2. jcsd
  3. May 27, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    That all seems reasonable.
     
  4. May 28, 2013 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    All this is pretty standard, and is well-discussed in computational complexity textbooks. Hamiltonian cycle and TSP are two instances of NP-Complete problems, and so are each reducible (in polynomially-bounded transformations) from one to the other. A lot of this stuff is presented in the old classic "Computers and Intractability: A Guide to the Theory of NP-Completeness", by M.R. Garey and D.S. Johnson, Freeman (1979). Or, you can Google "NP-Complete".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Problem Mapping
  1. Evaluation map problem (Replies: 18)

  2. Linear map problem (Replies: 1)

  3. Mapping / Set problem (Replies: 1)

Loading...