网站怎么建设,火脉推广平台,wordpress导入演示,建设银行+贷款+查询+网站双向DFS
定义
双向深度优先搜索#xff08;Bi-directional Depth First Search, BD-DFS#xff09;是一种在图或树中寻找两点间路径的算法。与传统的单向DFS不同#xff0c;BD-DFS同时从起始节点和目标节点出发进行搜索#xff0c;使用两个DFS过程。一个向前探索从起点到…双向DFS
定义
双向深度优先搜索Bi-directional Depth First Search, BD-DFS是一种在图或树中寻找两点间路径的算法。与传统的单向DFS不同BD-DFS同时从起始节点和目标节点出发进行搜索使用两个DFS过程。一个向前探索从起点到中间状态的路径另一个向后探索从终点到相同中间状态的路径。当两个搜索的前沿相遇时即可找到一条从起点到终点的路径。
运用情况
优化搜索效率当搜索空间非常大时双向搜索可以显著减少搜索的总节点数因为每个方向上的搜索都不需要遍历完整个空间。明确初态和终态适用于已知明确的起始状态和结束状态的问题如某些迷宫问题、最短路径问题等尤其是当两个状态之间的距离较远时。求解最短路径在某些情况下如求解有界范围内的最短路径问题双向DFS配合剪枝策略能有效降低时间复杂度。状态空间对称性当搜索空间存在某种对称性且从两端开始搜索能更快相遇时使用双向DFS更为高效。
注意事项
空间利用需要额外的数据结构来存储两个方向的搜索状态以及可能的中间状态匹配。状态匹配设计有效的数据结构如哈希表来快速判断两个搜索过程中的状态是否匹配这是算法成功的关键。剪枝合理设置剪枝条件避免重复搜索和无效扩展尤其是在状态空间较大的情况下。同步控制两个方向的搜索需要适当同步确保不会错过可能的交汇点特别是在动态规划或状态压缩场景下。
解题思路
初始化分别从起点和终点开始进行DFS并记录已访问的状态。状态标记与存储对每个访问的状态进行标记防止重复访问并将这些状态存储起来以便后续比较。中间状态匹配设计机制检查两个搜索过程中生成的状态是否有交集。这可以通过维护两个集合并在每次扩展状态时检查是否存在交集来实现。收敛一旦发现交集即找到了从起点到终点的路径。此时可以通过回溯或保存的路径信息来重构完整的路径。优化根据问题特性考虑使用启发式信息、剪枝策略等进一步优化搜索过程尤其是在搜索空间较大时。
AcWing 171. 送礼物
题目描述
171. 送礼物 - AcWing题库 运行代码
#include iostream
#include algorithm
#include vector
using namespace std;
typedef long long LL;
const int N 1 24;int n, m, k;
int g[50], weights[N];
int cnt 0;
int ans;void dfs(int u, int s)
{if(u k){weights[cnt ] s;return;}if((LL) s g[u] m) dfs(u 1, s g[u]);dfs(u 1, s);
}void dfs2(int u, int s)
{if (u n){int l 0, r cnt - 1;while (l r){int mid l r 1 1;if (weights[mid] (LL)s m) l mid;else r mid - 1;}if (weights[l] (LL)s m) ans max(ans, weights[l] s);return;}if ((LL)s g[u] m) dfs2(u 1, s g[u]);dfs2(u 1, s);
}int main()
{cin m n;for(int i 0; i n; i ) cin g[i];sort(g, g n, greaterint());k n / 2;dfs(0, 0);sort(weights, weights cnt);int t 1;for (int i 1; i cnt; i )if (weights[i] ! weights[i - 1])weights[t ] weights[i];cnt t;dfs2(k, 0);cout ans endl;return 0;
}
代码思路 输入处理与预处理读取背包最大承重m和物品数量n以及每个物品的重量g[]。然后按重量从大到小排序物品以利于贪心策略。 前向DFS (dfs函数)从物品集合的前半部分n/2个物品开始计算所有可能的子集重量并存储在weights[]数组中。这个步骤利用了深度优先搜索遍历所有组合。 排序与去重对weights[]数组进行排序并去除重复的重量值以便于二分查找。 后向DFS (dfs2函数)从物品集合的后半部分开始对每个可能的子集重量加上当前累计重量s并使用二分查找在前半部分得到的子集重量中寻找合适的配对更新最大总重量ans。 输出结果输出最终得到的最大总重量。
改进思路 记忆化搜索虽然原始代码没有直接使用但考虑到DFS的递归调用如果遇到更复杂的约束或更大规模的问题引入记忆化可以避免重复计算提高效率。 迭代代替递归DFS递归可能导致栈溢出对于大规模问题可以考虑使用迭代方式如栈模拟替代递归。 更高效的搜索算法对于背包问题动态规划(DP)通常比DFS更高效。此问题可以考虑使用二维DP数组其中dp[i][j]表示前i个物品中选取总重量不超过j的最大价值这里价值即重量。但由于需要分两部分考虑可以先DP计算前半部分所有可能的组合再基于这些组合结果对后半部分做优化搜索。 剪枝优化在DFS过程中可以通过剪枝策略进一步减少不必要的搜索比如在前向或后向DFS中如果当前路径的重量已经不可能超过当前最优解则停止该分支的搜索。
