Hello!
I have to write an algorithm as a course task that solves symmetric TSP problem with branch and bound method by:
1. breath-first search, using priorityqueue for best before branch and bound
2. depth-first search, by replacing priorityqueue with stack
3. make an animation about it
I have googled for it, I have somebodys Java code that solves it, but some classes are missing. I have a book that describes the solution by using maths (it is difficult for me to understand after the first page).
So far I only have written a recursive code that checks all possible solutions by depth search. I understand how that code works, but for a few days I have tried to figure out how the branch and bound works. So far I only understand how to calculate bound.
As a next task I have to make an animation about TSP problem that would help the next years students to better understand the problem and solution. Since I'm a bit familiar with JME, my current idea is to make the animation with JME, instead of using swing. Just a bunch of vertices with edges in 3d space and then drawing green lines to display how the shortest path is being searched, displaying bounds and distances and so on.
Do You know some good video, animation or text about TSP?
Do You have some better ideas for the animation that would really benefit from 3d scenegraph?
Hello Henri,
first of all I wouldn't trust somebody else's java code like that, I've seen it fail very often (be it because the code was erratic and I needed to rewrite it or in the form of classmates who did manage to find proper code getting busted).
Unfortunatly there's no text I can link you to as my own reading material about the subject was quite awefull. I'm a little confused about branch and bound, not exactly sure what those are (might be because of language differences). I might be able to help you if you'd explain a bit about those.
As far as graphic representation goes you could make a 3d globe with points on it to represent location on "earth" were the salesman needs to go. This (and any other 3d appliances I can think of) might bring some additional complication to the project though which you will not experience with a simple 2D visualization.
If you really want to impress with the visuals I'd go with a sphere with points, an airplane travellig in between them and counters for the ammount of money spent for each solution as a GUI on the side.
Hei, tx for the reply.
Meanwhile I have presented my task, the recursive code only that I made. The teacher now allows me to take exam.
By branch and bound i meant a method of solving the problem by calculating the bound at each node. Bound is something like the shortest possible path from that node til the end. I never exactly understood it. And branching is maybe making a choice based on the bounds at a cetain level in the search tree.
Thanx for offering help about the issue, but I’m gonna pass the exam now in January and do the course again in autumn so its ok.
You are definately right about more complication with 3d. I started off making a 3d visualization of the complete search tree (all possible paths displayed as a tree). So I wasted my time and energy on figuring out how to draw the tree procedually symmetrically:
This is complete search tree basically that represents all possible paths with 5 cities like:
1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
…
1,5,2,3,4
1,5,2,4,3
1,5,3,2,4
1,5,3,4,2
a total of !(5-1) = 24 different paths.
So when it came to the showdown, this was all I had to show and didnt have any animations
The plane flying from city to city is an excellent idea for visualization. I might just do that next autumn when I take the course again.
Tx for the idea.