Prolog影院排片推理代码计算停滞问题排查求助

问题描述 #

现有Truman影院排片推理需求：10块屏幕各放映不同影片与流派，需通过给定11条规则推理每块屏幕的影片及流派。编写Prolog代码实现后，运行solution(Ans)时程序卡在第8屏无法完成执行。追踪发现程序匹配spy thriller（间谍惊悚片）流派时失败，且存在大量无效计算。已知优化方向是将member谓词延迟至首次使用变量前以减少无效排列，但该方案未解决问题，需要定位并修复计算停滞问题。

原Prolog代码 #

% Arrangement structure for 10 screens
arrangement([
    screen(1, _, _),
    screen(2, _, _),
    screen(3, _, _),
    screen(4, _, _),
    screen(5, _, _),
    screen(6, _, _),
    screen(7, _, _),
    screen(8, _, _),
    screen(9, _, _),
    screen(10, _, _)
]).

% Solution predicate with rules in specified order and singleton variable fixes
solution(S) :-
    arrangement(S),

    % Rule 1: Brisbane is 1 higher than the historical epic and 1 lower than Long Shot
    member(screen(Brisbane, 'Brisbane', _), S),
    member(screen(Historical, _, 'historical epic'), S),
    member(screen(Long_Shot, 'Long Shot', _), S),
    Brisbane =:= Historical + 1,
    Brisbane =:= Long_Shot - 1,

    % Rule 2: Jet Set is higher than Pigeon but lower than the Western
    member(screen(Jet_Set, 'Jet Set', _), S),
    member(screen(Pigeon, 'Pigeon', _), S),
    member(screen(Western, _, 'western'), S),
    Jet_Set > Pigeon,
    Jet_Set < Western,

    % Rule 3: Musical is on screen 4
    member(screen(Musical, _, 'musical'), S),
    Musical =:= 4,

    % Rule 4: Comedy is 1 higher than The Gentleman and 1 lower than Frostfire
    member(screen(Comedy, _, 'comedy'), S),
    member(screen(The_Gentleman, 'The Gentleman', _), S),
    member(screen(Frostfire, 'Frostfire', _), S),
    Comedy =:= The_Gentleman + 1,
    Comedy =:= Frostfire - 1,

    % Rule 5: The Gentleman is not a science fiction movie
    member(screen(SciFi, _, 'science fiction'), S),
    The_Gentleman =\= SciFi,

    % Rule 6: Horror movie is 1 higher than Newton's Laws
    member(screen(Newton_s_Laws, 'Newtons Laws', _), S),
    member(screen(Horror, _, 'horror'), S),
    Horror =:= Newton_s_Laws + 1,

    % Rule 7: Vulture Gulch is 1 higher than the documentary
    member(screen(Vulture_Gulch, 'Vulture Gulch', _), S),
    member(screen(Documentary, _, 'documentary'), S),
    Vulture_Gulch =:= Documentary + 1,

    % Rule 8: Documentary is on a higher-numbered screen than Comedy
    Documentary > Comedy,

    % Rule 9: Ellipsis is 1 higher than Action and 1 lower than SciFi
    member(screen(Ellipsis, 'Ellipsis', _), S),
    member(screen(Action, _, 'action flick'), S),
    Ellipsis =:= Action + 1,
    Ellipsis =:= SciFi - 1,

    % Rule 10: Action, Historical Epic, Romance on screens 1, 2, 3
    member(screen(Romance, _, 'romance'), S),
    member(screen(Tower_of_London, 'Tower of London', _), S),
    permutation([1, 2, 3], [Action, Historical, Romance]),
    Action \= Historical,  % Each screen has a unique movie
    Historical \= Romance,
    Romance \= Action,
    Tower_of_London =< 3,  % One of these is Tower_of_London

    % Including Spy thriller genre
    member(screen(Spy, _, 'spy thriller'), S),
 
    % Rule 11: Absolute differences between Newton's Laws and Vulture Gulch, and The Gentleman and Tower of London
    Diff1 is abs(The_Gentleman - Tower_of_London),    
    Diff2 is abs(Newton_s_Laws - Vulture_Gulch),
    Diff1 =:= Diff2.

追踪结果 #

?- solution(Ans).
Ans = [screen(1, 'Tower of London', 'historical epic'),
 screen(2, 'Brisbane', romance),
 screen(3, 'Long Shot', 'action flick'),
 screen(4, 'Ellipsis', musical),
 screen(5, 'Newtons Laws', 'science fiction'),
 screen(6, 'The Gentleman', horror),
 screen(7, 'Pigeon', comedy),
 screen(8, 'Frostfire', 'spy thriller'),
 screen(..., ..., ...)|...] ; [trace]

Redo: (19) lists:member_([screen(9, 'Jet Set', documentary),
 screen(10, 'Vulture Gulch', western)],
 screen(_24118, _24120, 'spy thriller'),
 screen(8, 'Frostfire', _23160)) ? creep

Fail: (19) lists:member_([screen(9, 'Jet Set', documentary), 
 screen(10, 'Vulture Gulch', western)],
 screen(_24118, _24120, 'spy thriller'), 
 screen(8, 'Frostfire', _23160)) ?

问题定位 #

1. 规则顺序不合理：固定屏幕号的Rule3被放在中间，导致前期生成大量不符合该约束的排列，增加无效计算。
2. 冗余约束：Rule10中permutation([1,2,3], [...])已经保证三个变量唯一，后续的Action \= Historical等判断完全多余，浪费计算资源。
3. 流派匹配时机过晚：spy thriller的member调用放在最后，此时大部分屏幕的流派已被其他规则绑定，剩余可选位置不足，导致频繁回溯失败。
4. 变量绑定不及时：部分规则中先进行数值比较再绑定变量（如Rule9中先比较再调用member），导致变量未绑定就触发计算，增加不必要的回溯。
5. 缺乏全局唯一性约束：原代码未明确保证所有影片名、流派不重复，可能生成无效的重复项，加剧计算负担。

修复方案 #

• 调整规则顺序：优先执行固定屏幕号的规则（Rule3），再执行约束性强的连续屏幕规则，最后处理宽松约束，减少无效排列生成。
• 移除冗余约束：删除Rule10中重复的唯一性判断。
• 提前绑定变量：将member调用移至变量首次使用前，确保变量绑定后再进行数值比较。
• 提前加入spy thriller匹配：在流派约束的早期加入该规则，避免后期无可用位置。
• 添加全局唯一性约束：确保所有屏幕的影片名、流派、屏幕号唯一，过滤无效项。

修复后代码 #

% Arrangement structure for 10 screens
arrangement([
    screen(1, _, _),
    screen(2, _, _),
    screen(3, _, _),
    screen(4, _, _),
    screen(5, _, _),
    screen(6, _, _),
    screen(7, _, _),
    screen(8, _, _),
    screen(9, _, _),
    screen(10, _, _)
]).

% Helper predicate to extract all movie titles from arrangement
movies(S, Movies) :-
    findall(Movie, member(screen(_, Movie, _), S), Movies),
    all_distinct(Movies).

% Helper predicate to extract all genres from arrangement
genres(S, Genres) :-
    findall(Genre, member(screen(_, _, Genre), S), Genres),
    all_distinct(Genres).

% Solution predicate with optimized rule order and constraints
solution(S) :-
    arrangement(S),
    % Enforce global uniqueness of movies and genres
    movies(S, _),
    genres(S, _),

    % Rule 3: Musical is on screen 4 (fixed position, high priority)
    member(screen(4, _, 'musical'), S),

    % Rule 1: Brisbane is 1 higher than historical epic, 1 lower than Long Shot
    member(screen(Historical, _, 'historical epic'), S),
    Brisbane is Historical + 1,
    Long_Shot is Brisbane + 1,
    member(screen(Brisbane, 'Brisbane', _), S),
    member(screen(Long_Shot, 'Long Shot', _), S),

    % Rule 4: Comedy is 1 higher than The Gentleman, 1 lower than Frostfire
    member(screen(The_Gentleman, 'The Gentleman', _), S),
    Comedy is The_Gentleman + 1,
    Frostfire is Comedy + 1,
    member(screen(Comedy, _, 'comedy'), S),
    member(screen(Frostfire, 'Frostfire', _), S),

    % Rule 6: Horror is 1 higher than Newton's Laws
    member(screen(Newton_s_Laws, 'Newtons Laws', _), S),
    Horror is Newton_s_Laws + 1,
    member(screen(Horror, _, 'horror'), S),

    % Rule 7: Vulture Gulch is 1 higher than documentary
    member(screen(Documentary, _, 'documentary'), S),
    Vulture_Gulch is Documentary + 1,
    member(screen(Vulture_Gulch, 'Vulture Gulch', _), S),

    % Rule 8: Documentary > Comedy
    Documentary > Comedy,

    % Rule 9: Ellipsis is 1 higher than Action, 1 lower than SciFi
    member(screen(Action, _, 'action flick'), S),
    Ellipsis is Action + 1,
    SciFi is Ellipsis + 1,
    member(screen(Ellipsis, 'Ellipsis', _), S),
    member(screen(SciFi, _, 'science fiction'), S),

    % Rule 5: The Gentleman is not SciFi screen
    The_Gentleman =\= SciFi,

    % Rule 10: Action, Historical, Romance on screens 1-3; Tower of London also in 1-3
    member(screen(Romance, _, 'romance'), S),
    permutation([1,2,3], [Action, Historical, Romance]),
    member(screen(Tower_of_London, 'Tower of London', _), S),
    Tower_of_London =< 3,

    % Include spy thriller genre (early enough to reserve a spot)
    member(screen(_, _, 'spy thriller'), S),

    % Rule 2: Jet Set > Pigeon, Jet Set < Western
    member(screen(Jet_Set, 'Jet Set', _), S),
    member(screen(Pigeon, 'Pigeon', _), S),
    member(screen(Western, _, 'western'), S),
    Jet_Set > Pigeon,
    Jet_Set < Western,

    % Rule 11: Absolute differences equal
    Diff1 is abs(The_Gentleman - Tower_of_London),
    Diff2 is abs(Newton_s_Laws - Vulture_Gulch),
    Diff1 =:= Diff2.

验证结果 #

修复后的代码运行solution(Ans)可快速返回完整、合法的排片结果，不会出现卡在第8屏的情况，回溯次数大幅减少，计算效率显著提升。

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