Traveling Salesman in polynomial time

Posted by Andres on Stack Overflow See other posts from Stack Overflow or by Andres
Published on 2010-04-01T17:33:54Z Indexed on 2010/04/01 17:43 UTC
Read the original article Hit count: 671

Filed under:

code-golf

|

traveling-salesman

|

np-complete

|

april-fools

Problem Description:

Write a program in any language with the shortest number of characters that solves the following problem:

Given a collection of cities and the cost of travel between each pair of them, find the cheapest way of visiting all of the cities and returning to your starting point. All solutions must take at most polynomial time.

Input will be in the form of a text file named simply "i". The text file will contain data in the following format:

city1# city2# cost$
cityA# cityB# cost$
...

Each element in the file is separated with a space, and there is a newline at the end of every line.

Code count does not include whitespace.

Solutions that take longer than polynomial time to find will not be accepted

© Stack Overflow or respective owner

Related posts about code-golf

Code Golf: Collatz Conjecture

as seen on Stack Overflow - Search for 'Stack Overflow'
Inspired by http://xkcd.com/710/ here is a code golf for it. The Challenge Given a positive integer greater than 0, print out the hailstone sequence for that number. The Hailstone Sequence See Wikipedia for more detail.. If the number is even, divide it by two. If the number is odd, triple… >>> More
Code Golf - p day

as seen on Stack Overflow - Search for 'Stack Overflow'
The Challenge The shortest code by character count to display a representation of a circle of radius R using the *character, followed by an approximation of p. Input is a single number, R. Since most computers seem to have almost 2:1 ratio you should only output lines where y is odd. The approximation… >>> More
Code Golf - PI day

as seen on Stack Overflow - Search for 'Stack Overflow'
The Challenge The shortest code by character count to display a representation of a circle of radius R using the *character. Followed by an approximation of pi Input is a single number, R Since most computers seem to have almost 2:1 ratio you should only output lines where y is odd. The approximation… >>> More
Code Golf: Triforce

as seen on Stack Overflow - Search for 'Stack Overflow'
This is inspired by/taken from this thread: http://www.allegro.cc/forums/thread/603383 The Problem Assume the user gives you a numeric input ranging from 1 to 7. Input should be taken from the console, arguments are less desirable. When the input is 1, print the following: *********** *********… >>> More
Code Golf: Tic Tac Toe

as seen on Stack Overflow - Search for 'Stack Overflow'
Post your shortest code, by character count, to check if a player has won, and if so, which. Assume you have an integer array in a variable b (board), which holds the Tic Tac Toe board, and the moves of the players where: 0 = nothing set 1 = player 1 (X) 2 = player 2 (O) So, given the array b… >>> More

Related posts about traveling-salesman

A detail question when applying genetic algorithm to traveling salesman

as seen on Stack Overflow - Search for 'Stack Overflow'
I read various stuff on this and understand the principle and concepts involved, however, none of paper mentions the details of how to calculate the fitness of a chromosome (which represents a route) involving adjacent cities (in the chromosome) that are not directly connected by an edge (in the graph)… >>> More
Traveling Salesman in polynomial time

as seen on Stack Overflow - Search for 'Stack Overflow'
Problem Description: Write a program in any language with the shortest number of characters that solves the following problem: Given a collection of cities and the cost of travel between each pair of them, find the cheapest way of visiting all of the cities and returning to your starting point.… >>> More
Using Traveling Salesman Solver to Decide Hamiltonian Path

as seen on Stack Overflow - Search for 'Stack Overflow'
This is for a project where I'm asked to implement a heuristic for the traveling salesman optimization problem and also the Hamiltonian path or cycle decision problem. I don't need help with the implementation itself, but have a question on the direction I'm going in. I already have a TSP heuristic… >>> More
Traveling Salesman - Nearest Neighbor vs Genetic DEATHMATCH

as seen on Stack Overflow - Search for 'Stack Overflow'
Over the last few days I have noted a few web sites that demonstrated TS solution using genetic algorithms. I am looking for your opinion which is better for this particular problem. Heuristics vs Genetic. By better, I mean will yield a shorter/lower cost path. Explain why you feel the way that… >>> More
Suggested GA operators for a TSP problem?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm building a genetic algorithm to tackle the traveling salesman problem. Unfortunately, I hit peaks that can sustain for over a thousand generations before mutating out of them and getting better results. What crossover and mutation operators generally do well in this case? >>> More