关平打探得知，刘备如今身在袁绍营中 关羽闻讯就计划逃出曹营与刘备会和 逃出曹营需要经过多个城池 而部分城池有不同数量的守军，关羽路过需与守军交战 因此关羽需计划出逃路线 为免连续作战精疲力尽 在连续经过两个有守军的城池后，他必须前往一个没有守军的城池稍作休息 同时他希望出逃路线上遇到的守军尽可能少，增加出逃的机会 为求得最佳路线，关羽取出神算法板 >> 关平 回来报告，他已经找到刘备他的所在了 关羽呢十分之希望跟他的好兄弟 可以重聚，所以呢他就计划要离开曹操 做一个大逃亡。 当然要做这个逃亡 不是一件容易的事情，我们可以看看，这个就是他可以逃亡的不同的路线 其实曹操已经知道关羽有这个计划了 所以呢就在这个路线上面不同的重要的要点就放了很多的士兵 要阻止关羽去这个离开他的控制的范围 里面。 在这个图上面，我们看见有不同的颜色的点 绿色的点呢就是没有士兵的，红色的点就是有士兵 驻守的，而且呢我们也在旁边去标示士兵的数目 关羽呢就是需要在这个路线图上面找一个好的 路径，从他的起点第一点去到 刘备的所在。 好了 当然第一个约束就是在这个路线图上面找一个路径 我们看看另外一个约束，另外一个约束就是因为体力的问题 关羽呢就是没有可能连续在三个点都需要跟 这个士兵去对战的，所以呢我们就要求 如果关羽已经连续在两个点跟士兵对战的话，他下一个 点呢肯定是需要一个没有士兵的点，然后他可以休息一下 他这个逃亡的目标很简单，就是 希望在这个路径上面遇到的士兵的数目就是，总和就是最低 就是他的目标了。 好了，我们再看看这个路径图 我们为了我们求解过程里面一些方便，我们呢需要在这个路径图呢 加一个自环的一个边 我们在下面呢就会慢慢给大家说明为什么需要这个自环的边 好了，在这个图上面其实已经有很多的数据在里面了，我们看看 在我们 MiniZinc 这个数据的 文件里面是怎么表示我们刚才看见的数据的 首先我们有一个 n，这个 n 就是代表我们这个路径上面有多少个点 还有一个数组我们叫 guard，这个数组呢就是代表 在每一个点上面，这个士兵的数量 特别我们看看，这个就是我们第一个点，这个呢就是我们的终点 我们假设呢在我们的起点跟我们终点应该是没有士兵的 因为我们有这样子的假设呢，我们建议大家呢 应该用这个断言来检查我们的数据的 好了，另外一个参数呢 就是 m， m 就是代表了我们这个路径图上面边的数目 然后当然呢我们要表示我们的 这个路径图上面不同的边，我们就利用一个二维的数组 我们叫 edge，这个二维的数组呢每一行呢就代表 代表一条边的两个点，譬如说我们一条边它的 把第一个点跟第二个点连起来的，我们有另外一条边把第四个点跟第八个点 连起来了，还有最重要就是我们加进去的一个自环的一个边就是终点 自环回到终点，回到终点，是这样子 这个 rest 就是，这个参数就是代表 关羽每三个站，三个点他就需要有一个休息点 start 就是他的起点， destination 就是他的终点 还有一个呢我们叫 maxstep，就是代表了我们估计 这个关羽他选取的路径最大的步数 我们暂时呢把它定为 10，我们下面再说明这个 maxstep 它的用途是怎么样的 好了，我们可以看看我们的模型，模型首先当然 有数据的部分，这个数据的部分基本上就是把我们刚才 看过的数据它们的声明，所以我们不再讲了 还有呢，就是我们的决策变量 这个决策变量呢我们这个 maxstep 是非常重要的，这个就是我们要估计 关羽选取的路径的最大的步数，是因为 这个是个非常复杂的一个路径图，我们根本一开始就不知道 他选取的路径，他的步数是多少的，所以我们首先要 估计一个最大的步数，然后呢我们需要有一个变量 这个变量就是我们叫小写的 step，就是代表 真的关羽终于选取这个路线，它的实际的步数 而且呢我们还要定义一个 数组，这个数组呢它的范围 就是从 1 到我们最大估计的 最大的步数来表示关羽呢 他的选取的路径，这个数组里面每一点就是 关羽从第一点到第二点到第三点，终于可以到终点 的一个变量。 好了 当然了，这个问题里面最重要的约束我们就是要保证关羽选取的路线 从一点到另外一点呢是真的在我们的路径图上面是有一条这样子的边的 我们需要去保证这个条件是 可以满足的话，我们就需要介绍 MiniZinc 里面一个新的 全局约束，我们叫 Table 这个 Table 的全局约束呢有两个 参数，第一个参数呢就是一个变量的数组 它的范围呢是从 1 到 n，就是说这个数组有 n 个元素在里面 然后第二个参数就有一个二维的 数组，这个二维的数组呢 第一维就是有 T 的行这个数组，T 行 然后呢每一行也有 n 个元素在里面的 好了，我们看看这个 table 这个全局约束它的 语义是什么。 它是保证在我们第一个参数这个 x 这个数组的变量数组呢 的变量整体来说一定，它们可以取的 值一定是要在 t 这个二维数组里面的 每一行的作为它的值 我们看看下面这个例子呢有可能就可以 更好地理解我们这个 table 这个全局约束它的语义了 我们第一个参数就是一个 变量的数组，我们有三个变量x、 y、 z，然后呢 第二个参数就是个二维的数组，每一行也有三个 元素在里面，0、 0、 0，1、 2、 3，4、 2、 0 我们这个全局约束呢只有三个解 每一个解呢我们就需要 x、 y、 z 可以 取的值就是我们第二个参数里面 某一行，所以呢这个 全局约束它的解分别就是 0、 0、 0 1、 2、 3 跟 4、 2、 0，就只有三个 可能的解。 好了，我们可以 利用这个 table 这个全局约束呢帮助我们要求 关羽选取的路径上面从一点到下一点都是一定是在这个路径图 里面，上面的一条边，我们怎么做呢？ 就是可以利用我们显示表示的两条约束 第一条约束呢非常简单，就是说他关羽的逃亡的路径的第一点 应该就是我们的起点，这个没问题吧？然后我们呢就要求，关羽选取的 路径从第 i 点到第 i+1 点，就是连续的一个点呢，一定 是基于这个 table 这个全局约束，是在我们的路径图 我们的 edge 这个数组里面的其中一条边，这个就是我们的 意思。 那你们可能会问，我们 为什么还要需要在这个目的地还有一个自环呢？ 我们在下面就给大家说明 好了，这个 问题最需要一个技巧的地方呢就是 我们是在解题之前根本就没有 可能知道，关羽选取的路径它的长度是多少的 所以呢我们也需要，你们看看我们需要呢先估计 他这个选取的路径的步数的最大的值 我们选取这个，估计这个最大的值是有一点点的技巧的 如果选这个值选得太小呢 当然要越小越好，但是不可以太小。 太小的话就有可能就是关羽 有可能选取一个合理的路径，但是就不可以满足我们这个模型里面的条件了 但是如果把这个估计估得 太大的话呢，就会把我们的问题变得更难了 所以呢我们要好好地做一个估计。 我们现在的估计呢是他的步数是 10 的 然后我们再重温，就是我们有一个 变量就是，真的代表终于关羽选取路径的步数，还有呢 我们这个变量的数组呢，就代表他真的选取的 路径的每一点是一个顺序来的 好了，但是呢我们这个数组它的范围就是从 1 到这个最大的步数的，如果关羽真的选取的路径是比最大的步数要 少的话，怎么办呢？我们可以看看下面这个例子 譬如说关羽选取的路径是从第 1 点到第 2 点到第 3 点到 11 点 14 点、 15 点，到了第 9 点，如果大家还记得的话 第 9 点呢就是他的终点了。 其实呢我们就可以要求在这个数组里面 继续就在这个第 9 点就地循环 我们怎么可以保证有这个就地循环呢？我们可以加入这样子 这一条的约束，这个约束就是说，在我们这个数组里面 如果呢我的去到第 i 步，这个第 i 步已经 大于等于关羽可以到达这个 终点的步数的话，我们要求以后的所有的 点呢都是原来的终点，这个就是我们讲的自环了 好了 我们这个问题还有其他的约束的。 就是说关羽呢 在每三个点呢，他也需要有一个点他可以休息的 我们要表达这样子的一个条件呢，我们需要 另外一个新的全局约束，就是叫 sliding_sum 这个 sliding_sum 这个约束呢有四个 这个参数，第一个跟第二个参数呢分别是一个 下限跟一个上限，第三个参数呢是一个长度来的 然后第四个参数呢就是一个变量的数组 然后这个 sliding_sum 这个全局约束呢是要求 在这个变量数组从第一个元素开始 每 sequence 这个长度的一个子序列 它里面的元素的总和加起来一定要在这个 下限跟这个上限中间 我们都是看一看一个例子吧。 我们这个例子里面有一个 sliding_sum (4, 8, 4, x)，我们的 x 呢就是一个变量的数组 我们可以看看，如果我们 x 的值是 [1, 4, 2, 0, 0, 3, 4] 的话，这个是满足我们这个 sliding_sum 的条件的，因为我们可以看看 我们呢因为要求它的 子序列的长度是 4，所以我们就看 [1, 4, 2, 0] 这个子序列它加起来是 7 应该是在 4 跟 8 中间。 [4, 2, 0, 0] 加起来是 6 所以也是在 4 到 8 中间。 [2, 0, 0, 3] 加起来是 5 也是在 4 跟 8 中间。 然后 [0, 0, 3, 4] 加起来是7，也是在 4 到 8 中间 好了下面就是一个例子了。 如果 x 是等于 [1, 4, 3, 0, 1, 0, 2] 呢就不满足这个条件了 我们可以看看，[1, 4, 3, 0] 这个子序列加起来是 8，没问题。 [4, 3, 0, 1] 加起来是 8 也是没问题，但是到了最后，[0, 1, 0, 2] 加起来只有 3 出了 4 到 8 这个范围外面，所以这个 x 呢就不满足我们这个 sliding_ sum 这个全局约束了 好了，利用我们这个 sliding_sum 这个全局约束呢我们就可以表达，关羽要求在路径中 每三个点呢他需要 起码有一个点呢是可以给他休息的。 他什么时候可以休息啊？就是 这个点是没有士兵在的。 所以呢我们就首先做一个 序列出来，这个序列就是基于他选取的路径。 这个路径上面每一个点我们就看看 到底有没有士兵。 有士兵的话，这个就是为 0 没有士兵就是为 1。 然后我们要求每三个点它的总和 加起来是应该到 1 到 3 中间，基本上就是 希望起码有一个点是没有士兵，所以关羽就可以休息了 好了到了最后，就是我们的目标函数 就是呢要求关羽选取的路径上面 所有的士兵加起来的总和，我们希望把它最小化 好了，我们把我们的模型建好之后当然就要跑了 但是跑出来结果就是不可以满足，我们怎么办呢？ 我们遇到这个问题呢，我们 称之为"丢失解"的问题 因为我们觉得应该有一个解的，因为应该 有一个路径可以帮助这个关羽逃亡的，但是找不出来 其实丢失解呢，有一个最糟糕的情况，就是什么呢？ 我们要跑这个模型，一直在等 等，等了很久的时间，还是没有一个解输出出来 到了这个情况的时候呢，我们可以有一个办法 去把这个问题稍微 修复一下的，就是我们应该 要求这个 MiniZinc 呢要把输出所有解的 输出所有解，我们可以在这个命令里面要求放这个 -a 或者是 -all solutions，也可以当然在我们的 IDE 上面 要求把所有的解输出出来。 对于优化 问题呢我们不需要搞这个设置 因为在 IDE 里面默认的时候就已经把所有的解都输出出来了 但是如果还是没有解 又或者是我们刚才遇到是不可以满足，我们还可以怎么办呢？ 其实呢我们还是有一些技巧呢可以帮助我们解决这个问题的 第一，我们可以 再看看我们要解决这个问题，看看我们可不可以找到一个解 然后把这个解作为一个约束加进我们的模型当中 第二个方案呢，就是我们可以考虑 把我们模型里面一些的约束，把它松弛 好了，我们怎么找一个解出来加入 我们的模型呢？我们需要呢就是 建构一个比较小的实例，然后呢 我们也需要这个实例呢需要是反映我们这个问题的一个结构的 然后呢我们就利用这个实例就 构造一个我们觉得应该是我们问题的解的情况出来，然后把这个解呢 就作为一个约束加到我们的模型里面，然后当然呢重新求解 如果我们是幸运的话，我们 MiniZinc 呢就应该 输出下面的信息，就是说：Model inconsistency detected 然后而且也把在哪一行，这个行号 也标示出来，然后我们就知道问题发生在哪里，然后我们就可以修正我们的模型了 也有可能是没有这样子的输出的 只是给我们一个警告说：model inconsistency detected before search，就是 在我们开始求解之前已经发现这个模型出了问题了 我们还可以做什么呢？ 刚才已经提过，我们要用第二个方案，就是 考虑把我们这个模型里面某一些的约束 松弛，就是我们就把 模型里面的约束一条一条地移除，直到我们可以找一个解出来 但是呢当我们找到解之后，我们已经松弛了 一部分的约束，但是不是所有的约束都是 跟我们的问题有关系的，所以我们要收窄我们的范围 确认我们真的跟我们这个问题的有相关的 约束，然后我们应该就尝试去修复 这样子的约束。 好了 我们看看我们怎么利用刚才提到的技巧，去解决我们这个 寻找路径的这个问题里面 我们再看清楚这个路径图 我们觉得呢，其实这个是一个可行的路径，这个路径呢 有可能不是我们最优的路径，但是起码关羽是可以根据这个路径从他的起点 到了刘备的地方的，分别就是从第 1 点到 第 10 点到第 6 点、 11、 14、 到 9 总共用的步数是 7。 我们需要把这个解呢 变成这里的一个约束，加进我们的模型里面 然后我们再要求我们的 MiniZinc 去把我们的模型去跑 但是出来结果还是不可以满足 所以呢我们应该采用我们的第二个 方案了，就是开始把我们的问题里面的约束移除，首先我们移除 sliding sum，出来的结果还是不可以满足。 但是当我们移除了 table 这个约束之后呢，我们发觉这个 MiniZinc 就发现有一个解了 看起来应该 就是我们 table 这个约束出了问题了 但是是什么问题我们还是不知道。 你们还记得我们之前学过 如果我们有一个循环的话，我们可以利用 trace 这个功能去跟踪一下，看看 到底是什么的约束标示了出来 所以呢我们就可以加进一个 trace 这样子的 函数在里面。 但是大家要注意，我们这个技巧呢一定要用 跟这个添加解这个技巧一起来用，不然呢这个跟踪是没有用的 好了加进了跟踪之后，我们发现这个就是 MiniZinc 的输出了 好了，我们看清楚的时候发觉呢，原来 MiniZinc 呢是会尝试测试 这一条的约束是否满足的 原来我们发觉呢，它是 问 [10,6] 这一条边是不是在我们这个路径图的边里面的 如果大家有留意的话，原来呢我们 去定义我们这个边这个 数据的时候，我们只是给了单向的边 我们而且呢是给，从来都是一个小的点到一个大的点，一个小的点 到了一个大的点，我们没有给相反方向的一个边出来的，所以当 这个关羽选取的路线是需要从第 10 点到了第 6 点的时候 然后这个条件就不可以满足了，所以我们整个问题就不可以满足了 所以要解决这个问题呢，我们需要 把我们边这个数据要修改一下 修改的方法其实很容易，我们本来呢 有 m 条边，我们当然呢要变成这个 2*m 条边，我们基本上就用，把我们原来的边 就 i 到 j 这条边，我们加上一个从 j 到 i 这条边 然后呢把它们加起来，我们定义一个新的数据叫 uedge 然后我们要保证关羽选取的路径是不是在 我们路径图上面的边呢，我们就不可以再用 edge了，我们就应该用 uedge。 那我们就可以把这个不可以满足的问题解决了 好了，我们刚才呢解决了一个丢失解的一个问题了 我们没有遇到丢失解最坏的情况 最坏的情况就是我们把我们的模型去跑，跑了很长的时间 还是没有一个解返回出来 我们还有什么其他东西可以做呢？其实还有另外两个可能的方案。 第一个 方案呢，我们就可以去把我们的模型简化。 就是说我们可以考虑把我们 问题的某一些方面，我们先不看它们，然后看看这个简化的版本的问题 可不可以找出一个解出来，也希望在这个过程当中利用这个简化版本的 解可以帮助我们去找到我们这个模型里面的问题在哪里 另外一个方案呢，就是可以把我们的模型分解，把它分开 成为一个两个三个不同的部分，然后我们先解决一个部分 利用第一个部分的解呢，才再去解决我们模型的第二个部分 然后也希望这个过程可以帮助我们好好地去理解我们的模型 的行为，也可以帮助我们找出我们的模型的错处在哪里 好了，我们来一个小结 模型的调试是非常困难的。 我们在 要面对的是丢失解的一个问题 我们也介绍了几个关键的方法去帮助我们解决这个问题 包括我们可以把我们的问题 的一个比较小的一个实例找出来，利用这个实例可以帮助我们 去好好地理解我们模型的行为，从而帮我们找出这个问题 在这个过程当中呢，我们也应该保证我们 模型里面表达的约束，是真的我们所希望表达的约束 第三就是一个非常有用的方案，就是我们 应该找出一个我们希望找到的解，然后把这个解呢 加入，化为一个约束加进我们的模型里面，也希望利用这个 技巧帮助我们找出我们的模型哪里出了问题 如果都不行的话，我们应该考虑把我们的模型里面某一些约束 停用啊或者是启用啊，然后从而可以找出哪一条约束是真的给我们麻烦的 最后一个方案呢就是我们可以把我们原来要解决的问题 做一个简化的版本出来，然后 利用这个简化的版本也帮助我们去找出我们模型里面的问题 调试是一个非常重要的技巧、 技能，所以我建议大家一定要好好地 去培养你们这一方面的技能 [空白录音]
