Ex8. Search for Vacuum Problem(2)

Slides:



Advertisements
Similar presentations
オブジェクト指向 言語 論 第八回 知能情報学部 新田直也. 多相性(最も単純な例) class A { void m() { System.out.println( “ this is class A ” ); } } class A1 extends A { void m() { System.out.println(
Advertisements

社会人学習講座 「Javaプログラミング概論」
マルチスレッド処理 (II) Multithreading
GridLayout オブジェクト(省略)
情報理工学部 情報システム工学科 ラシキアゼミ 3年 H 井奈波 和也
JPAを利用した RESTful Webサービスの開発
プログラミング基礎I(再) 山元進.
アルゴリズムとデータ構造 2013年6月18日
アルゴリズムとデータ構造1 2005年7月8日
~手続き指向からオブジェクト指向へ(Ⅰ)~
Ex7. Search for Vacuum Problem
アルゴリズムとデータ構造 2010年7月5日
プログラミング基礎I(再) 山元進.
とても使いやすい Boost の serialization
アルゴリズムとプログラミング (Algorithms and Programming)
とても使いやすい Boost の serialization
Javaでゲーム  山本拓弥.
プログラミング基礎I(再) 山元進.
第2回:Javaの変数と型の宣言 プログラミングII 2007年10月2日.
アルゴリズムとデータ構造 2012年6月14日
独習Java ・ 10.6  Hashtableクラス ・ 10.7  String Tokenizerクラス  12月12日    小笠原 一恵.
プログラミング実習 1・2 クラス 第 1 週目 担当教員:  渡邊 直樹.
第2章 Eclipseと簡単なオブジェクト 指向プログラミング
Bridge Pattern
大岩 元 慶応大学環境情報学部 二分木 データ構造とプログラミング(10) 大岩 元 慶応大学環境情報学部
アルゴリズムとデータ構造 2011年6月14日
ピカチュウによる オブジェクト指向入門 (新版)
アルゴリズムとデータ構造 2011年6月20日
第13回 ハッシュテーブルを使ったプログラム ~高速に検索するには?~.
二分探索木によるサーチ.
Unity, C# 移動するモデルの位置を 指定した位置へ自動修正
~手続き指向からオブジェクト指向へ[Ⅱ]~
細かい粒度でコードの再利用を可能とするメソッド内メソッドのJava言語への導入
プログラミング言語入門 手続き型言語としてのJava
アルゴリズムとデータ構造 2012年6月28日
アルゴリズムとデータ構造 2011年6月27日
第9章 例外処理,パッケージ 9.1 例外処理 9.2 ガーベッジコレクション.
独習JAVA 6.8 コンストラクタの修飾子 6.9 メソッドの修飾子 6.10 ObjectクラスとClassクラス 11月28日(金)
MVP for VB が語る C# 入門 初音 玲.
MVP for VB が語る C# 入門 初音 玲.
Windows PowerShell Cmdlet
アルゴリズムとデータ構造 2013年7月16日
アルゴリズムとデータ構造1 2006年7月4日
アルゴリズムとデータ構造1 2005年7月15日
第11週:super/subクラス、継承性、メソッド再定義
アルゴリズムとプログラミング (Algorithms and Programming)
Collection, Generics, Iterator
Javaプログラムの変更を支援する 影響波及解析システム
Where is Wumpus Propositional logic (cont…) Reasoning where is wumpus
二分探索木における要素削除 データ構造とプログラミング(10)
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとデータ構造1 2005年7月5日
アルゴリズムとデータ構造1 2005年6月24日
アルゴリズムとデータ構造 2010年6月21日
アルゴリズムとデータ構造 2010年7月26日
Ex7. Search for Vacuum Problem
プログラミング 4 木構造とヒープ.
アルゴリズムとデータ構造1 2006年7月11日
アルゴリズムとプログラミング (Algorithms and Programming)
AVL木.
C#プログラミング実習 第3回.
アルゴリズムとデータ構造 2011年7月11日
アルゴリズムとデータ構造1 2008年7月24日
サブゼミ第7回 実装編① オブジェクト型とキャスト.
アルゴリズムとデータ構造1 2006年6月23日
アルゴリズムとデータ構造 2013年7月1日
アルゴリズムとデータ構造1 2009年7月2日
JAVA入門⑥ クラスとインスタンス.
アルゴリズムとデータ構造 2012年6月21日
計算機プログラミングI 第2回 2002年10月17日(木) 履習登録 複習 ライブラリの利用 (2.6-7) 式・値・代入 (2.6-8)
Presentation transcript:

Ex8. Search for Vacuum Problem(2) Application of Searching Algorithms

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 2 4 6 dirt 1 3 5 7 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 前回課題の状態空間を思い出してください。 2 1 3 5 7 6 8 9 4

Hint for the Vacuum Problem 前回課題と今回課題の比較 前回課題の「都市」に相当するのが今回の「状態(state)」です。 前回課題では「都市」が全部で10個でしたが、今回の課題は「状態(state)」が全部で8個です。 前回課題ではある「都市」に隣接した「都市」は子ノード(Children)として扱われましたが、今回の課題ではある「状態」から移行可能な次の「状態」を子ノードとして扱います。つまりどの「状態」も必ず3つの子ノード(次状態)を持ちます。

Hint for the Vacuum Problem 前回課題での「都市」 今回課題での「状態」 Move Right Move Left 1 2 Suck 3 Class Node { String name; Vector children; Node pointer; } Class State { int id; boolean dirtInLeftRoom; boolean dirtInRightRoom; boolean vacuum; Vector nextStates; State pointer; }

Hint for the Vacuum Problem 今回の課題の状態空間

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; //現状態から移行可能な三つの次状態 Vector 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 Vector(); }

Hint for the Vacuum Problem 実装に関するヒント 「次状態」はVectorに登録します 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) { //オペレータをキーとし、次状態インスタンスを値として //Vectorに、左へ移動、右へ移動、吸取りの順番で次の状態を登録する。 nextStates.add(left); nextStates.add(right); nextStates.add(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()); } else { System.out.println("↑"); System.out.println("[" + theState.getPreviousOperator() + "]"); printSolution(theState.getPointer()); } 「theState」になる為に使われたオペレータを返すメソッド

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 room has no dirt, the right room has no dirt and the vacuum is in the right room. ↑ [SUCK] (State5) : The left room has no dirt, the right room has dirt and the vacuum is in the right room. [MOVE RIGHT] (State4) : The left room has no dirt, the right room has dirt and the vacuum is in the left room. (State0) : The left room has dirt, the right room has dirt and the vacuum is in the left room.

Hint for the Vacuum Problem ソースコードはもちろん、最後のソリューション出力フォーマットについても特に指定は無いので、前ページのコード及び出力結果に縛られること無く自由に実装して下さい。

課題 Search a solution from a start state to the goal state using breadth-first and depth-first search algorithms. (optional) make a Java program (either Java Applet or Java Application) to search a solution from a start state to the goal state (clean up a mxn rooms) using breadth-first and depth-first search algorithms.