← Back

March 21, 2008

#399: Travelling Salesman Problem

Travelling Salesman Problem

[[There is a linked black web, with a path in red]]

Brute-force solution:

O(n!)

[[The web continues in this one. A man with a hat and a case is drawing it]]

Dynamic programming algorithms: O(n^2 2^n)

[[Another man, with a hat too, is at a computer, looking back over the chair]]

Selling on eBay: O(1)

Computer salesman: Still working on your route?

Drawing salesman: Shut the hell up.