湘潭大学软件工程算法设计与分析考试复习笔记（二）

回顾

湘潭大学软件工程算法设计与分析考试复习笔记（一）

前言

现在接着昨天的复习。今天复习一下，把人机交互的实验二综述写一下，把实验三的 bug 改一下。

模拟退火

在这里插入图片描述
最后热情被消耗殆尽，是这意思吗哈哈。这个模拟退火建议是看视频学一下，感觉看公式比较难。我之前学了一下。湘潭大学软件工程算法设计与分析实验-模拟退火算法

课件里面说的 TSP 是啥问题。还有课件怎么成这样了。
在这里插入图片描述

TSP（Traveling Salesman Problem），即旅行商问题，是数学领域中著名的问题之一。该问题假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求所选的路径路程为所有路径中的最小值。TSP问题可大致分为对称TSP问题和非对称TSP问题。对称TSP问题中，城市u到城市v的距离与城市v到城市u的距离是一样的，其在图中的体现就是对称TSP问题的输入一般是无向图；而非对称TSP问题的输入往往是有向图。TSP问题在图论中的描述是：其输入是一个边带权的完全图，目标是找一个权值和最小的哈密顿回路。

结合第六章课件，发现应该是这个问题。后面不知道在说啥了，感觉模拟退火知道这个大概的意思，还有一定的概率选择一个不那么优的解就好了。那个概率就是这个公式
在这里插入图片描述

遗传

这个有同学实验讲了这个，但是我是完全不知道，之前粗略看了一下他们讲的代码，不出所料，完全看不懂哈哈哈。

瞎子爬山陷入局部最优我感觉就是贪心策略。读者怎么看？

在这里插入图片描述
感觉完蛋了，每到关键的地方课件就看不清楚了。遗传算法就是模拟生物进化，模拟退火是模拟一个高温的系统降温。感觉这两个本质上比较接近，都是在一个缓慢的过程中找到答案。

人工神经网络

神经元让我想起了以前一些非常熟悉的生物知识，现在只剩下一个大概的印象了。
在这里插入图片描述

算法题真的是与时俱进，结合实际啊，之前写的一个算法题就一模一样的背景知识。xtu oj 神经网络

后面的感觉不是专门研究这个的也看不懂。

回溯

在这里插入图片描述
刷新了好几遍，原来是本来就没有课件。还以为是网络的问题。回溯法有两个小节。另外我现在还是复习第一个题型。我这个其实把所有课件看一遍的压力都比较大，然后看一遍也记不住哇，不会寄寄了吧。

看课件之前，我写一下我现在对于回溯法的理解。就是给定一棵二叉树，我们按照一定的规则去寻找节点，假设找到了叶子节点，就回溯，然后找到了不符合条件的节点，就剪枝。撞破南墙再回头，或者在合适的地方掉头。

回溯概述

深度优先搜索就是回溯。我感觉现在自己写不出深搜，广搜，还有一个什么排序，拓扑排序，我应该都写不出来。
在这里插入图片描述
和我之前的印象是一样的，就是一个深度优先搜索加上一个剪枝，剪枝可以加快我们的搜索。

课件太乱了，自己刚好找一个借口粗略地看，但是之后可能要重新看一遍，哭。

数的全排列

这个其实就是一个算法题。好像是深搜的模板题。

#include<bits/stdc++.h>using namespace std;const int N=10;
//保存每一位上面的数字
int path[N];
//保存是否使用过
bool st[N];
int n;void dfs(int u)
{//从 0 开始搜，搜到 n 表示结束//等到 n-1 的时候就是结束了
//	if(u==n)
//	{
//		//输出每一位的答案
//		for(int i=0;i<n;i++)
//			cout<<path[i]<<" ";
//		cout<<endl;
//		return;
//	}if(u>n){for(int i=1;i<=n;i++)cout<<path[i]<<" ";cout<<endl;return;}for(int i=1;i<=n;i++){if(!st[i]){path[u]=i;//表示用过了st[i]=true;//往下搜dfs(u+1);//恢复现场st[i]=false;}}
}int main()
{cin>>n;//从 0 开始搜，其实区别就是 dfs 的时候的结束条件//假设从 0 开始搜，到 u==n 的时候结束//假设从 1 开始搜，到 u>n 的时候结束//dfs(0);dfs(1);return 0;
}

之前写过好多遍，现在好像又忘掉了。

n 皇后问题

#include<bits/stdc++.h>using namespace std;const int N=11;char g[N][N];
//对角线要存两倍的长度
bool row[N],dg[N*2],udg[N*2];
int n;void dfs(int u)
{if(u==n){for(int i=0;i<n;i++)puts(g[i]);puts("");return;}for(int i=0;i<n;i++)//i 表示的是 y //u 表示的是 x//括号里面的数值表示的是截距//y=x+b,y=-x+b//b=y-x,b=y+x,因为数组下标的数值不可以为负数//所以前面部分的下标加上 n//y-x+n y+x//i-u+n i+u//三个判断条件相当于剪枝if(!row[i]&&!dg[u+i]&&!udg[i-u+n]){g[u][i]='Q';row[i]=dg[u+i]=udg[i-u+n]=true;dfs(u+1);//恢复现场g[u][i]='.';row[i]=dg[u+i]=udg[i-u+n]=false;}
}int main()
{cin>>n;//初始化地图for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]='.';dfs(0);return 0;
}

现在也忘了。

TSP

这个好难，课件上面全是代码，看不下去，这种没有题可以测试，然后知识密度也大。

01背包

这个之前的实验讲了一遍，现在印象还比较深刻，把实验的代码贴在这儿。

//回溯
#include <iostream>
using namespace std;
#define N 100
int n;
double W;
double maxv;
int ans[N];  //全局最优解
int vis[N];double w[N], v[N];void BackTrack(int index, double tw, double tv) {// 不能超出重量限制if (tw > W) return;// 且不越界if (index == n) {if (tv > maxv) {   //更新最优解for (int k = 0; k < n; ++k)ans[k] = vis[k];maxv = tv;}return;}// 选第i个物品vis[index] = 1;BackTrack(index + 1, tw + w[index], tv + v[index]);// 不选第i个物品vis[index] = 0;BackTrack(index + 1, tw, tv);
}int main() {cout << "输入物品种数和背包承受的最大重量:" << endl;cin >> n >> W;for (int k = 0; k < n; ++k) {cout << "依次输入第" << k + 1 << "个物品的重量和价值: " << endl;cin >> w[k] >> v[k];}maxv = 0.0;BackTrack(0, 0.0, 0.0);cout << "所选物品为：" << endl;for (int k = 0; k < n; ++k)if (ans[k])cout << k + 1 << "\t";cout << endl << "总价值为:" << maxv << endl;
}