1

我有一个代理列表a = {a1, a2, a3,..., an}，其中每个代理可以与零个或多个其他代理配对。例如，对于n = 6，我可以有：

a1: a2, a3, a5
a2: a1, a3, a4
a3: a1, a2. a5
a4: a2
a5: a1, a3
a6:

每一对相互交互，并且每个代理作为交互的结果获得一个值（例如，他们可以玩游戏，但交互的细节可以在这里抽象掉）。我对基于给定的成对结构（例如上述）计算和存储这些交互的结果感兴趣。

显然，一个简单的算法将遍历每个代理，然后逐个计算与他的每个交互伙伴的成对交互。然而，同样明显的是，这种方法会重复一些（或可能很多）计算。使用上面的示例：

当我们完成 agenta1时，我们已经获得了、 和的结果(a1, a2)，因此当我们对 agent 、和进行计算时，这些对之间的后续计算就变得多余了，(a1, a3)(a1, a5)a2a3a5

一种改进的算法是在两个维度（即沿着代理本身和沿着它们各自的伙伴）按升序对输入结构进行排序，如上例所示，因此对于每个代理（例如a3），我们只需要计算该代理 ( a3) 与比他“更高”的代理 ( )a5之间的交互，因为我们知道他与“下”伙伴 ( (a1, a3), (a2, a3)) 之间的交互已经计算过了。

我想知道这个问题是否有不同的更好的算法？更好，我的意思是在时间和空间方面更有效的计算。

4

5 回答 5

3

是的，这会尝试将每一对添加到集合中两次，但我觉得这可能比条件更有效。有人想尝试为替代方案计时吗？

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}
pairs = {(k,v) for k in agents for v in agents[k]}

这仍然是 O(n)，所以在效率方面胜过任何涉及排序的事情

通过使用，您可能会获得轻微的加速

pairs = {(k,v) for k,vs in agents.iteritems() for v in vs}
于 2012-06-07T01:12:54.880 回答
2

您可以将代理 ID 与以下内容进行比较：

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}

interactions = []
for agent, connections in agents.iteritems():
    interactions.extend((agent, connection) for connection in connections if agent < connection)

print interactions
# [('a1', 'a2'), ('a1', 'a3'), ('a1', 'a5'), ('a3', 'a5'), ('a2', 'a3'), ('a2', 'a4')]
于 2012-06-06T23:42:08.333 回答
0

itertools救援

>>> from itertools import combinations
>>> agents=['a1','a2','a3','a4','a5']
>>> list(combinations(agents, 2))
[('a1', 'a2'), ('a1', 'a3'), ('a1', 'a4'), ('a1', 'a5'), 
 ('a2', 'a3'), ('a2', 'a4'), ('a2', 'a5'),
 ('a3', 'a4'), ('a3', 'a5'),
 ('a4', 'a5')]
>>>
于 2012-06-06T23:28:13.673 回答
0

据我了解您的问题，您为什么不考虑二维矩阵？在第一阶段，如果两个代理可以相互合作，只需将交叉单元设置为 1。在第二阶段，只需围绕矩阵设置一个循环，并仅在那些具有互连的代理之间计算一些值（即单元格等于 1）。而不是 1 会有一个真正的价值。所以在那种情况下，你不需要做多余的计算。唯一多余的部分是在矩阵中填充计算值两次。

于 2012-06-06T23:41:05.520 回答
0

基于@gnibbler的回答，我想出了这个：

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}

pairs = {tuple(sorted((k,v))) for k in agents for v in agents[k]}

仍然需要排序，但仅限于一对。

于 2012-06-07T15:38:26.993 回答