出个算法题，大家练练手【3个和尚和3个妖怪过河】

下标越界

老师和知道方法的高手们千万不要马上给出通解，容我想想。

香川群子

下标越界 发表于 2018-9-9 13:22
老师和知道方法的高手们千万不要马上给出通解，容我想想。

对的，尽量自己先想办法。

可以在某个位置卡住时，提出讨论，但首先要自己反复思考，这样进步最快。

香川群子

wuliaolang 发表于 2018-9-7 13:59
想了一个方法，到达终点后在返回过程中，字典记录每个节点的步数和它的上一个节点，步数相同的上一个节点 ...

思路是对的。

如何实现，也需要多练手，否则不会有进步。哈哈。

香川群子

yipzx 发表于 2018-9-7 13:49
给出通解后，建议再加一个条件，比较好玩，也是在广度搜索上进一步的一个经典的算法。题目为，如果和尚和 ...

这个就是增加权重值的意思了。

如果较复杂，那么基本上就要用动态规划算法了。

香川群子

wuliaolang 发表于 2018-9-7 14:29
我把想法做个图，这样比较清晰

虽然没有明确说总步数最少，但是如果排除了【相同状态的重复】，那么实际步数总是最少的。

即：状态1 → 状态2 → 状态3 → 状态2 → 状态3 类似这样会反复进入相同状态是不被允许的，会进入死循环。

同样，状态1 → 状态2 → 状态3 → 状态4 → 状态2 这最后3步也是不被允许的。因为又回到了状态2。

香川群子

excelvlookup 发表于 2018-9-7 17:35
说的太复杂了，我对此题的理解是从A把人运到B，满足最短。只需考虑以下条件
如不考虑别的条件：A到B两人， ...

从条件分析来看，是正确的。

但是，需要实现的具体过程。
能够给出具体过程的方法，就是算法。

wuliaolang

香川群子 发表于 2018-9-10 09:58
虽然没有明确说总步数最少，但是如果排除了【相同状态的重复】，那么实际步数总是最少的。

即：状态1  ...

我排除掉了终点的取最小步数
状态1 → 状态2 → 状态3 → 状态7 → 状态8
状态1 → 状态4 → 状态6 → 状态8
两条路线都成立，因为之前找路线的时候已经排除了走回头路，所以一条路线不会出现两个相同状态。
我试验和尚3妖怪2的时候发现结果只有步数7的结果，并没有一条独立的长路线。
还是没能完全理解题目最简的意思

zopey

wuliaolang 发表于 2018-9-10 12:18
我排除掉了终点的取最小步数
状态1 → 状态2 → 状态3 → 状态7 → 状态8
状态1 → 状态4 → 状态6 →  ...

不知道理解的 对不对

yipzx

帖子没人跟啊，可能大家也懒得搜索，给一个具体思路吧，广度搜索的通解，希望大家以后碰到这种问题都可以这么思考。首先，我们这么考虑这个问题，想象每一次过河都是一个场景scence。那么题目的意思变化为，从开始船在左边，左边3个和尚3个妖怪。变成船在右边，左边0个和尚，0个妖怪（右边的情况你从左边可以算出来，而且是对应的，简化一下，不写出来），得解。从初始开始，场景变化如下图：

yipzx

接着，我们考虑，从初始场景出发，第一步能否到达目的地，到达得解。如果到达不了，我们将第一步到达的地方做为出发点，重新出发，再测试第二步，还到达不了，我们测试第三步，直到目的地。完整思路就在这里。如何用程序实现呢？我们需要的数据是什么样子的，是不是这样：scence0=left-3-3, scence0的下一步 即scence0.next=array(right-3-1,right-2-2,....)。VBA没有这样的数据结构，我们可以构建一个，当然你也可以用嵌套array，但是写出来的代码不直观，别人看不懂。这样的习惯不好。好了，我们先构建这个数据结构。
Public Type scence
    boat_location As String
    monks As Long
    monsters As Long
    next_scence 'array or collection or dictionary of scence
End Type