Bridge-Flashlight Puzzle的Prolog实现求助：四人过桥问题编码困境

嘿，我太懂这种“逻辑捋顺了但代码死活写不出来”的卡壳感了！过桥问题的最优解核心其实就两种策略，把它转化为Prolog的状态搜索其实没那么绕，咱们一步步拆解着来：

咱们用一个复合项来描述每个时刻的状态：state(Left, Right, TotalTime, ActionPath)，各部分含义：

• Left：还在桥左边的人（用原子表示，比如father）
• Right：已经到桥右边的人
• TotalTime：累计花费的时间
• ActionPath：记录每一步的操作，方便最后复盘整个过程

初始状态就是所有人在左边，时间为0，路径为空：state([father, mother, child, grandma], [], 0, [])
目标状态就是左边没人，右边凑齐4个人。

过桥的操作分两类：要么两个人一起从左到右，要么一个人拿手电筒从右回左。咱们用Prolog的规则来实现这两种转移：

首先先定义每个人的过桥耗时：

person_time(father, 1).
person_time(mother, 2).
person_time(child, 5).
person_time(grandma, 10).

然后是两人从左到右的规则：

% 从左边选两个人过桥，时间取较慢者的耗时
move(state(Left, Right, Time, Path), state(NewLeft, NewRight, NewTime, UpdatedPath)) :-
    % 从左边列表里选出两个人
    select(Person1, Left, TempLeft),
    select(Person2, TempLeft, NewLeft),
    % 拿到两人的耗时，取最大值
    person_time(Person1, T1),
    person_time(Person2, T2),
    StepTime is max(T1, T2),
    % 更新累计时间和操作路径
    NewTime is Time + StepTime,
    append(Path, [cross(Person1, Person2, StepTime)], UpdatedPath),
    % 更新两边的人员列表
    append(Right, [Person1, Person2], NewRight).

接着是一人从右回左送手电筒的规则：

% 从右边选一个人回来送手电筒，时间取这个人的耗时
move(state(Left, Right, Time, Path), state(NewLeft, NewRight, NewTime, UpdatedPath)) :-
    % 右边至少得有一个人才能回来（不然手电筒没了）
    select(Person, Right, NewRight),
    person_time(Person, T),
    % 更新时间和路径
    NewTime is Time + T,
    append(Path, [return(Person, T)], UpdatedPath),
    append(Left, [Person], NewLeft).

因为咱们要找耗时最短的方案，广度优先搜索（BFS）是最合适的——它会按时间顺序遍历所有可能的状态，第一个到达目标状态的就是最优解。咱们写个BFS的实现：

% 终止条件：找到左边没人的状态，返回时间和路径
bfs([(state([], Right, Time, Path), Time)|_], MinTime, MinPath) :-
    length(Right, 4), % 一家四口都到右边了
    MinTime = Time,
    MinPath = Path.

% 递归遍历队列里的每个状态，生成下一层状态继续搜索
bfs([(CurrentState, _)|Queue], MinTime, MinPath) :-
    % 生成当前状态能转移到的所有新状态
    findall((NewState, NewTime), move(CurrentState, NewState), NextStates),
    % 把新状态加到队列末尾，继续BFS
    append(Queue, NextStates, NewQueue),
    bfs(NewQueue, MinTime, MinPath).

% 启动搜索的入口
solve(MinTime, MinPath) :-
    InitialState = state([father, mother, child, grandma], [], 0, []),
    bfs([(InitialState, 0)], MinTime, MinPath).

运行solve(T, P).，你会得到最优时间T=17，对应的路径P是：
[cross(father, mother, 2), return(father, 1), cross(child, grandma, 10), return(mother, 2), cross(father, mother, 2)]
把时间加起来：2+1+10+2+2=17，完全符合最优解的逻辑。

如果要处理更多人的情况，只要修改初始状态的人员列表，以及BFS终止条件里的length(Right, N)（N是总人数）就行，通用性很强。

内容的提问来源于stack exchange，提问作者user9404193