Search
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.
BFS.java
bfs
bfs directx
noVisio
runBFS_novisio.bat
node.isTarget()
true
expand()
kui.Node
hashCode()
equals()
node
findWay()
Application.main
runBFS.bat
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.
r
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.
AStar.java
InformedSearchingAlgorithm
astar
<default config>
Do not create any other files, put all the necessary code into the AStar.java source file.
kui