[課題2]
教科書のプログラムでは，オペレータ間の競合解消戦略としてランダムなオペレータ選択を採用している．これを，あらかじめオペレータに優先度を付けておき，優先度が高いものから適用するような競合解消戦略に変更せよ．
- オペレータをキューに入れてクルクル回せばループしないし、いいんじゃないでしょーか
- つーことで作ってみます。
- それいいやん -- mt (2010-12-06 09:14:59)
- でも２回連続でリムーブしなきゃいかんとき、リムーブ→ピックアップ→リムーブ→ピックアップ とかのループにならんかな？ -- mt (2010-12-06 09:15:51)
- たぶんなるけど、そのループを解消すんのはむずそうだな -- こーへ (2010-12-06 23:49:10)
- 一回使ったインスタンシエーションを使わなくするor優先度を下げるなどでなんとかなるかも… -- こーへ (2010-12-06 23:50:01)
- 競合自体を起こさなくするためのゴールリストのソートアルゴリズム -- こーへ
- 説明は長くなるから、ソースだけ。聞きたいことあったら聞いてちょん -- こーへ (2010-12-15 21:02:49)
/*
* ゴールリストをプランニングしやすい順番にならべかえるメソッド
*
* @param ゴールリストを表すArrayList<String> goalList
*/
public void sortGoals(ArrayList<String> goalList){
/*
* step 1
*
*それぞれのゴール要素をADDリストに持つオペレータを1つずつ決定する
*/
ArrayList<Operator> theOperators = new ArrayList<Operator>();
HashMap<Operator,String> operatorsMap = new HashMap<Operator,String>();
for(int i = 0; i < goalList.size(); ++i){
ArrayList<Operator> conflict = new ArrayList<Operator>();
for(int j = 0; j < operators.size(); ++j){
ArrayList<String> theAddList = operators.get(j).getAddList();
for(int k = 0; k <theAddList.size(); ++k){
HashMap<String,String> aBinding = new HashMap<String,String>();
if((new Unifier()).unify(theAddList.get(k), goalList.get(i), aBinding)){
Operator instanced = operators.get(j).instantiate(aBinding);
conflict.add(instanced);
//ついでに動的な優先度決定指標となる1階層展開されたゴール要素を保存しておく
allGoals.addAll(instanced.getIfList());
}
}
}
//適応できるオペレータがない場合プランニング失敗
if(conflict == null) return;
//オペレータの競合が起こった場合静的な優先度に基づいてオペレータを1つに絞る
Operator anOperator = null;
int maxPriority = -1;
for(int j = 0; j < conflict.size(); ++j){
if(j == 0){
anOperator = conflict.get(j);
} else if(maxPriority < conflict.get(j).getPriority()){
maxPriority = conflict.get(j).getPriority();
anOperator = conflict.get(j);
}
}
theOperators.add(anOperator);
//ゴール要素とオペレータの対応関係を保存
operatorsMap.put(anOperator,goalList.get(i));
}
/*
* step 2
*
*オペレータのペアに対して一方がもう一方にどれだけ貢献する可能性があるかの尺度（以下"貢献度"と呼ぶ）を
*すべてのペアに対して計算し、それらを行列として保持する
*
* ここで
* オペレータA(opA)のオペレータB(opB)に対する貢献度 =
* （opAのADDリストに含まれるopBのIFリストの要素数 + opBのDELETEリストに含まれるopAのIFリストの要素数） (>= 0である)
* としている
*/
int size = operatorsMap.size();
Integer[][] contributionMat = new Integer[size][size];
//rowContributed は行列の各行の貢献度の和（各オペレータの非貢献度の和と考えられる）を要素に持つリスト
Integer[] rowContributed = new Integer[size];
for(int i = 0; i < size; ++i){
rowContributed[i] = 0;
for(int j = 0; j < size; ++j){
contributionMat[i][j] = 0;
}
}
for(int i = 0; i < size; ++i){
Operator columnOp = theOperators.get(i);
ArrayList<String> columnAddList = columnOp.getAddList();
ArrayList<String> columnDeleteList = columnOp.getDeleteList();
for(int j = 0; j < size; ++j){
Operator rowOp = theOperators.get(j);
ArrayList<String> rowIfList = rowOp.getIfList();
if(i != j){
for(int k = 0; k < rowIfList.size(); ++k){
for(int l = 0; l < columnAddList.size(); ++l){
if(rowIfList.get(k).equals(columnAddList.get(l))){
// if((new Unifier()).unify(rowIfList.get(k), columnAddList.get(l))){
contributionMat[i][j]++;
rowContributed[j]++;
}
}
for(int l = 0; l < columnDeleteList.size(); ++l){
if(rowIfList.get(k).equals(columnDeleteList.get(l))){
//if((new Unifier()).unify(rowIfList.get(k), columnDeleteList.get(l))){
contributionMat[j][i]++;
rowContributed[i]++;
}
}
}
}
}
}
//貢献度行列表示
for(int i =0; i<size; ++i){
for(int j =0;j<size;++j){
System.out.print(contributionMat[i][j]+" ");
}
System.out.println("");
}
/*
* すべてのオペレータの順序付けが完了するまでstep3,step4を繰り返す
*/
ArrayList<Integer> indexies = new ArrayList<Integer>();
for(int i = 0; i < size; ++i){
indexies.add(i);
}
int d = 0;
Operator[] sortedOp = new Operator[size];
while(!indexies.isEmpty()){
/*
* step 3
* 非貢献度が最小のオペレータを調べる
* 複数ある場合はすべて保持
*/
Integer[] index = new Integer[size];
int c = 0;
int min = 0;
for(int j = 0; j < indexies.size(); ++j){
if(j == 0){
min = rowContributed[indexies.get(j)];
index[c++] = indexies.get(j);
} else if(rowContributed[indexies.get(j)] < min){
min = rowContributed[indexies.get(j)];
c = 0;
index[c++] = indexies.get(j);
} else if(rowContributed[indexies.get(j)] == min){
index[c++] = indexies.get(j);
}
}
/*
* step 4
* step 3で得られたオペレータを初期値として、
* 貢献度を参考に効率的と考えられる順序でオペレータを取り出して行く
*/
boolean increase = true;
while(increase){
increase = false;
//抽出したオペレータから順に保存
for(int i = 0; i < c; ++i){
System.out.println(d+theOperators.get(index[i]).name);
sortedOp[d++] = theOperators.get(index[i]);
indexies.remove(index[i]);
}
//次に貢献されているオペレータを抽出
int c1 = 0;
Integer[] index1 = new Integer[size];
for(int i = 0; i < c; ++i){
for(int j = 0; j < size; ++j){
if(contributionMat[index[i]][j] > 0 && indexies.contains(j)){
//他のオペレータからも貢献されている場合、それらすべてのオペレータが取り出されてからこのオペレータを取り出す
boolean thisIsMax = true;
for(int k = 0; k < size; ++k){
if(k != index[i] && contributionMat[k][j] >= contributionMat[index[i]][j]){
contributionMat[index[i]][j] = 0;
thisIsMax = false;
break;
}
}
if(thisIsMax){
index1[c1++] = j;
increase = true;
}
}
}
}
c = c1;
index = index1;
}
//書き換えられた貢献度行列を表示
for(int i = 0; i < size; ++i){
for(int j = 0; j < size; ++j)
System.out.print(contributionMat[i][j]+" ");
System.out.println("");
}
/*
//残ったオペレータを取り出す
for(int i : indexies){
sortedOp[d++] = theOperators.get(i);
}
*/
}
//所与のゴールリストを並べ替える
goalList.clear();
for(int i = 0; i < size; ++i){
goalList.add(operatorsMap.get(sortedOp[i]));
//System.out.println(sortedOp[i].name);
}
}
最終更新：2010年12月15日 22:00
