当前位置: 首页 > article >正文

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

回顾

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

前言

现在接着昨天的复习。今天复习一下,把人机交互的实验二综述写一下,把实验三的 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;
}

动态规划

后记

明天接着复习,现在看的比较粗糙,现在还是在看前面的十分的算法的大致理解,应该能稍微写点东西这个题型就能拿到分,后面可能更重要的是代码填空,时间复杂度分析啥的,那个分值比较多。


http://www.kler.cn/a/404862.html

相关文章:

  • 音视频pts/dts
  • 【CVE-2024-9413】SCP-Firmware漏洞:安全通告
  • 实验室管理效率提升:Spring Boot技术的力量
  • 基于rkmedia的视频解码
  • 微信小程序组件详解:bottom 和 image 组件的基本用法
  • .NET9 - 新功能体验(一)
  • 【FFmpeg】FFmpeg 内存结构 ③ ( AVPacket 函数简介 | av_packet_ref 函数 | av_packet_clone 函数 )
  • 【Unity】网格系统:物体使用网格坐标定位
  • ceph 18.2.4二次开发,docker镜像制作
  • 【保姆级图文教程】QT下载、安装、入门、配置VS Qt环境
  • C++20 协程入门
  • QT+osg+osgearth显示一个地球(进阶)
  • 《Java核心技术 卷I》链表
  • 多目标优化算法:多目标吸血水蛭优化算法(MOBSLO)求解DTLZ1-DTLZ9,提供完整MATLAB代码
  • 集合卡尔曼滤波(Ensemble Kalman Filter),用于二维滤波(模拟平面上的目标跟踪),MATLAB代码
  • 机器学习——数据隐私与安全学习
  • 排序算法:直接插入排序,希尔排序,选择排序,快速排序,堆排序,归并排序
  • 【IEEE独立出版 |往届均已成功检索】第八届大数据与应用统计国际学术研讨会(ISBDAS 2025)
  • C#核心(10)拓展方法
  • 机器学习:智能技术的未来
  • Vue_Router权限控制:不同角色显示不同路由
  • MySQL基础大全(看这一篇足够!!!)
  • 解决.DS_Store 在项目一致无法排除,.gitignore里也不生效
  • C++ 网络编程:打造多线程 TCP 服务器,同时服务多个客户机!
  • Qt-常用的按钮控件 QPushButton QRadioButton QCheckBox
  • Kadane 算法 二维 详解