{{indexmenu_n>7}}

<timer 2000-01-01 00:00:01=2016-03-07 00:00:01>
The content of this page is going to be accessible from Apr 4.
</timer>

<timer 2016-03-07 00:00:01=->
====== Searching a State Space ======

//Author: Petr Benda// \\ //Translation: Radek Píbil// \\ //Edit: Tibor Strašrybka//

This tutorial assumes a basic knowledge of Java and NetBeans IDE.

===== Part A =====

==== Assignment ====

Implement BFS and DFS algorithms for state-space search. If you implement them using the //OPEN// and //CLOSED// sets (lists), the difference between them is minimal. \\ The output of the algorithm is meant to be the first path between start and target state found. Use the provided libraries for the GUI. In case of matlab or c/c++ either use comprehensive text output, or create a simple GUI yourself. 

==== Guidelines for implementation ====

  - Download the <wrap round download>{{:courses:a3b33kui:cviceni:07_prohledavani_nastroj.zip?nocache|software tool for students}}</wrap> from the CourseWare website. Use [[http://netbeans.org/downloads|NetBeans IDE]] to open the unzipped project folder.
  - Open the ''BFS.java'' source in NetBeans IDE. Your implementation goes in there.
  - You can run your program using a premade run configuration ''bfs'' for NB. ''bfs directx'' is provided in case you cannot use OpenGL.
  - In case you have troubles using the project on your home PC, follow the instructions [[courses:ae3b33kui:seminars_and_labs:07_java_settings|solving settings problems]] on the CW website, which is going to be periodically updated. The system **can be ran with console output** only using the ''noVisio'' argument (see ''runBFS_novisio.bat''), which may be useful for debugging.

==== Notes for implementation ====

  * Do not create any other files, all the code is supposed to go into ''BFS.java''.
  * See javadoc.
  * The ''node.isTarget()'' methods return ''true'' if a node is the target.
  * Newly expanded edges are drawn automatically after calling ''expand()'' method.
  * You should know that the nodes accessed through the ''kui.Node'' interface have ''hashCode()'' and ''equals()'' correctly implemented. **It is not possible to create a ''node'' __class__ not implementing ''kui.Node'' __interface__.**
  * In order to draw the path (the ordered list of nodes), it is necessary to return it from the ''findWay()'' method.
  * Your algorithm can be run without NetBeans IDE using the ''Application.main'' class as the main class and the name of your class (fully qualified) as a parameter. This method is also being used by the provided batch files (''runBFS.bat'').
  * In order to slow down the execution in order to see the progress of execution you can use the following code:
<code java>
try {
    Thread.sleep(10); // 10 ms
}
catch (InterruptedException ex) {
    ex.printStackTrace();
}
</code>

==== Using the visualization tool ====

Setting the start and target node can be done using the left mouse button. Zooming in and out can be done with the mouse wheel. A region can be enlarged using ctrl+left mouse button and drag selecting the desired region. The right mouse button can be used to scroll around the map. The color of an expanded edge corresponds with the time at which the expansion took place. The oldest edges are green, followed by blue, purple, red and yellow for the newest. \\ **Entering a new search path is possible after pressing ''r'' key.**

===== Part B =====

==== Assignment ====

Implement the A* algorithm. The result is going to be the shortest path between the starting a target node specified by the user. Design and use a heuristic function. Use the provided GUI libraries (if applicable). The state-space is specified by a planar graph.

==== Guidelines for implementation ====

  - Open the ''AStar.java'' source file in the project. This class implements the ''InformedSearchingAlgorithm'' interface. In contrast with the previous task, ''findWay()'' receives both the starting and target node.
  - Change the run configuration to ''astar'' (hit the arrow next to the combo box with ''<default config>'' and choose ''astar'').

==== Notes for implementation ====

Do not create any other files, put all the necessary code into the ''AStar.java'' source file.

==== Questions ====

  * Which of the algorithms usually (in our case) returns the shortest path?
  * How many states the BFS and DFS algorithms are going to expand in the worst case?
  * In what sense is the path found by BFS the shortest one?
  * What conditions must the heuristic function satisfy in order to be sure that the A* algorithm actually returns the shortest path with certainty?
  * What is a monotonic heuristic function?
  * What heuristic function have you chosen?
  * Is it necessary to implement the algorithm in its full generality, or is it possible to perform some simplifications?

===== How to submit? =====
  - The deadline for all three tasks (BFS, DFS, A*) is the next seminar.
  - Only BFS and A* are submitted into CW. DFS is evaluated by your teacher, in person.
  - Create a zip archive, which contains the ''BFS.java'' and ''AStar.java'' source __files in__ ''kui'' __directory__. One file is ok as well, for a partial automatic test, but it is necessary for you to submit both files in the end. Including other files or differently named files is not admissible.
  - Your classes must not contain any slowdown code.
  - Upload the zip archive into the [[https://cw.felk.cvut.cz/upload/secure/index.phtml|Upload system CourseWare]]. The name of the archive is irrelevant.
  - An automatic test is executed. It takes 30s at most, and then you can examine the results.
  - You can upload the zip archive into the upload system as many times as you may require.

===== Assignment scoring =====
^ algorithm ^ code presentation  ^ auto-evaluation on the server  ^ bonus  ^
^ BFS/DFS  | 2 pts  | 2 pts  | 1 pt  |
^ A*  | 4 pts  | 2 pts  | 1 pt  |
^ Total:  |  **12 pts**  |||
</timer>