|
发表于 2012-5-20 19:14:05
|
显示全部楼层
分支限界(Branch and Bound)算法是一种带剪枝技巧的搜索算法。当应用在 TSP 时,分支限界法的最大优势是,它一定能找到最优解。
我这代码所带的 3 个算例,还是上次 MMAS 的那 3 个,这可以验证 MMAS 确实有一定概率能找到最优解的。比如,第三个算例的最优解就是 1185485。当然,MMAS 更多时候找到的是次优解 1187399。
注意,分支限界算法处理有向图和无向图的方式是不一样的,这一点我在算例的代码注释中已经说明了!
下面介绍一下分支限界算法的基本概念,以方便大家阅读代码。
行(列)归约 —— 用一行(列)的最小数据减去行(列)中的各个数据。显然,经过归约后,行(列)中最小数据所在的位置必定为零!
行(列)归约数 —— 用来归约一行(列)的数据。显然,行(列)归约数就是该行(列)最小的数据。
归约矩阵 —— 每一行每一列都归约过的矩阵。显然,归约过的矩阵每一行每一列都至少有一个零。
归约矩阵中,那些数值为零的位置,就是那些有可能成为 TSP 的边。那么,我们该如何选择呢?
很简单,我们把那些零逐个挖去,然后重新对这一行和这一列进行归约,则行归约数和列归约数之和,就是不选择这条边的“代价”。显然,我们应该选择代价最高的边。
做出选择后,下一步自然就分裂成选择边和不选择边这两种情况了。在代码中,我把这两种情况分别成为“左节点(left node)”和“右节点(right node)”。
然后,又重复进行归约和选择,直至得到最优解为止!
以下是算法的主体框架:- void fuck_tsp()
- {
- implement_project_branch_bound();
- }
- void implement_project_branch_bound()
- {
- initialize();
- struct _node *node = tsp.next;
- while( node->order_matrix > 2 )
- {
- struct _node *left = construct_left_node();
- struct _node *right = construct_right_node();
- dequeue();
- enqueue( left );
- enqueue( right );
- node = tsp.next;
- }
- output();
- clear();
- }
- struct _node *construct_left_node()
- {
- struct _node *node = construct_node();
- struct _node *backup = tsp.next;
- tsp.next = node;
- set_adjacency_list();
- set_signpost();
- decrease_order();
- node->lower_limit += reduce_array();
- search_candidate();
- if( 2 == node->order_matrix ) // Well, we find a solution.
- {
- if( 0 == node->cost[ 0 ][ 0 ] )
- {
- node->potential_edge.row = 0;
- node->potential_edge.column = 0;
- set_adjacency_list();
- node->potential_edge.row = 1;
- node->potential_edge.column = 1;
- set_adjacency_list();
- }
- else
- {
- node->potential_edge.row = 0;
- node->potential_edge.column = 1;
- set_adjacency_list();
- node->potential_edge.row = 1;
- node->potential_edge.column = 0;
- set_adjacency_list();
- }
- }// if( node->order_matrix )
- tsp.next = backup;
- return node;
- }
- struct _node *construct_right_node()
- {
- struct _node *node = construct_node();
- struct _edge *potential_edge = &( node->potential_edge );
- copy_node( node, tsp.next );
- struct _node *backup = tsp.next;
- tsp.next = node;
- node->cost[ potential_edge->row ][ potential_edge->column ] = NO_ROUTE;
- node->lower_limit += reduce_array();
- search_candidate();
- tsp.next = backup;
- return node;
- }
复制代码
Branch and Bound.rar
(30.71 KB, 下载次数: 2068)
|
|