Friday, February 01, 2008

Dog solves the travelling salesman problem

The travelling salesman problem is classified as NP-hard and it is one of the most notorious problems in the class.

The task is to find the cheapest closed path connecting n=74 balloons, with well-defined costs for the transfer between any two pairs of balloons, and exact your revenge on them. (The tasks where the balloons explode and where they don't are equivalent.)
See P vs NP and NP-completeness
It's not easy because the solution space is 1/2 (n-1)! = 1/2 times 73! and it is widely believed that no algorithm that would only take time proportional to a power of n=74 can exist.



However a dog called Prof Simon, not to be confused with Jim Simons, has solved the problem for n=74 in t=47 seconds. Congratulations. ;-)

2 comments:

  1. > and it is widely believed that no
    > algorithm that would only take time
    > proportional to a power of n=74 can exist.

    That's not right. The issue is scaling
    of the computation time as the number
    increases, not the speed of computation
    for any particular number.

    ReplyDelete
  2. Jesus Christ, I am not silly. But let me assure you that 74 is a large enough number in this context and the actual required time for n=74 will almost exactly match the asymptotic expectation with n=74 substituted.

    ReplyDelete