プレイヤーのすべての可能な組み合わせを計算してパーティションを形成するプロセスを最適化しようとしています。私の問題を理解するために、次の例を使用します。
たとえば、プレーヤーのセットがありN = {1,2,3,4,5}、このプレーヤーは次のように再グループ化され{1,2},{3,4},{5}ます。これは、プレイヤー 1 がプレイヤー 2 とシングル プレイヤーとしてプレイすることを意味します。プレーヤーの各グループには、一連の戦略または選択肢があります。各プレイヤーは、自分が所属したいグループを選択します。たとえば、グループ{1,2}には次の可能性が{{1,2};{1,2,3,4}}あります。つまり、プレイヤー{1,2}は一緒にいるか、グループに参加するかを選択します{3,4}。残りのプレイヤーに対する同じ説明:
{3,4}=>{{3,4};{3,4,5};{1,2,3,4}}
{5}=>{{5};{3,4,5}}
これで、同じ戦略を選択したプレイヤーのグループが新しいグループ (連合) を形成します。たとえば、 group{1,2}は戦略を選択しました。{1,2,3,4}つまり、players は、players{1,2}で新しいグループを形成したいと考えてい{3,4}ます。プレイヤー{3,4}は戦略を選択し{3,4,5}、プレイヤーは戦略を{5}選択します{3,4,5}。同じ戦略を選択したプレーヤーはグループ化され、次のようなプレーヤーの最終的なパーティションが形成され{1,2},{3,4,5}ます。プレイヤー{3,4,5}は同じ戦略を選択したため、グループ化され、プレイヤー{1,2}別の戦略を選んだので、彼らは一人でいました。このプロセスを再帰関数としてプログラムし、プレイヤーの許容可能なすべてのパーティションを取得しました。ここでの別の問題: 私の関数は可能なすべてのパーティションを生成し、多くの時間がかかる許容可能なものだけを取得します。
私の質問は、再帰関数を使用せずにこの問題を解決できるかどうかです。つまり、JCUDA で並列処理を使用するために、特に多くのプレーヤーと非常に多くのパーティションがある場合に、順次形式で使用します。ここでの理想的なソリューションは、MPI または JCUDA ですか?
import java.util.ArrayList;
import java.util.Hashtable;
public class Partitions {
public Hashtable<ArrayList<Integer>, ArrayList<ArrayList<Integer>>> HashTab = new Hashtable<ArrayList<Integer>,ArrayList<ArrayList<Integer>>>(); // The key is the chosen strategy(coalition) and the value is the group of players have chosen the same coalition(strategy).
// create partitions combination
public void CalculStrategiesCombination (int index, ArrayList<ObjectsCoalitions> PlayerCoalitions, int K,int L) {
index = index +1;
if(index < PlayerCoalitions.size()) {
for(int j =0; j< PlayerCoalitions.get(index).Coaltions.size(); j++) {
if(!this.HashTab.containsKey(PlayerCoalitions.get(index).Coaltions.get(j))) {
ArrayList<ArrayList<Integer>> e = new ArrayList<ArrayList<Integer>>();
e.add(PlayerCoalitions.get(index).Objects);
this.HashTab.put(PlayerCoalitions.get(index).Coaltions.get(j), e);
} else {
this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).add(PlayerCoalitions.get(index).Objects);
}
if(this.HashTab.size()<K) {
CalculStrategiesCombination (index, PlayerCoalitions,K,L);
}
if(this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).size()==1) {
this.HashTab.remove(PlayerCoalitions.get(index).Coaltions.get(j));
} else {
this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).remove(this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).size()-1);
}
}
} else {
// Treatment.......
}
}
}
public class ObjectsCoalitions {
public ArrayList<Integer>Objects = new ArrayList<Integer>(); // for example Objects = {1,2}
public ArrayList<ArrayList<Integer>> Coaltions = new ArrayList<ArrayList<Integer>> (); // coalitions (strategis)={{1,2};{1,2,3,4}}
}