献给皮鞋👞经理

有一个无限大的棋盘，在某个点有一个只能走日的马，计算马到达棋盘上任意一个点 P(x, y) 最小步数。

“走日” 规则下，任意坐标的 “马” 是否可达任意其它坐标需要证明。按照递归原则，只需证明 “马” 可达它的前后左右四个坐标就足够了，再根据对称原理，只需证明 “马” 能可达它相邻的坐标就足够，而这很容易：

上来就 BFS 遍历肯定没问题，答案一定是正确的：

#!/Users/zhaoya/myenv/bin/python3from collections import dequedx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]def horse_move(target_x, target_y):queue = deque([((0, 0), 0)])visited = set([(0, 0)])while queue:(curr_x, curr_y), steps = queue.popleft()if curr_x == target_x and curr_y == target_y:return stepsfor i in range(8):next_x = curr_x + dx[i]next_y = curr_y + dy[i]if (next_x, next_y) not in visited:visited.add((next_x, next_y))queue.append(((next_x, next_y), steps + 1))if __name__ == "__main__":target_x, target_y = map(int, input("target: ").split())print(horse_move(target_x, target_y))

这最简单，也最蠢，主要就是欺负计算机算得快，但即便如此，在 target 距离原点非常遥远时，BFS 计算量将爆炸式递增。设搜索深度为 d(即最终的结果)，涉及棋盘面积为 n^2，最坏情况下，d 接近 n^2，跳马问题的分支因子为 8，因此最坏情况下时间复杂度为 $O(8^{n^2})$，在无任何优化涉入时，盲目遍历的总体性能非常接近最坏情况，运行以上代码，输入 (10000 10000)，几近卡死，归根结底是能耗。因此需要剪枝。

一个自然的优化就是按 “两点之间线段最短” 原则，在原点和 target 连线周边约束 BFS，其它点不予考虑：

由于 “走日” 规则并不能让坐标连续移动，为避免过度拟合，到达目标点前的 “一定距离” 后，关闭启发式优化，回退到标准 BFS：

#!/Users/zhaoya/myenv/bin/python3from collections import deque
import mathdx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
MIN_DIST = 20def point_to_line_distance(x1, y1, x2, y2, x0, y0):A = y2 - y1B = x1 - x2C = x2 * y1 - x1 * y2distance = abs(A * x0 + B * y0 + C) / math.sqrt(A ** 2 + B ** 2)return distancedef horse_move(target_x, target_y):queue = deque([((0, 0), 0)])visited = set([(0, 0)])total_cnt = 0while queue:(curr_x, curr_y), steps = queue.popleft()total_cnt += 1if curr_x == target_x and curr_y == target_y:return steps, total_cntcurr_dist = pow((target_x - curr_x)**2 + (target_y - curr_y)**2, 0.5);for i in range(8):next_x = curr_x + dx[i]next_y = curr_y + dy[i]if (next_x, next_y) not in visited and curr_dist < MIN_DIST:visited.add((next_x, next_y))queue.append(((next_x, next_y), steps + 1))elif (next_x, next_y) not in visited:line_dis = point_to_line_distance(0, 0, target_x, target_y, next_x, next_y)if line_dis < 2:visited.add((next_x, next_y))queue.append(((next_x, next_y), steps + 1))else:visited.add((next_x, next_y))if __name__ == "__main__":target_x, target_y = map(int, input("target: ").split())print(horse_move(target_x, target_y))

看出问题了吗？

给一个遥远的 target，比如 (10000, 10000)，与原始 BFS 相比，total_cnt 小了几个数量级，但优化后的 steps 可能并非最优的，因为在退出 “瞄准目标” 这种优化前，可能已经走了弯路(虽然概率上不太可能，但受限于 target 坐标和 MIN_DIST，也不是不可能)。这就是优化的代价。

后面我会提到，如此约束的可扩展节点实际上接近 DFS，下图展示相比 BFS，DFS 如何错过最短路径：

求一个 “最值” 时，需考虑该 “最值” 在付出多大代价后会削减它的收益，这就需要权衡。这也是人和 计算机(或许还有 AI?)的最大区别之一。人总是会求一个足够好但并非绝对最优的解，但计算机利用其强大的算力，总是试图通过试错的方式遍历求解绝对最优解。

用最优效益替代最优解是高尚的，它可以做成一个比值：

$E=\frac{解的收益}{获得解的代价}$

看一个效率和正确性的折中方案：

上述代码输入 (1234567 10000) 时，输出如下：(617285, 9877442)，比较次数相比 steps 还是多了一个数量级，在最最理想情况下，二者应该相等，如何逼近这种相等呢？

观察上面的优化，虽然随着到达直线的距离约束的缩短，黑色实心点变少，空心点变多，但依然有太多实心坐标参与遍历，需要用一种更加确定的手段排除尽可能多的坐标。这里的哲学是，目标遥远时采用深度优先，接近目标时采用广度优先。我们从学习一门课程的实践，或寻找一个从未去过的地点时，可以体验到这样做的效率。

从上面的折中方案图示我们可以看到 BFS 到 DFS 再到 BFS 的渐变过程。最初我们希望 BFS 遍历，但由于源到达目标直线斜率的约束，我们排除了 BFS 过程中许多 child，这相当于转向了 DFS，然而随着目标的接近，约束逐渐放宽，更多下一级 child 加入，DFS 转向 BFS。BFS 倾向于正确性，DFS 倾向于效率，它们在互相转换中折中。

若牺牲一定正确性，考虑到 target 非常遥远，便不去榨取 BFS 避免过拟合节省的比较次数，持续使用 DFS。代码如下：

#!/Users/zhaoya/myenv/bin/python3from collections import dequedx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]def horse_move(target_x, target_y):stack = deque()d0 = 0 + math.sqrt((target_x - 0) ** 2 + (target_y - 0) ** 2)stack.append(((0, 0), 0, d0)) visited = set([(0, 0)])total_cnt = 0while stack:(curr_x, curr_y), steps, d = stack.popleft()total_cnt += 1if curr_x == target_x and curr_y == target_y:return steps, total_cntcandidates = []for item in stack:candidates.append(item)for i in range(8):next_x = curr_x + dx[i]next_y = curr_y + dy[i]new_steps = steps + 1# 只度量相对大小，为确保精度不缺失，不再进行 sqrt。new_d = new_steps + ((target_x - next_x) ** 2 + (target_y - next_y) ** 2)candidates.append(((next_x, next_y), steps + 1, new_d))candidates.sort(key=lambda x: (x[1] + x[2]))# 这里实现复杂了，我的本意是对 8 个 child 在整个 stack 中做基于 new_d 的排序插入，# 以确保 stack 从栈顶到栈底的 dist 越来越大，于是距离目标最短的 item 优先弹出继续# 向目标推进。stack = deque()for candidate in candidates:if candidate[0] not in visited:visited.add(candidate[0])stack.append(candidate)if __name__ == "__main__":target_x, target_y = map(int, input("target: ").split())print(horse_move(target_x, target_y))

同样的 (1234567, 10000) 输入，输出为 (617289, 617290)，目标已经达成。但还是那句话，这个解不能保证最优，但足够好，至少它不仅算出了足够小的步数，还保证了这个计算的代价足够低。
这里有一个使用 Python heapq 的实现，一个意思：

#!/Users/zhaoya/myenv/bin/python3import heapqdx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]def horse_move_optimized(target_x, target_y):queue = [(0, ((0, 0), 0))]visited = set([(0, 0)])total_cnt = 0while queue:_, ((current_x, current_y), steps) = heapq.heappop(queue)total_cnt += 1if current_x == target_x and current_y == target_y:return steps, total_cntfor i in range(8):next_x = current_x + dx[i]next_y = current_y + dy[i]if (next_x, next_y) not in visited:visited.add((next_x, next_y))new_steps = steps + 1prior = new_steps + ((target_x - next_x) ** 2 + (target_y - next_y) ** 2)heapq.heappush(queue, (prior, ((next_x, next_y), new_steps)))if __name__ == "__main__":target_x, target_y = map(int, input("target: ").split())print(horse_move_optimized(target_x, target_y))

到此为止，就差一步便导出 A* 搜索算法的形式，用方向(类似哈密尔顿距离的启发)逼近替代欧几里得距离：

def heuristic(current_x, current_y, target_x, target_y):return max(abs(current_x - target_x), abs(current_y - target_y))prior = new_steps + heuristic(next_x, next_y, target_x, target_y)

A* 算法用总代价 f(x) = g(x) + h(x) 作为节点的扩展优先级，其中 g(x) 为起点到 x 的实际代价，h(x) 为 x 到目标节点的预估代价，h(x) <= ‘x 到目标节点的实际代价’ 确保代价不会被高估，从而保证被低估的实际代价逐渐叠加到 g(x) 上，优先级队列使实际代价低却被隐藏的节点往上浮，这就保证了最优解的正确性，h(x) 的该特性称作可采纳性。

可采纳性保证了算法能朝最优解的方向合理引导搜索过程，避免过度探索偏离最优路径的区域，优于采用欧氏距离作为引导的搜索，在跳马类问题中，欧氏距离作为预估代价经常导致看似很远的节点却比欧氏距离很近的节点更容易到达，不具备可采纳性。

与上面一系列优化相比，A* 算法显然兼具正确性和效率，棒极了，我没有自然而然推出 A*(虽然我不知道名字，但知道意思) 算法，因为我没有从全局优先级队列去设计算法，而是采用 “优化 BFS” 的思路，有了 BFS 本就在那里待优化的前提，大方向一开始就错了，但我对过程中最优解和次优解的辩证转换还是很满意，转念一想，A* 算法在优先级队列(或堆)里消耗了太多时间，如排序，插入，这并非免费，同样是代价，而我最初用直线斜率约束 8 个 child 扩展资格的方法在稍微松弛了最优解的 “最” 字之后就自然避免了这些代价，交易依然存在。

遗留一个小问题，如果棋盘不是无穷大，而是 mm，mn 则如何？

若在有限范围内跳马，徒增约束而已，在 BFS 过程中，8 个 child 节点的添加需要考虑边界约束。但最大的问题是无法利用 “方向约束” 进行有效 DFS 了。但仔细一想，这也不是问题，如果 m，n 够大，依然可以利用 DFS，如果 m，n 很小，BFS 遍历时间复杂度也会被有效抑制，也就用不到 DFS 优化。

参考 Dijkstra 算法，它其实就是个洪水泛滥的过程，背后是第一性原理，最短路径恰由 BFS 保证，自然界的最小作用量原则总让最短路径的目标首当其冲，基于此我提出一个一次 BFS 寻遍最短路径的方法：单源最短路径新方法。将算法约束松弛一下，便可在快得多的时间内寻遍 “不一定最优但足够好” 的 “短路径”，这在实践上非常有意义。

早些年做 SDWAN 流量调度，为疏导拥塞流量，我会搜罗一箩筐指标进行加权，运行 Dijkstra 算法，作为 overlay 隧道路径质量度量 ，随节点规模扩大，稳定收敛时间到达秒级以上，终于还是遇到扩展性问题。每当这时，我心里清楚得很，需要做交易，但内心还是希望白嫖，通过一个巧妙的把戏妙手回春。

我的目标是将拥塞流量疏导，动作一定要快才能避免更严重丢包，而丢包重传意味着能耗的浪费。换句话说，只要找到一条或几条不拥塞的路径构建隧道，而不是为了找到任意两点的最短路径而构建一棵最短路径树。这连次优解都不需要，甚至只需要几个次差路径就够了。

我毅然抛弃了通过最短路径树稳定收敛的方法，转向了随机试错的方式(我对 PFC 拥塞疏导还是一样的观点)，在此基础上构建松散的最大流网络。虽然得到的不是最优解，但我根本不需要最优解，能快速疏导大流量拥塞就完成目标了。

重新审视这事，方法论和本文前半部分针对跳马问题的逐步优化如出一辙，理解交易的本质，你需要什么，你能付出什么来交换。

更进一步讲，基于 TCP/IP 的互联网路由真的需要 “最短路径优先” 吗？流量在 “最短” 路径上真的能获得最优传输 QoS/QoE 吗？如果最优路径形成共识，次优路径有何种概率可成为事实上的最优路径却又形不成共识呢？与最短路径优先(比如，所有节点都保有一棵一致的最短路径树的副本)共识相反，本质上路由就是个无共识的概率问题，能顺利通过的概率，而顺利度需要以不同的方式度量，而不是一般数学意义上的 “最优”。概率路由更符合连通的第一性原理。

最优解的目标是约束计算复杂度，但获得最优解的过程却有代价，和往常一样，现实的最优解要做个除法。

从开始学编程做课后习题到各类考试，面试，晋升，再到应经理对立项挑战，论文 PR…始终绕不开 “最优解”，最短路径，最小生成树，最大流，最小割…似乎最优解就是最有效率解，能挑战一切。但实际情况中我们考虑的更多是平均情况下差不多的解，多低的概率不跌落到最坏情况。比如最常见的排序算法，没人任何算法声称最快，但快速排序却在大多数情况下表现足够好以获得其名。此外，我们虽在效率上敢于打折扣，却几乎不敢在正确性上打折扣，本文提出一个观点，为了效率亦可挑战 正确性，为了效率亦可牺牲正确性，全局最优要同时考虑正确性和效率。挑战正确性的前提是正确性是否为效率服务，如果是，那正确性本身就可退而求其次被挑战，幸运的是，绝大多数求最优解的算法都是为了效率，这意味着它们可以被挑战，求次优解的代价可小多了。

浙江温州皮鞋湿，下雨进水不会胖。