用途:当问题要求以最少步数或操作次数达到目标状态时(如倒水谜题、滑块拼图),把问题建模为状态空间上的广度优先搜索(BFS)。
主要能力与规则:状态用能完整描述当前情形的元组表示,例如 (bucket_a, bucket_b);从每个状态枚举所有合法转移并生成下一状态;用基于状态元组的 visited 集合避免循环;从起始状态做 BFS,首次弹出与目标匹配的状态时,其距离即最少步数;同时记录目标值所在容器及另一容器的值。
必要用法:绝不能跳过 visited 检查,否则循环会导致死循环;禁止的移动应编码为转移上的过滤器,而不是写成特例。倒水示例的转移包括:fill A、fill B、empty A、empty B、pour A→B、pour B→A。从 (0, 0) 开始 BFS,首次出现含目标值的状态时,该距离即最小值。
边界情况:若起始容器被禁止作为“先填错的那个”立即移动,应将其编码为初始转移上的过滤器。
限制:资料未提供具体实现代码、性能数据、支持平台或收费信息。