T Naughton, NUIM
Back to SE307 home

Lab 7 - Simple solutions to intractable problems

This lab is based on the principle that exhaustive searches are often the simplest programs guaranteed to solve a particular problem. First, you'll encounter a provably intractable problem, the Towers of Hanoi puzzle. Next, you'll write the main component of a solution to an NP-complete problem: the decision-form of the travelling salesman problem. The latter problem can be stated as follows. Given a fully-connected weighted graph and a positive integer k, is there a tour of the graph of length less than or equal to k that visits each node exactly once? By the end of the lab you should see no contradiction at all in the fact that conceptually simple solutions exist for hard problems.

So, first, here is a cute look at the Towers of Hanoi puzzle.

Problem 7.A Write a program to solve the Towers of Hanoi puzzle (using the code given in the slides) and write down approximately how long it takes (in minutes) to run for inputs of size 20, 40, 60, 80.

Problem 7.B Write a function in your favourite programming language to list all possible tours of a particular graph with n vertices (nodes). The nodes in the graph are identified by a unique letter in {a, b, ..., z}. Your function takes a char array of length n and prints each permutation to the screen. Write a main() to call and test your function. For example, if the array [f, l, k] is passed to your function, then your function should print the following lines (in any order you want) to the screen:
f l k
f k l
l k f
l f k
k f l
k l f

Problem 7.C How many permutations are there for a graph of n vertices?

Problem 7.D Let us change the problem slightly. Imagine that every graph contains at least two vertices, and that vertices a and b are in every graph. How many possible tours are in a fully-connected graph of n vertices where each tour begins at a and ends at b?

Problem 7.E What else is required, in addition to your function from 7.B (or a modified version of it), to completely solve the decision form of the travelling salesman problem? (The input to the problem is a list of vertices, a list (usually in matrix form) of the weights between pairs of vertices, and a positive integer k.)