1

エージェントのリストがa = {a1, a2, a3,..., an}あります。各エージェントは、0個以上の他のエージェントとペアになっている可能性があります。たとえば、の場合、次のn = 6ようにできます。

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

各ペアは相互作用し、各エージェントはこの相互作用の結果として値を取得します（たとえば、ゲームをプレイすることはできますが、相互作用の詳細はここで抽象化できます）。上記のような特定のペアワイズ構造に基づいて、これらの相互作用の結果を計算して保存することに興味があります。

明らかに、単純なアルゴリズムは、各エージェントを調べてから、相互作用する各パートナーとのペアワイズ相互作用を1つずつ計算することです。ただし、このアプローチが一部の（または潜在的に多くの）計算を複製することも明らかです。上記の例を使用すると：

エージェントの処理が終了するまでに、、、、およびa1の結果はすでに取得されているため(a1, a2)、エージェント、、、(a1, a3)および、(a1, a5)の処理を行うと、これらのペア間の後の計算が冗長になります。a2a3a5

改善されたアルゴリズムは、上記の例のように、入力構造を両方の次元で昇順で（つまり、エージェント自体とそれぞれのパートナーに沿って）並べ替えることです。これにより、各エージェント（たとえばa3）について、このエージェント（a3）と彼よりも「高い」エージェント（）の間の相互作用は、彼自身と「低い」パートナー（ 、）の間の相互作用がすでに計算されていることがa5わかっているためです。(a1, a3)(a2, a3)

この問題には別のより良いアルゴリズムがあるのだろうか？より良いのは、時間と空間の両方の観点から、より効率的な計算を意味します。

4

5 に答える 5

3

はい、これは各ペアをセットに2回追加しようとしますが、これは条件付きよりも効率的かもしれないと感じています. 代替案のタイミングを試してみたい人はいますか?

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

@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 に答える