制作网站的方法,浅析电商网站建设趋势,青岛西海岸新区城市建设局网站,合肥学校网站建设算法设计与分析实验3
计科210X 甘晴void 202108010XXX
目录 文章目录 算法设计与分析br实验31 用Dijkstra贪心算法求解单源最短路径问题问题重述证明模板#xff1a;Dijkstra算法代码验证算法分析 1【扩展】 使用堆优化的Dijkstra原因代码算法分析验证 2 回溯法求解…算法设计与分析实验3
计科210X 甘晴void 202108010XXX
目录 文章目录 算法设计与分析br实验31 用Dijkstra贪心算法求解单源最短路径问题问题重述证明模板Dijkstra算法代码验证算法分析 1【扩展】 使用堆优化的Dijkstra原因代码算法分析验证 2 回溯法求解0-1背包问题重述想法代码验证算法分析 3 实现题3-17 字符串比较问题问题重述想法代码验证算法分析 4 实现题5-1 子集和问题问题想法代码验证算法分析 4【扩展】 类似问题选数问题代码验证 参考文献实验感悟 1 用Dijkstra贪心算法求解单源最短路径问题
问题重述
给定一个带权有向图G(V, E),其中每条边的权是非负实数。另外给定V中的一个顶点称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。对于无向图的计算可以转化为对有向图的计算
证明
使用贪心算法完成该题。
输入的带权有向图是G(V, E)点集V{1,2, ……,n}顶点v是源。 c是邻接矩阵g[i][j]表示边(i,j)的权。 当(i,j)不在E 时g[i][j]是inf无穷大。
dist[i]表示当前从源到顶点i的最短路径长度。
d min(dist[k]g[k][u]) (k∈S)
需要证明 dist[u]d
1问题最优解可以以贪心选择开始
只经过S中的点计算到V-S中点的特殊最短路径V-S中选择使得这样的特殊路径最短的一点u加入S。
证明集合S初始只含v选择v直接相连的边权最短的一点u加入可以得到最优解。
分析现在只涉及第一点u那么只要证明了u得到的路径值是最短的。对于点u不存在g[v][k]g[v][u] k属于S因此dist[u]g[v][u]。
因此贪心选择开始可以得到最优解。
2最优子结构性质
证明v到u的最短路径为v-v1-v2-……-vi-u 那么v-v1-v2-……-vi是v到vi的最短路径。
设v-v1-v2-……-vi的路径长d1假设存在v到vi的另一条路径是最短路径长度为d2满足d2d1那么dist[u] d1 g[vi][u] d2g[vi][u]矛盾假设不成立。
问题具有最优子结构性质。
3步步贪心选择可以得到最优解
使用数学归纳法进行证明 令|S|sS集合的元素个数为s
①当s1时因为最优解可以由贪心选择开始成立
②假设sk时成立则sk1时
按贪心规则选择V-S中一点u且只经过S中的点到u的最短路径为d(v , u)对于所有i∈V-S知道d(v , u) 是d(v , i)中最小的。
假设u到v的最短路径经过了V-S的点且经过V-S中第一点为x因为最优子结构性质此前的路径长一定为d(v , x)设x到u的路径长为d’(x , u) dist[u]d(v , x) d’(x , u) d(v , u) 因为d’(x , u)0所以d(v , x) d(v , u)与d(v , u) 是d(v , i)中最小矛盾。
因此sk时成立步步贪心可以得到最优解。
简单来说若v到S外一点x的距离比v到S外一点u的距离更短那么x必定得更优先作为下一个扩展的对象否则就违反了步步贪心的策略形成了矛盾反证法。
模板Dijkstra算法
声明一个dis的数组来保存源点到其他点的最短路径长度最开始都设为无穷大以及一个已经找到最短路径的顶点的集合S。初始时我们将源点s到源点的路径长度置0dis[s] 0,将源点放进集合S中。找到源点所能到达的点v,w (v是源点能到的点w是源点到v点的路长)令dis[v] w。接下来从未在集合中的点的dis数值中选出最小的将这个点加入到集合S中。接下来要进行判断新加入的结点所能到达的点的路径长度是否小于dis数组中的数值如果小于则将dis进行数值更新。重复34操作直到S中包含了所有点。
图示如下 图片来源于网络CSDN大佬
示例读入因为是按照有向图来做的所以每条边要读两遍
7 14
1 7 2
1 5 9
1 6 5
2 6 4
3 4 3
7 3 1
7 5 6
7 1 2
5 1 9
6 1 5
6 2 4
4 3 3
3 7 1
5 7 6代码
#include iostream
#include cstring
using namespace std;const int N 510;
int n, m;
int g[N][N];// 邻接矩阵
int dist[N];// 距离
bool st[N];// 是否已经确定了最短路径int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;// 初始化第一个节点for(int i 0; i n - 1; i)// 循环n - 1次{int t -1;// 找最小节点for(int j 1; j n; j){if(!st[j] (t -1 || dist[j] dist[t])){t j;}}st[t] true;// 更新其他节点for(int j 1; j n; j){dist[j] min(dist[j], dist[t] g[t][j]);}}if(dist[n] 0x3f3f3f3f) return -1;else return 0;
}int main()
{memset(g, 0x3f, sizeof g);cin n m;int a, b, c;while(m--){cin a b c;g[a][b] min(g[a][b], c);}if (dijkstra() -1) couterrorendl;else for(int i 1; i n; i) coutdist[i] ;return 0;
}
验证
由于洛谷的单源最短路径问题对算法要求较高至少得是经过堆优化的Dijkstra故没有进行在线测评。
就对上面那张图进行验证
示例读入因为是按照有向图来做的所以每条边要读两遍
7 14
1 7 2
1 5 9
1 6 5
2 6 4
3 4 3
7 3 1
7 5 6
7 1 2
5 1 9
6 1 5
6 2 4
4 3 3
3 7 1
5 7 6运行结果如下 算法分析
时间复杂度O(n^2)双重循环。
空间复杂度O(n^2)使用邻接矩阵存储有向图。
1【扩展】 使用堆优化的Dijkstra
原因
如果是稀疏图使用邻接矩阵存储过于浪费而且寻找最小边的时候代价太大。故改用优先队列来存储最小的边。
代码
#include iostream
#include cstring
#include queueusing namespace std;typedef pairint, int PII;//分别表示距离和节点const int N 150010;int n, m;int h[N], e[N], ne[N], w[N], idx;
bool st[N];
int dist[N];void add(int a, int b, int c)
{e[idx] b;w[idx] c;ne[idx] h[a];h[a] idx;
}int dijkstra()
{memset(dist, 0x3f, sizeof dist);priority_queuePII, vectorPII, greaterPII pq;pq.push({0, 1});dist[1] 0;while(pq.size()){auto t pq.top();pq.pop();int node t.second, val t.first;if(st[node]) continue;st[node] true;// 更新其他节点for(int i h[node]; i ! -1; i ne[i]){int j e[i];dist[j] min(dist[j], w[i] dist[node]);pq.push({dist[j], j});}}if(dist[n] 0x3f3f3f3f) return -1;else return 0;
}int main()
{memset(h, -1, sizeof h);cin n m;int a, b, c;while(m--){cin a b c;add(a, b, c);}if (dijkstra() -1) couterrorendl;else for(int i 1; i n; i) coutdist[i] ;return 0;
}
算法分析
二叉堆优化的Dijkstra
时间复杂度 O( ( V E )lg V)
验证
同样就验证上面那张图的解。 2 回溯法求解0-1背包
问题重述
一共有N件物品第ii从0开始件物品的重量为weight[i]价值为value[i]。在总重量不超过背包承载上限maxw的情况下求能够装入背包的最大价值是多少并要求输出选取的物品编号。
要求使用回溯法求解
想法
使用回溯法。构造解空间树从第0层到第n-1层每层表示对于背包内某个物品的“取”或“不取”。第n层为答案层在第n层进行判定结果是否是想要的即能不能获得更优的解若是就做出相应的处理。
这是一个万能的解空间树图借来用用。 剪枝想法
1如果在第n层之前就出现了总和大于的maxw情况那么此时已经超重了。之后无论是否取都不可能再得到总和小于maxw的结果了。这种情况以及它的子树直接删去即可。
2如果在第n层之前目前已有的价值即使加上剩余可取的最大价值也不能达到已经达到的bestv那么之后即使全部取也不能达到bestv了。这种情况及它的子树直接删去即可。
剪枝代码可以删去不影响结果但会降低效率。
代码
// -*- coding:utf-8 -*-// File : 01背包问题回溯.cpp
// Time : 2023/12/14
// Author : wolf#include iostream
using namespace std;int w[5000];
int v[5000];
bool flag[5000];
bool ans[5000];
int now_w 0, now_v 0;
int n, maxw, bestv 0;
int rest_v;void backtrace(int depth)
{if (depth n) // 到达第n层答案{if (now_v bestv now_w maxw) // 答案是需要打印的{bestv now_v;for (int i 0; i n; i){ans[i] flag[i];}}return;}if (depth n now_w maxw)return; // 剪枝此时背包已经过重if (now_v rest_v bestv)return; // 剪枝此时剩余价值即使全部拾取也无法达到最大价值rest_v - v[depth];// 取这个物品now_v v[depth];now_w w[depth];flag[depth] 1;backtrace(depth 1);now_v - v[depth];now_w - w[depth];flag[depth] 0;// 不取这个物品backtrace(depth 1);rest_v v[depth];return;
}int main()
{cin maxw n;for (int i 0; i n; i){cin w[i] v[i];ans[i] 0;flag[i] 0;rest_v v[i];}backtrace(0);// for (int i 0; i n; i)//{// if (ans[i])// cout i ;// }// cout endl;// cout bestv bestv endl;cout bestv endl;return 0;
}
验证 回溯法解决背包问题的O(2n)还是从数量级上显著不如动态规划的O(n2)。
故在数据量很大的时候不能通过测评显示超时。
所以01背包问题还是得用动态规划解本题只是练习一下回溯法。
算法分析
时间复杂度O(2^n)解空间树是子集树
空间复杂度O(n)递归深度是n
3 实现题3-17 字符串比较问题
问题重述
【问题描述】 对于长度相同的2 个字符串A和B其距离定义为相应位置字符距离之和。2 个非空格字符的距离是它们的ASCII码之差的绝对值。空格与空格的距离为0空格与其它字符的距离为一定值k。 在一般情况下字符串A和B的长度不一定相同。字符串A的扩展是在A中插入若干空格字符所产生的字符串。在字符串A 和B 的所有长度相同的扩展中有一对距离最小的扩展该距离称为字符串A和B的扩展距离。 对于给定的字符串A和B试设计一个算法计算其扩展距离。
【算法设计】
对于给定的字符串A和B编程计算其扩展距离。
【输入样例】
cmc
snmn
2#第1行是字符串A第2行是字符串B第3行是空格与其它字符的距离定值k。
【输出案例】
10【解释】
c mcsnm n想法
用数组dp[i][j]来记录A,B两串中A串出到第i个,B串出到第j个并且把它们出来的部分进行扩展至长度相等后的最小距离。
讨论dp[i][j]时有以下三种可能
1、A串出一个字符B串不出字符用空格代替这样形成的dp[i][j]。则dp[i][j]dp[i-1][j]k。
2、A串不出字符用空格代替B串出一个字符这样形成的dp[i][j]。则dp[i][j]dp[i][j-1]k。
3、A串出一个字符B串出一个字符。这样形成的dp[i][j]。则dp[i][j]dp[i-1][j-1]abs(a[i]-b[j])。
所以状态转移方程为dp[i][j]min{dp[i-1][j]k,dp[i][j-1]k,dp[i-1][j-1]abs(a[i]-b[j])}
代码
// -*- coding:utf-8 -*-// File : P1279 字串距离递归.cpp
// Time : 2023/12/13
// Author : wolf#include iostream
#include math.h
#include string.husing namespace std;int main()
{string A, B;int k;cin A B k;int lenA A.length();int lenB B.length();int dp[lenA 1][lenB 1];for (int i 1; i lenA; i){dp[i][0] i * k;}for (int i 1; i lenB; i){dp[0][i] i * k;}dp[0][0] 0;for (int i 1; i lenA; i){for (int j 1; j lenB; j){dp[i][j] min(dp[i - 1][j - 1] abs(A[i-1] - B[j-1]), min(dp[i - 1][j] k, dp[i][j - 1] k));//字符串下标从0开始}}cout dp[lenA][lenB] endl;return 0;
}
验证
洛谷P1279字串距离
https://www.luogu.com.cn/problem/P1279 测评结果如下 算法分析
时间复杂度O(nm)
空间复杂度O(nm)
4 实现题5-1 子集和问题
问题
【问题描述】 子集和问题的一个实例为〈S,t〉。其中S{ x1 x2… xn}是一个正整数的集合c是一个正整数。子集和问题判定是否存在S的一个子集S1使得子集S1和等于c。 【编程任务】 对于给定的正整数的集合S{ x1 x2… xn}和正整数c编程计算S 的一个子集S1使得子集S1和等于c。 【输入格式】 由文件subsum.in提供输入数据。文件第1行有2个正整数n和cn表示S的个数c是子集和的目标值。接下来的1 行中有n个正整数表示集合S中的元素。 【输出格式】 程序运行结束时将子集和问题的解输出到文件subsum.out中。当问题无解时输出“No Solution!”。 【输入样例】 5 10 2 2 6 5 4 【输出样例】 2 2 6
想法
使用回溯法。构造解空间树从第0层到第n-1层每层表示对于集合内某个元素的“取”或“不取”。第n层为答案层在第n层进行判定结果是否是想要的若是就做出相应的处理。
这是一个万能的解空间树图借来用用。 传递是否有解
使用函数来传递若返回1则表示已经找到解返回0表示尚未找到解。若子节点返回1其父节点都会返回1。
剪枝想法
如果在第n层之前就出现了总和大于c的情况那么之后无论是否取都不可能再得到总和等于c的结果了。这种情况以及它的子树直接删去即可。
剪枝代码可以删去不影响结果但会降低效率。
代码
// -*- coding:utf-8 -*-// File : 子集合问题回溯.cpp
// Time : 2023/12/14
// Author : wolf#include iostream
using namespace std;int x[50000];
bool flag[50000];
int total 0;
int n, c;int backtrace(int depth)
{int if_ans 0; // 用来存放是否得到了解if (depth n) // 到达第n层答案{if (total c) // 答案是需要打印的{for (int i 0; i n; i){if (flag[i])cout x[i] ;}cout endl;return 1;}return 0;}if (depth n total c)return 0; // 剪枝// 取这个数字total x[depth];flag[depth] 1;if (backtrace(depth 1))if_ans 1;total - x[depth];flag[depth] 0;// 不取这个数字if (backtrace(depth 1))if_ans 1;return if_ans;
}int main()
{cin n c;for (int i 0; i n; i){cin x[i];flag[i] 0;}if (!backtrace(0))cout No Solution! endl;return 0;
}
注意我这个解法给出了所有的结果如果只需要一个结果可以稍微修改代码在递归函数的所有递归入口增加判定若函数返回值为1直接返回不再进入。
【操作】在递归函数第二个递归入口前加这句话
if (if_ans) return 1;结果就只会出现一个结果。 验证
这道题的原题没有找到线上测评。只能自己给数据试试。 算法分析
时间复杂度O(2^n)子集树
空间复杂度O(n)递归深度为n
4【扩展】 类似问题选数
这道题目是类似刚刚上面那道题的只有一点点小区别这题是限定取k个整数而且要判断累加结果是不是素数比上面那道题要难一点。主要是有测评所以就做了。
思路极为相似都是最简单的回溯所以直接给代码了。
问题 代码
// -*- coding:utf-8 -*-// File : 子集合问题回溯.cpp
// Time : 2023/12/14
// Author : wolf#include iostream
using namespace std;int x[50000];
bool flag[50000];
int total 0;
int n, c;int backtrace(int depth)
{int if_ans 0; // 用来存放是否得到了解if (depth n) // 到达第n层答案{if (total c) // 答案是需要打印的{for (int i 0; i n; i){if (flag[i])cout x[i] ;}cout endl;return 1;}return 0;}if (depth n total c)return 0; // 剪枝// 取这个数字total x[depth];flag[depth] 1;if (backtrace(depth 1))if_ans 1;total - x[depth];flag[depth] 0;if (if_ans)return 1;// 不取这个数字if (backtrace(depth 1))if_ans 1;return if_ans;
}int main()
{cin n c;for (int i 0; i n; i){cin x[i];flag[i] 0;}if (!backtrace(0))cout No Solution! endl;return 0;
}
验证 参考文献
Dijkstra证明https://blog.csdn.net/qq_43496675/article/details/106289566
实验感悟
主要是完成了1道贪心题2道回溯题1道动态规划题题目比较简单所以做了一些扩展完成之后感觉还是有点收获的。
