作者:n大牙 | 来源:互联网 | 2023-05-17 20:54
知识点:分支定界;Dijkstra;c++读取txt文件到二维数组这个题目是北航研究生算法课的,因为以前主要写java,用c++写作业的时候遇到了一些读文件啊,深度优先遍历图的问题
知识点:分支定界; Dijkstra; c++读取txt文件到二维数组
这个题目是北航研究生算法课的,因为以前主要写java,用c++写作业的时候遇到了一些读文件啊,深度优先遍历图的问题啥的,所以记录下来。
题目:
Assignment 2
用分支定界算法求以下问题:
某公司于乙城市的销售点急需一批成品, 该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座城市,互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的长度由矩阵M1 给出。每段公路均由地方政府收取不同额度的养路费等费用, 具体数额由矩阵 M2 给出。请给出在需付养路费总额不超过 1500 的情况下,该公司货车运送其产品从甲城市到乙城市的最短运送路线。
具体数据参见文件:
M1.txt: 各城市之间的公路连通情况及每段公路的长度矩阵(有向图); 甲城市为城市 Num.1,乙城市为城市 Num.50。
M2.txt: 每段公路收取的费用矩阵(非对称)。
点此下载可执行程序和源代码以及m1.txt,m2.txt
- 主要思路:
- 遍历:利用栈结构,通过深度优先搜索遍历路径
- 定界:每一个最短路径值更小的可行解确定了新的下界
- 剪枝:先利用Dijkstra算法计算每个城市到目的城市的最短路径和最小花费,当算法运行到某个城市后,计算在栈里的城市的路径长度 + 这个城市到目的城市的最短路径,以及在栈里的城市的路径花费 + 这个城市到目的地的最小花费, 与当前最优的可行解以及约束条件进行比较,从而达到剪枝的目的
平心而论,代码的一般……
代码:
#include "stdafx.h"
#include
#include
#include
#include
using namespace std;
#define MAX_NODE 60
#define MAX_INT 9999
#define MAX_COST 1500
int n1, n2;
deque<int> queueMinPath;
int minPath;
int costOfMinPath;
int main(int argc, char* argv[]) {
clock_t startTime, endTime;
startTime = clock();
cout <"程序开始运行"
<
int** readTxtToArrayWithoutKnowRowOrColumn(const char* strPath);
void findPathWithDFS(int **m1, int **m2, int fn, int tn);
int pIn[MAX_INT] = { 0 };
int** m1 = 0, **m2 = 0;
cout <<"从txt文件读取数据(请把txt文件和可执行文件放在同一路径下):" <
m1 = readTxtToArrayWithoutKnowRowOrColumn("m1.txt");
m2 = readTxtToArrayWithoutKnowRowOrColumn("m2.txt");
cout <<"行数: " <", 列数: " <
for (int i = 0; i for (int j = 0; j if (m1[i][j] == MAX_INT) {
m2[i][j] = MAX_INT;
}
}
}
minPath = MAX_INT;
findPathWithDFS(m1, m2, 0, n1 - 1);
cout <<"满足条件的最短路径长度为: " < cout <<"满足条件的最短路径的花费为: " < cout <<"最短路径为: " < for (int is = 0; is cout <<"\t" <1;
}
cout <
cout <<"程序运行结束" < endTime = clock();
cout <<"总共耗时: " <<(double)(endTime - startTime) / CLOCKS_PER_SEC <<" 秒" <
cout <<"按 即可退出程序" < getchar();
return 0;
}
void findPathWithDFS(int **m1, int **m2, int fn, int tn) {
int calculateShortestByDijkstra(int **m1, int fn, int tn);
int p1[MAX_NODE] = { 0 }, c1[MAX_NODE] = { 0 };
int pMin = MAX_INT, cNow = MAX_INT;
cout <<"先用Dijkstra算法求出每个城市到目的城市的最短路径和最小花费" <
for (int i = 0; i p1[i] = calculateShortestByDijkstra(m1, i, n1 - 1);
}
for (int i = 0; i c1[i] = calculateShortestByDijkstra(m2, i, n1 - 1);
}
cout <<"再用分枝定界算法求满最大花费不超过" <"的最短路径" < deque<int> stackPathNode;
stackPathNode.push_back(fn);
int nPath[MAX_NODE] = { 0 };
nPath[fn] = 1;
int lastOut = -1;
int tag = 0;
int pathLengthNow = 0;
int pathCostNow = 0;
int nNow;
while (!stackPathNode.empty()) {
nNow = stackPathNode.back();
for (int i = 0; i if (nPath[i] == 1 || i <= lastOut || nPath[i] == 1)
continue;
if (m1[nNow][i]
if (pathLengthNow + p1[i] >= minPath || pathCostNow + c1[i] > MAX_COST) {
continue;
}
if (pathLengthNow + m1[nNow][i] >= minPath || pathCostNow + m2[nNow][i] > MAX_COST){
continue;
}
if (i == tn) {
minPath = pathLengthNow + m1[nNow][i];
costOfMinPath = pathCostNow + m2[nNow][i];
pathLengthNow = minPath;
pathCostNow = costOfMinPath;
stackPathNode.push_back(i);
queueMinPath = stackPathNode;
break;
}
else {
tag = 1;
stackPathNode.push_back(i);
nPath[i] = 1;
pathLengthNow += m1[nNow][i];
pathCostNow += m2[nNow][i];
lastOut = -1;
break;
}
}
}
if (tag == 0) {
lastOut = stackPathNode.back();
stackPathNode.pop_back();
if (stackPathNode.empty()) {
break;
}
nNow = stackPathNode.back();
nPath[lastOut] = 0;
pathLengthNow -= m1[nNow][lastOut];
pathCostNow -= m2[nNow][lastOut];
}
tag = 0;
}
}
int** readTxtToArrayWithoutKnowRowOrColumn(const char* strPath) {
int** a = new int*[MAX_NODE];
for (int i = 0; i a[i] = new int[MAX_NODE];
}
int nTmp = 0;
n1 = 0;
n2 = 0;
ifstream is(strPath);
if (!is) {
cout <<"open file error!" < }
else {
char p;
int num;
int j = 0;
while (is.get(p)) {
do {
if (p == '\n') {
n1++;
if (n2 == 0) {
n2 = nTmp;
}
j = 0;