信奥赛C++提高组csp-s之搜索进阶（搜索剪枝案例实践4）

信奥赛C++提高组csp-s之搜索进阶（搜索剪枝案例实践4）

吃奶酪 —— 记忆化搜索 + 最优性剪枝

题目描述

房间里放着n nn块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在( 0 , 0 ) (0,0)(0,0)点处。

输入格式

第一行有一个整数，表示奶酪的数量n nn。

第2 22到第( n + 1 ) (n + 1)(n+1)行，每行两个实数，第( i + 1 ) (i + 1)(i+1)行的实数分别表示第i ii块奶酪的横纵坐标x i , y i x_i, y_ixi​,yi​。

输出格式

输出一行一个实数，表示要跑的最少距离，保留2 22位小数。

输入输出样例 1

输入 1

4 1 1 1 -1 -1 1 -1 -1

输出 1

7.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 表示第 i+1 块奶酪已吃。
• dp[s][lst]表示在已经吃过集合s中的奶酪，并且最后停留的奶酪编号为lst时，已经走过的最小距离。
• 最终目标是求出dp[(1<<n)-1][i]的最小值（i 为最后一块奶酪），然后加上从起点到第一块奶酪的距离？注意代码实现是 DFS 搜索，从起点出发，累计距离sum，dp用于剪枝记忆化。

算法设计：

用户代码采用了DFS + 剪枝 + 记忆化搜索：

1. 预处理：计算所有点（包括起点）之间的欧氏距离，存入dis[][]。
2. DFS 搜索：
   • 参数：当前状态s（已吃奶酪集合），最后到达的奶酪编号lst，当前总距离sum。
   • 剪枝1：若sum >= ans（当前最优解），直接返回。
   • 剪枝2：若dp[s][lst]已记录且sum >= dp[s][lst]，说明之前到达相同状态时路径更短，当前分支不可能更优，返回；否则更新dp[s][lst] = sum。
   • 递归扩展：枚举所有未吃奶酪，递归进入下一层。
3. 初始调用：dfs(0, 0, 0)，起点编号 0，距离 0。
4. 终点：当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)。n=15 时约15 × 2 15 ≈ 500 k 15×2^{15}≈500k15×215≈500k，加上剪枝实际很快。

---

代码实现

#include<bits/stdc++.h>usingnamespacestd;structnode{doublex,y;}d[20];// 存奶酪坐标，下标 1..n，d[0] 为起点intn,all;// n:奶酪数量，all:全1掩码doubledis[20][20];// 距离矩阵，dis[i][j] 表示 i 到 j 的距离doubledp[1<<15][20];// 记忆化数组，dp[s][lst] 记录状态(s,lst)的最小已走距离doubleans=2e9;// 最优答案，初始化为一个大数intLog[1<<15];// 预处理 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(sum>=ans)return;// 如果所有奶酪都吃完了，更新答案if(s==all){ans=min(ans,sum);return;}// 剪枝2：记忆化剪枝。如果之前到达状态(s,lst)时走过的距离更小，则当前分支不可能更优if(dp[s][lst]!=0&&sum>=dp[s][lst])return;dp[s][lst]=sum;// 记录当前状态的最小距离// 枚举下一个要吃的奶酪intvis=all&(~s);// 未吃奶酪的掩码// 遍历所有未吃的奶酪，利用 lowbit 提取每一位for(inti=vis;i;i-=(i&-i)){intlb=i&-i;// 取出最低位的 1intidx=Log[lb]+1;// 根据 lowbit 得到奶酪编号（因为编号从1开始）// 递归：吃掉 idx 奶酪，状态更新，距离累加 dis[lst][idx]dfs(s|lb,idx,sum+dis[lst][idx]);}}intmain(){cin>>n;all=(1<<n)-1;// 全1掩码，表示所有奶酪都吃完了// 预处理 lowbit 值到编号的映射，例如 lb=1 (二进制1) -> idx=1，lb=2 (10) -> idx=2，lb=4 (100) -> idx=3// Log[1<<i] = i，这里使用递推初始化，方便快速得到索引for(inti=2;i<(1<<15);i++)Log[i]=Log[i/2]+1;// 读入奶酪坐标for(inti=1;i<=n;i++)cin>>d[i].x>>d[i].y;// 起点坐标 (0,0)d[0].x=d[0].y=0;// 预处理任意两点间距离（包括起点）for(inti=0;i<=n;i++)for(intj=0;j<=n;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)，n=15 时约 3.6e6 次运算，实际由于剪枝会更快，完全可以接受。

空间复杂度：

• dis[20][20]常数空间
• dp[1<<15][20]约 32768×20 ≈ 655k 个 double，约 5.2 MB
• Log[1<<15]约 128 KB

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

---

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、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.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}