信奥赛C提高组csp-s之搜索进阶搜索剪枝案例实践4吃奶酪 —— 记忆化搜索 最优性剪枝题目描述房间里放着n nn块奶酪。一只小老鼠要把它们都吃掉问至少要跑多少距离老鼠一开始在( 0 , 0 ) (0,0)(0,0)点处。输入格式第一行有一个整数表示奶酪的数量n nn。第2 22到第( n 1 ) (n 1)(n1)行每行两个实数第( i 1 ) (i 1)(i1)行的实数分别表示第i ii块奶酪的横纵坐标x i , y i x_i, y_ixi,yi。输出格式输出一行一个实数表示要跑的最少距离保留2 22位小数。输入输出样例 1输入 14 1 1 1 -1 -1 1 -1 -1输出 17.41说明/提示数据规模与约定对于全部的测试点保证1 ≤ n ≤ 15 1\leq n\leq 151≤n≤15∣ x i ∣ , ∣ y i ∣ ≤ 200 |x_i|, |y_i| \leq 200∣xi∣,∣yi∣≤200小数点后最多有3 33位数字。提示对于两个点( x 1 , y 1 ) (x_1,y_1)(x1,y1)( x 2 , y 2 ) (x_2, y_2)(x2,y2)两点之间的距离公式为( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 \sqrt{(x_1-x_2)^2(y_1-y_2)^2}(x1−x2)2(y1−y2)2。思路分析问题理解给定 n≤15块奶酪的坐标老鼠从原点 (0,0) 出发要吃掉所有奶酪求最短路径长度。这是一个典型的旅行商问题TSP但起点固定为原点且 n 很小可以用状态压缩动态规划或深度优先搜索DFS加剪枝解决。状态表示奶酪编号 1…n起点编号 0。用二进制掩码s表示已经吃过的奶酪集合s的二进制第 i 位从 0 开始为 1 表示第 i1 块奶酪已吃。dp[s][lst]表示在已经吃过集合s中的奶酪并且最后停留的奶酪编号为lst时已经走过的最小距离。最终目标是求出dp[(1n)-1][i]的最小值i 为最后一块奶酪然后加上从起点到第一块奶酪的距离注意代码实现是 DFS 搜索从起点出发累计距离sumdp用于剪枝记忆化。算法设计用户代码采用了DFS 剪枝 记忆化搜索预处理计算所有点包括起点之间的欧氏距离存入dis[][]。DFS 搜索参数当前状态s已吃奶酪集合最后到达的奶酪编号lst当前总距离sum。剪枝1若sum ans当前最优解直接返回。剪枝2若dp[s][lst]已记录且sum dp[s][lst]说明之前到达相同状态时路径更短当前分支不可能更优返回否则更新dp[s][lst] sum。递归扩展枚举所有未吃奶酪递归进入下一层。初始调用dfs(0, 0, 0)起点编号 0距离 0。终点当s all所有奶酪已吃更新ans min(ans, sum)。剪枝策略最优性剪枝当前累计距离已超过已知最优解终止。记忆化剪枝用dp[s][lst]记录到达该状态的最小距离避免重复搜索更差路径。复杂度状态数最多2 n ∗ n 2^n * n2n∗n对每个状态枚举未吃奶酪 O(n)总复杂度O ( 2 n ∗ n 2 ) O(2^n * n^2)O(2n∗n2)。n15 时约15 × 2 15 ≈ 500 k 15×2^{15}≈500k15×215≈500k加上剪枝实际很快。代码实现#includebits/stdc.husingnamespacestd;structnode{doublex,y;}d[20];// 存奶酪坐标下标 1..nd[0] 为起点intn,all;// n:奶酪数量all:全1掩码doubledis[20][20];// 距离矩阵dis[i][j] 表示 i 到 j 的距离doubledp[115][20];// 记忆化数组dp[s][lst] 记录状态(s,lst)的最小已走距离doubleans2e9;// 最优答案初始化为一个大数intLog[115];// 预处理 lowbit 对应的索引奶酪编号// 计算两点欧氏距离doubledist(node a,node b){returnsqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));}// 深度优先搜索// s: 当前已吃奶酪的二进制掩码1表示已吃// lst: 当前所在的奶酪编号0表示起点// sum: 已经走过的总距离voiddfs(ints,intlst,doublesum){// 剪枝1当前距离已不小于已知最优解无需继续if(sumans)return;// 如果所有奶酪都吃完了更新答案if(sall){ansmin(ans,sum);return;}// 剪枝2记忆化剪枝。如果之前到达状态(s,lst)时走过的距离更小则当前分支不可能更优if(dp[s][lst]!0sumdp[s][lst])return;dp[s][lst]sum;// 记录当前状态的最小距离// 枚举下一个要吃的奶酪intvisall(~s);// 未吃奶酪的掩码// 遍历所有未吃的奶酪利用 lowbit 提取每一位for(intivis;i;i-(i-i)){intlbi-i;// 取出最低位的 1intidxLog[lb]1;// 根据 lowbit 得到奶酪编号因为编号从1开始// 递归吃掉 idx 奶酪状态更新距离累加 dis[lst][idx]dfs(s|lb,idx,sumdis[lst][idx]);}}intmain(){cinn;all(1n)-1;// 全1掩码表示所有奶酪都吃完了// 预处理 lowbit 值到编号的映射例如 lb1 (二进制1) - idx1lb2 (10) - idx2lb4 (100) - idx3// Log[1i] i这里使用递推初始化方便快速得到索引for(inti2;i(115);i)Log[i]Log[i/2]1;// 读入奶酪坐标for(inti1;in;i)cind[i].xd[i].y;// 起点坐标 (0,0)d[0].xd[0].y0;// 预处理任意两点间距离包括起点for(inti0;in;i)for(intj0;jn;j)dis[i][j]dist(d[i],d[j]);// 从起点开始深度优先搜索dfs(0,0,0);// 输出答案保留两位小数printf(%.2lf\n,ans);return0;}功能分析主要功能计算从原点出发经过所有给定奶酪点的最短路径长度结果四舍五入保留两位小数。正确性分析状态穷举DFS 遍历所有可能的吃奶酪顺序确保不会遗漏任何路径。剪枝正确性最优性剪枝sum ans时剪枝因为即使后续距离为 0总长也不会小于当前最优解。记忆化剪枝dp[s][lst]记录的是到达状态(s,lst)的最小已走距离。如果当前sum不小于该最小值说明当前分支不可能产生更优的完整路径因为后续路径完全一样可以安全剪枝。距离计算使用欧氏距离公式符合题目要求。起点处理将起点作为编号 0 加入距离矩阵初始调用dfs(0,0,0)第一次移动会从起点到第一块奶酪。时间复杂度最坏情况O ( 2 n ∗ n 2 ) O(2^n * n^2)O(2n∗n2)n15 时约 3.6e6 次运算实际由于剪枝会更快完全可以接受。空间复杂度dis[20][20]常数空间dp[115][20]约 32768×20 ≈ 655k 个 double约 5.2 MBLog[115]约 128 KB更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
信奥赛C++提高组csp-s之搜索进阶（搜索剪枝案例实践4）
信奥赛C提高组csp-s之搜索进阶搜索剪枝案例实践4吃奶酪 —— 记忆化搜索 最优性剪枝题目描述房间里放着n nn块奶酪。一只小老鼠要把它们都吃掉问至少要跑多少距离老鼠一开始在( 0 , 0 ) (0,0)(0,0)点处。输入格式第一行有一个整数表示奶酪的数量n nn。第2 22到第( n 1 ) (n 1)(n1)行每行两个实数第( i 1 ) (i 1)(i1)行的实数分别表示第i ii块奶酪的横纵坐标x i , y i x_i, y_ixi,yi。输出格式输出一行一个实数表示要跑的最少距离保留2 22位小数。输入输出样例 1输入 14 1 1 1 -1 -1 1 -1 -1输出 17.41说明/提示数据规模与约定对于全部的测试点保证1 ≤ n ≤ 15 1\leq n\leq 151≤n≤15∣ x i ∣ , ∣ y i ∣ ≤ 200 |x_i|, |y_i| \leq 200∣xi∣,∣yi∣≤200小数点后最多有3 33位数字。提示对于两个点( x 1 , y 1 ) (x_1,y_1)(x1,y1)( x 2 , y 2 ) (x_2, y_2)(x2,y2)两点之间的距离公式为( x 1 − x 2 ) 2 ( y 1 − y 2 ) 2 \sqrt{(x_1-x_2)^2(y_1-y_2)^2}(x1−x2)2(y1−y2)2。思路分析问题理解给定 n≤15块奶酪的坐标老鼠从原点 (0,0) 出发要吃掉所有奶酪求最短路径长度。这是一个典型的旅行商问题TSP但起点固定为原点且 n 很小可以用状态压缩动态规划或深度优先搜索DFS加剪枝解决。状态表示奶酪编号 1…n起点编号 0。用二进制掩码s表示已经吃过的奶酪集合s的二进制第 i 位从 0 开始为 1 表示第 i1 块奶酪已吃。dp[s][lst]表示在已经吃过集合s中的奶酪并且最后停留的奶酪编号为lst时已经走过的最小距离。最终目标是求出dp[(1n)-1][i]的最小值i 为最后一块奶酪然后加上从起点到第一块奶酪的距离注意代码实现是 DFS 搜索从起点出发累计距离sumdp用于剪枝记忆化。算法设计用户代码采用了DFS 剪枝 记忆化搜索预处理计算所有点包括起点之间的欧氏距离存入dis[][]。DFS 搜索参数当前状态s已吃奶酪集合最后到达的奶酪编号lst当前总距离sum。剪枝1若sum ans当前最优解直接返回。剪枝2若dp[s][lst]已记录且sum dp[s][lst]说明之前到达相同状态时路径更短当前分支不可能更优返回否则更新dp[s][lst] sum。递归扩展枚举所有未吃奶酪递归进入下一层。初始调用dfs(0, 0, 0)起点编号 0距离 0。终点当s all所有奶酪已吃更新ans min(ans, sum)。剪枝策略最优性剪枝当前累计距离已超过已知最优解终止。记忆化剪枝用dp[s][lst]记录到达该状态的最小距离避免重复搜索更差路径。复杂度状态数最多2 n ∗ n 2^n * n2n∗n对每个状态枚举未吃奶酪 O(n)总复杂度O ( 2 n ∗ n 2 ) O(2^n * n^2)O(2n∗n2)。n15 时约15 × 2 15 ≈ 500 k 15×2^{15}≈500k15×215≈500k加上剪枝实际很快。代码实现#includebits/stdc.husingnamespacestd;structnode{doublex,y;}d[20];// 存奶酪坐标下标 1..nd[0] 为起点intn,all;// n:奶酪数量all:全1掩码doubledis[20][20];// 距离矩阵dis[i][j] 表示 i 到 j 的距离doubledp[115][20];// 记忆化数组dp[s][lst] 记录状态(s,lst)的最小已走距离doubleans2e9;// 最优答案初始化为一个大数intLog[115];// 预处理 lowbit 对应的索引奶酪编号// 计算两点欧氏距离doubledist(node a,node b){returnsqrt((a.x-b.x)*(a.x-b.x)(a.y-b.y)*(a.y-b.y));}// 深度优先搜索// s: 当前已吃奶酪的二进制掩码1表示已吃// lst: 当前所在的奶酪编号0表示起点// sum: 已经走过的总距离voiddfs(ints,intlst,doublesum){// 剪枝1当前距离已不小于已知最优解无需继续if(sumans)return;// 如果所有奶酪都吃完了更新答案if(sall){ansmin(ans,sum);return;}// 剪枝2记忆化剪枝。如果之前到达状态(s,lst)时走过的距离更小则当前分支不可能更优if(dp[s][lst]!0sumdp[s][lst])return;dp[s][lst]sum;// 记录当前状态的最小距离// 枚举下一个要吃的奶酪intvisall(~s);// 未吃奶酪的掩码// 遍历所有未吃的奶酪利用 lowbit 提取每一位for(intivis;i;i-(i-i)){intlbi-i;// 取出最低位的 1intidxLog[lb]1;// 根据 lowbit 得到奶酪编号因为编号从1开始// 递归吃掉 idx 奶酪状态更新距离累加 dis[lst][idx]dfs(s|lb,idx,sumdis[lst][idx]);}}intmain(){cinn;all(1n)-1;// 全1掩码表示所有奶酪都吃完了// 预处理 lowbit 值到编号的映射例如 lb1 (二进制1) - idx1lb2 (10) - idx2lb4 (100) - idx3// Log[1i] i这里使用递推初始化方便快速得到索引for(inti2;i(115);i)Log[i]Log[i/2]1;// 读入奶酪坐标for(inti1;in;i)cind[i].xd[i].y;// 起点坐标 (0,0)d[0].xd[0].y0;// 预处理任意两点间距离包括起点for(inti0;in;i)for(intj0;jn;j)dis[i][j]dist(d[i],d[j]);// 从起点开始深度优先搜索dfs(0,0,0);// 输出答案保留两位小数printf(%.2lf\n,ans);return0;}功能分析主要功能计算从原点出发经过所有给定奶酪点的最短路径长度结果四舍五入保留两位小数。正确性分析状态穷举DFS 遍历所有可能的吃奶酪顺序确保不会遗漏任何路径。剪枝正确性最优性剪枝sum ans时剪枝因为即使后续距离为 0总长也不会小于当前最优解。记忆化剪枝dp[s][lst]记录的是到达状态(s,lst)的最小已走距离。如果当前sum不小于该最小值说明当前分支不可能产生更优的完整路径因为后续路径完全一样可以安全剪枝。距离计算使用欧氏距离公式符合题目要求。起点处理将起点作为编号 0 加入距离矩阵初始调用dfs(0,0,0)第一次移动会从起点到第一块奶酪。时间复杂度最坏情况O ( 2 n ∗ n 2 ) O(2^n * n^2)O(2n∗n2)n15 时约 3.6e6 次运算实际由于剪枝会更快完全可以接受。空间复杂度dis[20][20]常数空间dp[115][20]约 32768×20 ≈ 655k 个 double约 5.2 MBLog[115]约 128 KB更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
