实践中的算法

Situation Task Action Result (STAR)

回溯算法

S (Situation) 寻找到目标节点的路径

1. Vue 项目中，需要实现侧边与路由关联，目录约定如下

interface RouteItem {
	path: string
	title: string
	subs: RouteItem[]
}

type Target = RouteItem["path"];

T (Task)

1. 找到 Target 在 RouterItem 中的 path 链路

A (Action)

1. 尝试了利用 Vue.Router 中的 matched 字段，但是发现和路由配置强关联了。想到路径算法，计算叶子路径，考虑到叶子路径关系，以及剪枝。采用算法实现如下。

1.1 递归回溯

function findPath(asides:RouteItem[], activeAside:Target,res:Target[][]=[],path=[]) {

	// 利用路由建立映射
	// 副本拷贝，初始入栈
	const stack:RouteItem[] = […asides];
	// 开始深搜
	while (stack.length) {
	// 检出当前可进入分支
	const cur = stack.pop();
	// 路径剪枝，因为路径都已经为空了，但是我们寻找的是path
	if (!cur.path) continue;
	// 如果存在路径，一股脑推进
	findPath([...cur.subs],activeAside,res,path.concat(cur.path));
	// 拿到一次性的到叶子节点的路径
	// preflight 检查是否是可行结果
	}
	// 如果是可行解,保留路径,注意拷贝方式
	if(path.includes(activeAside)) res.push([…path]);
	// 不管路径是否满足，因为已经向结果 push 了，不需要记录
	path.length = 0;
	return res;
}

1.2 迭代回溯

function findPath(asides:RouteItem[], activeAside:Target) {
  // 利用路由建立映射
  // 副本拷贝，初始入栈
  const stack:RouteItem[] = […asides];
  // 记录遍历路径
  const path:Target = [];
  // 记录可以解决的结果分支
  const res:Target[][] = [];
  // 开始深搜
  while (stack.length) {
	// 检出当前可进入分支
    const cur = stack.pop();
    // 路径剪枝，因为路径都已经为空了，但是我们寻找的是path
    if (!cur.path) continue;
    // 推入路径
    path.push(cur.path);
    // 如果存在路径，就一次性推入
    if (cur.subs) {
      stack.push(…cur.subs);
      continue;
    }
    // 拿到一次性的到叶子节点的路径
    // preflight 检查是否是可行结果
    if(path.includes(activeAside)){
	    // 如果是可行解,保留路径
	    res.push([…path])
    }
    // 不管路径是否满足，因为已经向结果 push 了，不需要记录
    path.length = 0;
  }
  return [];
}

R (Result)

1. 成功达到目的，最终结果如下

function findPath(asides:RouteItem[], activeAside:Target) {
  // 利用路由建立映射
  // 副本拷贝，初始入栈
  const stack:RouteItem[] = […asides];
  // 记录遍历路径
  const path:Target[] = [];
  // 开始深搜
  while (stack.length) {
	// 检出当前可进入分支
    const cur = stack.pop();
    // 路径剪枝，因为路径都已经为空了，但是我们寻找的是path
    if (!cur.path) continue;
    // 推入路径
    path.push(cur.path);
    // 如果存在路径，就一次性推入
    if (cur.subs) {
      stack.push(...cur.subs);
      continue;
    }
    // 拿到一次性的到叶子节点的路径
    // preflight 检查是否是可行结果
    const idx = path.findIndex(p => p === activeAside);
    // 截取出路径，本次特定情况下可以直接截取
    if (idx !== -1)  return path.slice(0, idx + 1)
	// 不管路径是否满足，因为已经向结果 push 了，不需要记录
    path.length = 0;
  }
  return [];
}

贪心系列

TODO

S (Situation)

需要实现一个效果：

A (Action)

前缀树

TODO