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.

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.

1. Download the software tool for students from the CourseWare website. Use NetBeans IDE to open the unzipped project folder.
2. Open the BFS.java source in NetBeans IDE. Your implementation goes in there.
3. You can run your program using a premade run configuration bfs for NB. bfs directx is provided in case you cannot use OpenGL.
4. In case you have troubles using the project on your home PC, follow the instructions 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.

• 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:

try {
    Thread.sleep(10); // 10 ms
}
catch (InterruptedException ex) {
    ex.printStackTrace();
}

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.

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.

1. 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.
2. Change the run configuration to astar (hit the arrow next to the combo box with <default config> and choose astar).

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

• 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?

1. The deadline for all three tasks (BFS, DFS, A*) is the next seminar.
2. Only BFS and A* are submitted into CW. DFS is evaluated by your teacher, in person.
3. 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.
4. Your classes must not contain any slowdown code.
5. Upload the zip archive into the Upload system CourseWare. The name of the archive is irrelevant.
6. An automatic test is executed. It takes 30s at most, and then you can examine the results.
7. You can upload the zip archive into the upload system as many times as you may require.