State

L7. Search for Vacuum Problem
Application of Searching Algorithms
Continue doing ex6
Problem Description
• Apply the program to the vacuum problem
in the next page.
(Searching a path from an initial state to the goal state)
• 次のページにあるような「掃除機問題」を解く
プログラムを前回までに学んだことを使って
作成してください。
（初期状態（スタート）から目標状態（ゴール）までのパスを求
めてください）
The Vacuum Problem
The vacuum world: 2 squares
vacuum
0
2
4
6
1
3
5
7
dirt
State（状態）: one of the eight states above.（上の8状態が全て）
Operators（操作、アクション）: move left（左に移動）, move right（右に移
動）, suck（吸取る）.
start-state（初期状態）:Right room has dirt, left room has dirt and vacuum is
in left room.（上の図の0）
goal-state（目標状態）: no dirt left in any square.（上の図の6または7）
Hint for the Vacuum Problem
• どのようにして状態空間を作
るかがポイントです！
Hint for the Vacuum Problem
前回課題の状態空間を思い出してください。
0
2
1
5
3
7
6
8
9
4
Hint for the Vacuum Problem
• 前回課題と今回課題の比較
– 前回課題の「都市」に相当するのが今回の「状態（state）」
です。
– 前回課題では「都市」が全部で10個でしたが、今回の課
題は「状態（state）」が全部で8個です。
– 前回課題ではある「都市」に隣接した「都市」は子ノード
（Children）として扱われましたが、今回の課題ではある
「状態」から移行可能な次の「状態」を子ノードとして扱い
ます。つまりどの「状態」も必ず3つの子ノード（次状態）を
持ちます。
Hint for the Vacuum Problem
前回課題での「都市」
今回課題での「状態」
Move Right
0
Move Left
1
2
0
1
Suck
Class Node {
Class State {
int id;
boolean dirtInLeftRoom;
boolean dirtInRightRoom;
boolean vacuum;
Hashtable nextStates;
State pointer;
String name;
Vector children;
Node pointer;
}
}
3
Hint for the Vacuum Problem
今回の課題の状態空間
Move Right
Move Right
Move Left
Move Left
0
1
Suck
Suck
Move Right
Move Left
Move Left
Move Right
Move Right
Move Right
4
Move Left
2
5
Suck
Move Left
3
Suck
Suck
Suck
Move Right
Move Left
Move Right
6
Suck
Move Left
7
Suck
Hint for the Vacuum Problem
• ここまで出来れば後は簡単ですね
• 出来上がった状態空間をDepthFirstまたは
BreathFirstで探索するだけです。
Hint for the Vacuum Problem
実装に関するヒント
– 前回のNodeクラスをStateクラスに変更します
class State {
・・・・
//State ID
int id;
//左の部屋に埃はあるか
boolean dirtInLeftRoom;
//右の部屋に埃はあるか
boolean dirtInRightRoom;
//Vacuumがどちらの部屋にいるか。
//true：左の部屋
//false：右の部屋
boolean vacuum;
//現状態から移行可能な三つの次状態
Hashtable nextStates;
//解表示のためのポインタ
State pointer;
Hint for the Vacuum Problem
実装に関するヒント
– コンストラクタにて「現状態」をセットします
/**
* コンストラクタ
* @param id この状態のID
* @param dirtInLeftRoom 左の部屋に埃があるかないか
* @param dirtInRightRoom 右の部屋に埃があるかないか
* @param vacuum Vacuumが右左どちらの部屋にあるか
*/
State(int id, boolean dirtInLeftRoom, boolean dirtInRightRoom, boolean vacuum) {
this.id = id;
this.dirtInLeftRoom = dirtInLeftRoom;
this.dirtInRightRoom = dirtInRightRoom;
this.vacuum = vacuum;
nextStates = new Hashtable();
}
Hint for the Vacuum Problem
実装に関するヒント
– 「次状態」はHashtableに登録します
class State {
final String MOVE_LEFT = "MOVE LEFT";
final String MOVE_RIGHT = "MOVE RIGHT";
final String SUCK = "SUCK";
・・・
/**
* 現状態から移行可能な全3次状態をセットするメソッド
* @param left Vacuumが左に移動した場合の次状態
* @param right Vacuumが右に移動した場合の次状態
* @param suck Vacuumが現在の部屋で吸取りを行った場合の次状態
*/
public void setNextState(State left, State right, State suck) {
//オペレータをキーとし、次状態インスタンスを値として
//Hashtableへ登録する
nextStates.put(MOVE_LEFT, left);
nextStates.put(MOVE_RIGHT, right);
nextStates.put(SUCK, suck);
}
・・・
Hint for the Vacuum Problem
実装に関するヒント
– 例えば、
「左の部屋に埃有り、右の部屋に埃有り、掃除機は左の部屋にいる」
という状態インスタンスを作り、更に移行可能な3つの次状態をセットするには
public class VacuumProblem {
State state[];
・・・
private void makeStateSpace() {
state = new State[8];
・・・
state[0] = new State(0, true, true, true);
・・・
state[0].setNextState(state[0], state[1], state[4]);
・・・
}
・・・
}
Hint for the Vacuum Problem
実装に関するヒント
– 注意する点として、「掃除機問題」には2つの目標状態（ゴール）があります。
– 「左の部屋に埃無し、右の部屋に埃無し、掃除機は左の部屋にいる」
– 「左の部屋に埃無し、右の部屋に埃無し、掃除機は右の部屋にいる」
public class VacuumProblem {
・・・
State goal, goal2;
・・・
private void makeStateSpace() {
・・・
state[6] = new State(6, false, false, true);
goal = state[6];
state[7] = new State(7, false, false, false);
goal2 = state[7];
・・・
}
・・・
}
Hint for the Vacuum Problem
実装に関するヒント
– また、前回の経路探索問題と違い、次状態に移行する際に使用されたオペレータ（アク
ション）を出力時に表示させる必要があります。例えば以下のように
public class VacuumProblem {
・・・
public void printSolution(State theState) {
if (theState == start) {
System.out.println(theState.toString());
「theState」になる為に使われ
たオペレータを返すメソッド
} else {
System.out.println(theState.toString());
System.out.println("↑");
System.out.println("[" + theState.getPreviousOperator() + "]");
System.out.println("↑");
printSolution(theState.getPointer());
}
}
・・・
}
Hint for the Vacuum Problem
実装に関するヒント
– 前述した「getPreviousOperator」のようなメソッドを作るには、Stateクラスの中に
PreviousOperatorを保存する為の変数が必要です。例えば以下のように
class State {
・・・
//解表示のためのポインタ
private State pointer;
//この状態に移行する為に行われたアクション
//解表示の為に必要
private String previousOperator;
・・・
}
previousOperatorに値をセットするタイミン
グはpointerをセットする時と同じ！
Hint for the Vacuum Problem
出力結果の一例（あくまでも一例ですよ）
Breadth First Search
STEP:0
OPEN:[State0]
closed:[]
STEP:1
OPEN:[State1, State4]
closed:[State0]
STEP:2
OPEN:[State4, State3]
closed:[State0, State1]
STEP:3
OPEN:[State3, State5]
closed:[State0, State1, State4]
STEP:4
OPEN:[State5, State2]
closed:[State0, State1, State4, State3]
STEP:5
OPEN:[State7, State2]
closed:[State0, State1, State4, State3, State5]
Hint for the Vacuum Problem
出力結果の続き
*** Solution ***
(State7) : The left
↑
[SUCK]
↑
(State5) : The left
↑
[MOVE RIGHT]
↑
(State4) : The left
↑
[SUCK]
↑
(State0) : The left
room has no dirt, the right room has no dirt and the vacuum is in the right room.
room has no dirt, the right room has dirt and the vacuum is in the right room.
room has no dirt, the right room has dirt and the vacuum is in the left room.
room has dirt, the right room has dirt and the vacuum is in the left room.
Hint for the Vacuum Problem
• ソースコードはもちろん、最後のソリューショ
ン出力フォーマットについても特に指定は無
いので、前ページのコード及び出力結果に縛
られること無く自由に実装して下さい。
今課題について
来週の授業にも続けてください。

Download Report