Azzera filtri
Azzera filtri

Generate a branch and bound tree

15 visualizzazioni (ultimi 30 giorni)
Stefan Zeiter
Stefan Zeiter il 1 Mag 2018
Modificato: Stefan Zeiter il 2 Mag 2018
Hey
I developed a script to solve the travelling salesman problem (TSP) using the branch and bound algorithm.
As a result the script visualizes a map (attached) with the shortest travelling way.
Is it also possible to generate a branch and bound tree? I think this would be also a nice way to presentate the result.
I stored the optimal way in an array. For example the optimal way for a 5 city problem is: 1 => 2 => 3 => 4 => 5
Now I would like the generate a tree. The number of possible branches decrease with every additional city, because every city can be visited just once. My expected outcome tree is also attached.
I hope someone can help me.
Best

Risposte (1)

Mary Fenelon
Mary Fenelon il 2 Mag 2018
A tree is a graph so you could visualize it with MATLAB graph objects . There's also a treeplot function.
  1 Commento
Stefan Zeiter
Stefan Zeiter il 2 Mag 2018
Modificato: Stefan Zeiter il 2 Mag 2018
Thanks for your answer.
The treeplot function looks interesting. When I try the Matlab example it works properly.
treeplot([2 4 2 0 6 4 6])
But when I use my own array where I stored the order of the city then it does not work.
>> treeplot([1 2 3 4 5 1])
Error using treelayout (line 28)
Bad vector of parent pointers.
Error in treeplot (line 18)
[x,y,h]=treelayout(p);
When I have 5 cities then I expect after my first node (inital city) 4 further nodes. After my second node I expect 3 further nodes. And so on...
The number of possible cities decreases with every node because every city can be visited just once.
I hope you can help me.
Best

Accedi per commentare.

Categorie

Scopri di più su Graph and Network Algorithms in Help Center e File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by