Generate a branch and bound tree

33 次查看（过去 30 天）
Stefan Zeiter
Stefan Zeiter 2018-5-1
编辑： Stefan Zeiter 2018-5-2
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

请先登录，再回答此问题。

回答（1 个）

Mary Fenelon
Mary Fenelon 2018-5-2
A tree is a graph so you could visualize it with MATLAB graph objects . There's also a treeplot function.
  1 个评论
Stefan Zeiter
Stefan Zeiter 2018-5-2
编辑：Stefan Zeiter 2018-5-2
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

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by