本文主要是介绍分支限界法：运输问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用分支定界算法求以下问题：
某公司于乙城市的销售点急需一批成品，该公司成品生产基地在甲城市。
甲城市与乙城市之间共有n座城市，互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵M1给出。
每段公路均由地方政府收取不同额度的养路费等费用，具体数额由矩阵M2给出。
请给出在需付养路费总额不超过1500的情况下，该公司货车运送其产品从甲城市到乙城市的最短运送路线。
具体数据参见文件：
M1.txt：各城市之间的公路连通情况及每段公路的长度矩阵（有向图）；甲城市为城市Num.1，乙城市为城市Num.50。
M2.txt：每段公路收取的费用矩阵（非对称）。
CSDN模仿别人的版本
先用弗洛伊德算法求出所有顶点之间的最短路径和最短花费。
先对0节点进行考察，vis置1，如果当前最短路径总长+待考察节点到49的最短路径 > 已知最短路径总长，或者当前最少花费+待考察节点到49的最短花费 >1500，就不扩展这个节点，直接return。
否则对剩下每个未被考察过的节点进行考察，并将其添加至cur_path_list。
如果此时到了49号，也需要判断剪枝，因为在k < 49判断剪枝的时候，当前最短路径总长+待考察节点到49的最短路径，即最好的情况都比已有的糟糕，然而当k == 49的时候，总路径长度是上一轮的当前最短路径总长 + 上一轮的k对应的dist[k][49]，你不能保证“上一轮的当前最短路径总长 + 上一轮的k对应的dist[k][49]”一定小于等于已有情况。
凡是进入dfs函数的k，都已经在cur_path_list里面了。（这点很重要，因为每次扩展节点的时候，有一行是cur_path_list[cur_path_number++] = i;）
我的做法，速度快的原因主要是在扩展的时候，判断了子节点可不可达，即应该不等于9999。
#include <stdio.h>
#include <string.h>int dist[50][50];
int cost[50][50];
int minDist[50][50];
int minCost[50][50];int cur_path_list[50];
int cur_path_number;int best_path_list[50];
int best_path_number;
int best_path_length;
int best_path_cost;
int vis[50];void init()
{int i,j;FILE *fp = fopen("m1.txt", "r");if(fp){for(i = 0; i < 50; i++){for(j = 0; j < 50; j++){fscanf(fp, "%d", &dist[i][j]);minDist[i][j] = dist[i][j];}fscanf(fp,"\n");}fclose(fp);}fp = fopen("m2.txt", "r");if(fp){for(i = 0; i < 50; i++){for(j = 0; j < 50; j++){fscanf(fp, "%d", &cost[i][j]);minCost[i][j] = cost[i][j];}fscanf(fp,"\n");}fclose(fp);}memset(vis, 0, sizeof(vis));memset(cur_path_list, 0, sizeof(cur_path_list));memset(best_path_list, 0, sizeof(best_path_list));cur_path_list[0] = 0;cur_path_number = 1;best_path_list[0] = 0;best_path_list[1] = 49;best_path_number = 2;best_path_length = dist[0][49];best_p这篇关于分支限界法：运输问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
