实现程序Flow, 在规定时间内得到Puzzle的解，算法使用改进过的Dijkstra.
Deliverables
You are given a base code. You can compile the code and execute the solver by typing ./flow <puzzleName>. You are going to have to program your solver in the file search.c. Look at the file and implement the missing part in the function called game_dijkstra_search. Once you implement the search algorithm, go to the file called extensions.c and implement the function called game_check_deadends
You are given the structure of a node in node.*files, and also a priority queue queues.* implementation. Look into the engine.* and utils.* files to know about the functions you can call to perform the search.
In your final submission, you are free to change any file, but make sure the command line options remain the same.
Input
In order to execute your solver use the following command:
./flow [options] <puzzleName1> ... <puzzleNameN>
for example:
./flow puzzles/regular_5x5_01.txt
Will run the solver for the regular 5 by 5 puzzle, and report if the search was successful, the number of nodes generated and the time taken. if you use flag -q (quiet) it will report the solutions more concisely. This option can be useful if you want to run several puzzles at once and study their performance.
If you append the option -A it will animate the solution found. If you append the option -d it will use the dead-end detection mechanism that you implemented. Feel free to explore the impact of the other options, specifically the ordering in which the colors are explored.
By default, the color that has fewer free neighbors (most constrained), is the one that is going to be considered first.
All the options can be found if you use option -h:
$./flow -h
usage: flow_solver [ OPTIONS ] BOARD1.txt
BOARD2.txt [ ... ] ]
Display options:
-q, --quiet Reduce output
-d, --diagnostics Print diagnostics when search unsuccessful
-A, --animation Animate solution
-F, --fast Speed up animation 4x
-C, --color Force use of ANSI color
-S, --svg Output final state to SVG
Node evaluation options:
-d, --deadends dead-end checking
Color ordering options:
-r, --randomize Shuffle order of colors before solving
-c, --constrained Disable order by most constrained
Search options:
-n, --max-nodes N Restrict storage to N nodes
-m, --max-storage N Restrict storage to N MB (default 1024)
Help:
-h, --help See this help text
Output
Your solver will print the following information if option -q is used:
- Puzzle Name
- SearchFlag (see utils.c, line 65-68 to understand the flags)
- Total Search Time, in seconds
- Number of generated nodes
- A final Summary
For example, the output of your solver ./flow -q ../puzzles/regular_* could be:
../puzzles/regular_5x5_01.txt s 0.000 18
../puzzles/regular_6x6_01.txt s 0.000 283
../puzzles/regular_7x7_01.txt s 0.002 3,317
../puzzles/regular_8x8_01.txt s 0.284 409,726
../puzzles/regular_9x9_01.txt s 0.417 587,332
5 total s 0.704 1,000,676
These numbers depend on your implementation of the search, the ordering you use, and whether you prune dead-ends. If we use dead-end pruning ./flow -q -d ../puzzles/regular_* we get the following results
../puzzles/regular_5x5_01.txt s 0.000 17
../puzzles/regular_6x6_01.txt s 0.000 254
../puzzles/regular_7x7_01.txt s 0.001 2,198
../puzzles/regular_8x8_01.txt s 0.137 182,136
../puzzles/regular_9x9_01.txt s 0.210 279,287
5 total s 0.349 463,892
Remember that in order to get full marks, your solver has to solve at least the regular puzzles.
Deliverables
Deliverable 1 - Dijkstra Solver source code
You are expected to hand in the source code for your solver, written in C. Obviously, your source code is expected to compile and execute flawlessly using the following makefile command:
make
generating an executable called
flow
Remember to compile using the optimization flag gcc -O3 for doing your experiments, it will run twice as quickly as compiling with the debugging flag gcc -g (see Makefile). The provided Makefile compiles with the optimization flag by default, and with the debugging flag if you type make debug=1. For the submission, please do not remove the -g option from your Makefile, as our scripts need this flag for testing. Your program must not be compiled under any flags that prevent it from working under gdb or valgrind.
Your implementation should be able to solve the regular puzzles provided. To solve the extreme puzzles, you’ll need further enhancements that go beyond the time for this assignment, but feel free to challenge yourself if you finish early and explore how you would solve the extreme puzzles.
Deliverable 2 - Experimentation
Besides handing in the solver source code, you’re required to provide a table reporting at least the execution time and number of generated nodes with and without dead-end detection. Include in the table only the puzzles that your solver finds a solution to.
Plot figures, where the x-axis can be the number of free cells at the start, or the size of the grid, and the y-axis is either the number of generated states or solution time.
Explain your results using your figures and tables. Which complexity growth does your data show? What’s the computational benefit of the dead-end detection, does it decrease the growth rate? Answer concisely.
If you decide to implement any further optimization beyond the instructions of the assignment, or change the default arguments such as allowed memory or color ordering, please discuss their impact on the experimentation section as well.
Please include your Username, Student ID and Full Name in your Document.
My recommendation is that you generate the plots using any standard Python visualization library. See for example Seaborn or Matplotlib. Otherwise, there’s always the old-school excel/open-office/google-sheets method.