0

原谅这个模糊的标题，我已经有几年没有做过任何与该领域相关的数学了，而且我的术语相当缺乏（我问这个问题的部分原因）。我确信有一个定义明确的算法/理论已经处理了我想要实现的目标，但我不能完全确定要找到它的词。

我将尝试描述我正在建模的情况：

给定一组物品 [a,b,c,d,e,f]，一个人可能会提议交易某些物品，例如，我可能将“a”换成“b”，而您可能会提供“2xc”为“e”。我可以收集所有这些交易并创建一个图表来概述所提供的选项。我有兴趣寻找特定的贸易路径，顺便说一句，贸易路径会给我带来多余的物品——我认为这种东西一定已经存在于金融领域（再次，我错过了数学）。

所以如果我有“a”并且想要“f”，并且我有以下可用路径：

a -> b, b -> f, c -> b, a-> 2(c), b -> a

我最终会得到

a -> b -> f

a -> (2)c -> b -> f    
      |
      c             (An additional c)

可能有我可以重复循环的地方，所以如果我使用上面的 b -> a 关系，我可以不断提取 c 因为多余的 c 项目。

我有理由确定我可以编写一个程序来执行此操作，但我非常喜欢理解此类问题背后的正确术语和方法。如果有人能指出我要阅读的特定主题的正确方向，或者如果我想要实现的目标有一个明显的名称，我将不胜感激。

再次为模糊性道歉。

4

1 回答 1

1

听起来像是典型的状态空间搜索问题。像BFS或迭代深化这样的算法可以找到最短的交易序列，甚至可以产生所有的可能性。

要应用这些算法，您必须重新定义图表。与其使用a和之类b的节点a -> b，不如定义一个状态空间，其中状态由有限数量的每个元素组成{a, b, c, f}（在这种情况下，整数的四元组就足够了）和一个应用所有可能的后继函数S交易给定的状态并构造一组后继状态。例如，在伪 Python 表示法中，

S({a: 1, b: 2, c: 0, f: 0}) = [{a: 0, b: 3, c: 0, f: 0},   # trade a for b
                               {a: 1, b: 1, c: 0, f: 1},   # trade b for f
                               {a: 1, b: 2, c: 2, f: 0},   # trade a for 2c
                               {a: 2, b: 1, c: 0, f: 0}]   # trade b for a

由于状态空间搜索是 AI 中的经典范式，因此大多数 AI 教科书都涵盖了它。特别是，我可以推荐Russell 和 Norvig 的AIMA，它的前几章非常详细地讨论了状态空间搜索。

于 2013-02-20T16:33:30.417 回答