写在22WN最后一个project完结之后
前言
本周终于做完了 370，281 两门课的 Project4，虽然并没有如释重负的感觉（因为后面就是 Final），但还是有点小开心。这篇博文就总结一下这次的两个 p4。
Cache
模拟一个简单的 Cache 运行，并且和 p1 写的 simulator 链接。需要考虑两种大情况，hit 和 miss，并且在 miss 时分类讨论是否有 empty block，难点应该是地址的转换。
Debug 教训
我写了一个比较离谱的 bug，if else 中都有 return，然后在 if else 结束之后写了一段对 LRU 的操作，如图：
导致对 LRU 的操作没有执行。
Pokemon
大概设定是你是一名宝可梦训练家，要收集齐所有宝可梦。从一些设定上看得出这个 Project 的作者应该是个资深的宝可梦的玩家，比如，二周目可以使用飞行（随意连接地图上的两个点），一周目如果要下海，必须先捕捉一只岸边的宝可梦获得冲浪技能。
PartA 本质上是写一个有限制的 MST，在搜寻目标点周围相邻点标记距离时增加一个 coast 和 sea 的判断（至少有一方在 coast 或两点都在 land），如果不符合则不标记两点之间的 d。MST 的本质是逐步选择和 SubGraph 最近的点并且逐步扩大 SubGraph，直到访问所有点。
PartB&C 关于 TSP（traveling salesperson problem），即找到一条最优的路径访问所有点后并回到起始点构成一个环（Hamiltonian cycle）。
PartB 需要完成一个 FastTSP（TSP Heuristics） ，即更快的找到一条相对接近 Optimal TSP 的路径。我使用了 Arbitrary Insertion 的方法。
- 随机选择第一个点 i
- 找到离 i 最近的第二个点 j，将路径设为 i -> j -> i。
- 对所有剩余的点进行循环，每次循环找到一个点加入当前的环（cost 最小），即遍历所有的 j 和 j-1 计算 (j -> candidate -> j-1) - (j -> j-1) cost 最小时即为最优点。
*具体可见 281NotesC22Page37
PartC 需要找到最优的 TSP，并尽可能优化算法，代码核心为 GenPerm（遍历所有可能的排列），为了尽可能增加效率，需要应用 Branch and Bound 的算法。那此时我们就需要考虑，如何得到算法需要的 upperBound 和 lowerBound？显然，upperBound 就是 PartB 的结果，lowerBound 的估计方法则是先找到两条 arm 一条从剩余点连接到 current path 的起始点，一条从剩余点连接到 current 的结尾点，并对剩余点计算 MST（minimum）。将 arm，current cost， MST 相加，结果极为 Lower Bound（在本问题可以视为最低 cost）。如下图所示：
Debug 教训
我起初并没有用 tempDis 保存 distance，而是直接在 += 时调用 distancs[][]，但此时因为 swap，OPTpath[i]中的数据已经改变，+-的数据错误。