基于PROLOG实现指定部件类型的最低成本配置求解方案问询

嘿，作为Prolog新手碰到这种带递归依赖的最优配置问题，确实得好好捋捋思路，咱们一步步来拆解解决～

首先先把给定的部件规则规整成Prolog可直接使用的事实（我帮你调整了格式，更符合Prolog规范）：

% part(Name, Type, Number, RequiredTypes, Size, Price)
% 字段说明：
% - Name: 部件唯一标识
% - Type: 部件所属类型
% - Number: 同类型内的部件编号
% - RequiredTypes: 依赖规则（"-"表示无依赖；格式如"2*b"、"1*b && 2*c"、"1*c-1"）
% - Size: 部件尺寸（0.5为半尺寸，1为全尺寸）
% - Price: 部件成本
part(a-1, a, 1, "2*b", 0.5, 60).
part(a-2, a, 2, "3*b", 1.0, 25).
part(b-1, b, 1, "2*c", 0.5, 25).
part(b-2, b, 2, "-", 1, 45).
part(c-1, c, 1, "-", 0.5, 5).
part(c-2, c, 2, "-", 0.5, 10).
part(d-1, d, 1, "1*b && 2*c", 0.5, 45).
part(d-2, d, 2, "1*c-1", 0.5, 25).

你的需求是：给定一个部件类型集合（比如{a,b}），输出成本最低、成本相同时空间最紧凑的完整配置组合——这里的完整配置不仅要包含输入类型的部件，还要递归包含所有依赖的下级部件，直到无依赖的基础部件。

本质上这是一个递归枚举+多维度排序筛选的问题，核心步骤是：

1. 解析依赖规则，把字符串格式的依赖转换成Prolog可处理的结构化数据
2. 递归展开每个部件的所有直接/间接依赖，生成所有可能的完整配置组合
3. 计算每个组合的总成本和总尺寸
4. 按「成本优先（升序），尺寸次之（升序）」的规则筛选最优解

1. 依赖规则解析 #

首先需要把RequiredTypes字段的字符串转换成结构化的依赖项，方便后续处理。比如：

• "2*b" → [{2, type(b)}]（需要2个b类型部件）
• "1*b && 2*c" → [{1, type(b)}, {2, type(c)}]（需要1个b类型+2个c类型部件）
• "1*c-1" → [{1, part(c-1)}]（需要1个具体的c-1部件）
• "-" → []（无依赖）

实现代码示例：

% 解析整个依赖字符串
parse_requirements("-", []).
parse_requirements(Str, Requirements) :-
    split_string(Str, "&&", " ", RawReqs), % 按&&拆分多个依赖条件
    maplist(parse_single_requirement, RawReqs, Requirements).

% 解析单个依赖项（比如"2*b"或"1*c-1"）
parse_single_requirement(RawReq, {Count, Target}) :-
    split_string(RawReq, "*", " ", [CountStr, TargetStr]),
    number_string(Count, CountStr),
    % 判断目标是类型还是具体部件
    (   sub_string(TargetStr, 0, 1, _, TypeChar) % 类型是单个字符（a/b/c/d）
    ->  atom_string(Type, TypeChar),
        Target = type(Type)
    ;   atom_string(Part, TargetStr),
        Target = part(Part)
    ).

2. 递归展开部件依赖 #

接下来需要写一个递归函数，把单个部件展开成包含自身和所有依赖的完整部件列表。这里要注意：对于需要多个同类型部件的情况，要枚举所有可能的部件组合（比如2个b类型部件，可能是[b-1,b-1]、[b-1,b-2]、[b-2,b-2]）。

实现代码示例：

% 展开单个部件到完整依赖列表
expand_part(Part, [Part | AllDeps]) :-
    part(Part, _, _, RequiredTypes, _, _),
    parse_requirements(RequiredTypes, Reqs),
    expand_requirements(Reqs, AllDeps).

% 展开一组依赖项
expand_requirements([], []).
expand_requirements([{Count, Target} | Rest], CombinedDeps) :-
    % 生成满足当前依赖的Count个部件
    generate_components(Target, Count, Components),
    % 递归展开每个生成的部件
    maplist(expand_part, Components, DepLists),
    append(DepLists, DepsFromThisReq),
    % 处理剩余依赖
    expand_requirements(Rest, DepsFromRest),
    append(DepsFromThisReq, DepsFromRest, CombinedDeps).

% 生成满足目标的部件列表
% 目标是类型时，生成Count个该类型的任意部件（允许重复）
generate_components(type(Type), Count, Components) :-
    findall(Part, part(Part, Type, _, _, _, _), AvailableParts),
    length(Components, Count),
    maplist(member(AvailableParts), Components).
% 目标是具体部件时，生成Count个该部件
generate_components(part(Part), Count, Components) :-
    length(Components, Count),
    maplist(=(Part), Components).

3. 生成输入类型的所有可能配置 #

对于给定的输入类型集合（比如{a,b}），我们需要先枚举该类型下的所有部件，然后生成所有可能的初始部件组合（每个输入类型至少选一个），再展开每个组合的完整依赖：

% 展开一组初始部件到完整配置
expand_part_list([], []).
expand_part_list([Part | Rest], FullConfig) :-
    expand_part(Part, PartDeps),
    expand_part_list(Rest, RestDeps),
    append(PartDeps, RestDeps, FullConfig).

% 生成输入类型的所有可能完整配置
generate_all_configs(InputTypes, AllUniqueConfigs) :-
    % 收集输入类型对应的所有部件
    findall(TypePart, (member(Type, InputTypes), part(TypePart, Type, _, _, _, _)), TypeParts),
    % 生成所有初始部件组合（每个输入类型选一个）
    findall(InitialCombo, maplist(member(TypeParts), InitialCombo), InitialCombos),
    % 展开每个初始组合到完整配置
    findall(FullConfig, (member(Initial, InitialCombos), expand_part_list(Initial, FullConfig)), AllConfigs),
    % 去重（不同初始组合可能展开出相同的完整配置）
    sort(AllConfigs, AllUniqueConfigs).

4. 计算配置的成本与尺寸并筛选最优解 #

最后一步是计算每个完整配置的总成本和总尺寸，然后按规则排序筛选：

% 计算单个部件的成本和尺寸
get_part_metrics(Part, Cost-Size) :-
    part(Part, _, _, _, Size, Cost).

% 计算完整配置的总成本和总尺寸
calculate_config_metrics(Config, TotalCost, TotalSize) :-
    maplist(get_part_metrics, Config, Metrics),
    split_list(Metrics, Costs, Sizes),
    sum_list(Costs, TotalCost),
    sum_list(Sizes, TotalSize).

% 筛选最优配置
find_optimal_config(InputTypes, OptimalConfig, TotalCost, TotalSize) :-
    generate_all_configs(InputTypes, AllConfigs),
    % 给每个配置绑定成本和尺寸
    findall((TotalCost, TotalSize, Config), (
        member(Config, AllConfigs),
        calculate_config_metrics(Config, TotalCost, TotalSize)
    ), ConfigsWithMetrics),
    % 排序规则：先按成本升序，成本相同则按尺寸升序
    sort(ConfigsWithMetrics, SortedConfigs),
    % 取第一个即为最优解
    SortedConfigs = [(TotalCost, TotalSize, OptimalConfig) | _].

• 组合枚举的完整性：比如需要3个b类型部件时，要确保枚举所有可能的重复组合（比如[b-1,b-1,b-2]这种），上面的generate_components用maplist(member(AvailableParts), Components)可以实现这一点，因为member允许重复选择。
• 去重优化：不同的初始部件组合可能展开出完全相同的完整配置，用sort去重可以避免重复计算，提升效率。
• 递归终止：当部件的依赖为"-"时，parse_requirements返回空列表，递归自动终止，只包含部件自身。

比如输入类型集合{a}，调用find_optimal_config([a], Optimal, Cost, Size)，就会得到成本最低的a部件配置（a-2加上其依赖的3个b部件的最优组合，再加上b部件的依赖）。

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