回溯算法在项目中的实际应用
大多数同学苦于刷了很多算法却在项目中很少应用，难以加深印象，而且总有同学问着有啥用啊有啥用啊？为了刷题而刷题，带着需求场景去应用算法是最为直接的学习方式。
在大多数算法中解法排名前三的绝对是暴力法，回溯法(含递归)，迭代法（含分治法）。
回溯算法Backtracking
尝试搜索答案，类似枚举，一层层向下递归，直到路径结束。与DSF算法极度相似。
算法模板
// 伪代码
List<Value> result;
void backtrack(路径, 选择列表) {
if (满足结束条件){
result.add(路径);
return;
}
for (选择 : 选择列表) {
做选择;
backtrack(路径, 选择路径);
撤销选择;
}
}
应用场景
当前外卖骑手接单N单，如何计划路线才是最优配送路线？
思路：
- 先计算N单客户距离配送商户距离，起点固定为商户，终点为客户，然后比较N个路线中距离从小到大排列，即为最优路线。
- 枚举出商户到客户的全排列，计算出每个路线的距离，这一次与上一次的距离比较，哪个路线最小保留。
疑问点：
有人会问了，咦？你这第一个方法不是已经算出最优路线了吗？为什么还要枚举全部可能去计算？NoNoNo!在地图上我们计算距离为实际空间的直线距离，如果实际线路中可能存在逆行，限行等实际路线冲突，所以有必要枚举全部可能。
第一种情况伪代码
function (int[] nums)->num[]
String origin = "";
String destinations= "";
List<?> list = new ArrayList;
for( i=0;i<nums.length;i++){
list.add(calcDistance(origin,i.getdestinations()));
}
}
list.sort(Comparator.comparing(Object::getDistance);第二种情况 回溯算法
思路：
当第一次选择为全部数字，由于不能重复，第二次的数据为除去已经被选择的数据的全部数字，第三次数字为除去已经被选择的全部数字，终止条件为满足排列组合等于当前数组的长度。
图解
结论：
当第一次选择开始的客户点为N-0个，不能重复计算...
当第二次选择开始的客户点为N-1个，不能重复计算...
当第三次选择开始的客户点为N-2个，不能重复计算...
终止条件为满足排列组合等于当前数组的长度...
或者可以用多层map去判断，当第一层时为map不包含全部数字，然后向下，当第二层时为map不包含全部数字，直到第[数组长度]层，向上返回，向上返回一层时把当前层已选择的数字从map中去掉，如果向上返回时的数字仍有下层节点则接着遍历，如果没有接着向上返回，直到返回到根节点为止。如图
伪代码
function getDistance(int[] nums) ->[[][],[][],[][]]{
result = new ArrayList<List<Integer>>();
cur = new ArrayList<Integer>();
for(int num :nums){
cur.add(num);
}
backtracking(nums.length, cur, res, 0);
}
backtracking(int n, List<Integer> cur, List<List<Integer>> res, int index);{
//终止条件
if(result.length == n)
res.add(new ArrayList<>(cur));
return;
for (int i = index; i < n; i++) {
if(res.contains(nums[i]))continue;
cur.add(i);
//向下一层
backtracking(n,cur,res,index+1);
//返回上一层是删除
cur.removelast();
}
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读