Classic Intractable Problems

The Towers of Hanoi and Traveling Salesman problems

Two other examples of problems that can be modeled by algorithms but are not tractable when they are scaled up, because they take an inordinate amount of time, are the Towers of Hanoi and the Traveling Salesman problem.

Towers of Hanoi

"...is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.
No disk may be placed on top of a smaller disk.

"

From http://en.wikipedia.org/wiki/Tower_of_Hanoi

The image below shows how disks are moved from the left peg to the right one. The number of moves is 2ⁿ - 1, where n is the number of disks. The table below shows the moves for various numbers of discs. As can be seen the number of moves increases exponentially as n increases. Imagine that you could create a program that calculated a move every second, then for 40 discs the program would take 34,841 years (1,099,511,627,776 /60 /60 /24 /365.25). This makes the problem intractable for a large number of disks because it simply takes too long to run.

n	2ⁿ - 1
1	1
2	3
3	7
4	15
10	1,023
20	1,048,575
40	1,099,511,627,775
100	1,267,650,600,228,229,401,496,703,205,375

Following is an algorithm or method to move the disks from a left-most peg (A) to a right-most peg (C), using these pegs and a middle one (B). In other words using a three peg arrangement (A, B, and C).

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:

For starting with an even number of disks:

make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

For starting with an odd number of disks:

make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs B and C
repeat until complete

From http://en.wikipedia.org/wiki/Tower_of_Hanoi

The following link points to a Flash game where you can attempt to solve the puzzle for various numbers of disks: Owen's World

Traveling Salesman problem (TSP)

Background information

"The traveling salesman problem (TSP) is an old and well-studied problem in computer science. Given a collection of cities on a map, a salesman must make a tour of the cities, visiting each once, and returning to the city from which he started. Of all the ways that he could travel from city to city, he must find the one that requires him to travel the least total distance (our salesman is nothing if not frugal). Mathematically, we can view this form of the TSP as finding the minimum length closed path connecting a collection of points in the plane. The tour that results from a collection of cities tends to have some of the same density properties as the collection itself. In other words, in regions where cities are packed tightly together, you get a lot of traveling in tight little knots; where cities are spaced out, you tend to travel in long straightaways."

From http://www.cgl.uwaterloo.ca/~csk/projects/tsp/

The image above shows a salesman traveling between four cities. The number of possible routes is 4! or 4x3x2x1 = 24. This number includes the same route in reverse. E.g. ABCD -> DCBA. If there were 3 cities then the possibilities would be 3! or 3x2x1 = 6. The combinations are:

Combination	Then return to
ABC	A
ACB	A
BAC	B
CBA	C
BCA	B
CAB	C

A 'brute force' algorithm would work out all the possible combinations, adding up the distances for each. The smallest distance would then give the best route. The algorithm is of a type called brute force because it contains no thoughtful logic. It is relying on the processing power of the computer to work out all the combinations of cities to visit just once on a particular journey. Even with a powerful computer the task quickly becomes intractable as the number of cities grow. For instance, for 20 cities the number of possible routes is 20! or 2,432,902,008,176,640,000.

Attached to the bottom of this page is a BYOB 3.0.9 program that simulates the TSP. A recursive function is used to work out all the possible permutations for a given number of nodes. When the program is run, the user can see that as the number of nodes (lettered A, B, C, etc.) increases the time to compute all possible routes, starting and finishing at node s, increases sharply. For 6 nodes the time on a slowish computer is around 3 minutes, for 7 it is about 21.

However, more efficient algorithms have been devised. Click on this link to go to a site that features them, complete with demonstration Java applets:
TSP Algorithms in Action

Visit this website to see how, for instance, the TSP problem for the cities of Sweden has been solved (24,978 cities. Tour has length approximately 72,500 kilometers). The Traveling Salesman Problem

Finally, there are many TSP type problems in the real world. For example, how do you optimally load a container ship? How does a courier work out the best route to deliver their parcels? Programs have been devised to solve these problems.

This link points to some TSP games that can help get a better idea of the problem.

Big O notation

Note: a knowledge of Big O notation does not necessarily need to be known by students (or teachers!) for DT 2.44, but it is useful.

The complexity of a problem can be modeled using a mathematical notation called Big O. The mathematical formula above looks daunting, but the general ideas to do with Big O are easily understood. The following link points to a page that has more detail on them.

Measuring complexity using Big O

Additional Resources

The following link points to a Word document that gives an excellent rundown on Complexity and Big O: Complexity by Joe Carthy
The following link points to a web page/website set up by Lero in Ireland. It contains excellent resources to do with complexity. You will need to obtain a password to access Module 7, which is the one dealing with complexity. Be sure to check out the rest of the website which contains an excellent complete Computer Science course. It is recommended for students 15-16, but in my opinion some parts could be used with a younger age group.

Link: http://www.scratch.ie/module7

Screenshot of the relevant web page.

v.2

TSP.ypr

(323k)

joebloggsnz .,

18 May 2011 03:33

Comments