算法教材 · 蛮力法与暴力法 · 旅行商问题
发布时间
阅读量：
阅读量
-
算法说明
旅行商问题属于NP难问题范畴，本文采用穷举法进行求解。具体过程为：以初始城市为起点，依次访问所有其他城市后返回起点，即对中间城市的所有可能排列方式进行计算，并得出每种路径对应的总权重，最终选择其中最小的值作为最优解。在实现过程中，所涉及的排列组合操作通过STL库中的next_permutation()函数完成。- 代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 4
#define min(a, b) (a) > (b) ? (b) : (a)
int main() {
int dis[maxn + 1][maxn + 1] = { //路径
{0, 0, 0, 0, 0},
{0, 0, 2, 5, 7},
{0, 2, 0, 8, 3},
{0, 5, 8, 0, 1},
{0, 7, 3, 1, 0}
};
int a[maxn - 1];
for(int i = 0; i < maxn - 1; i++) { //待排列的城市
a[i] = i +全部评论 (0)
还没有任何评论哟~