Deliverables
You are given a base code. You can compile the code and execute the solver by typing ./flow
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.
Copyright By PowCoder代写 加微信 powcoder
In order to execute your solver use the following command:
./flow [options]
./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
-d, –diagnostics
-A, –animation
-F, –fast
-C, –color
Node evaluation options:
-d, –deadends
Color ordering options:
-r, –randomize
-c, –constrained
Search options:
-n, –max-nodes N
-m, –max-storage N
-h, –help
Reduce output
Print diagnostics when search unsuccessful
Animate solution
Speed up animation 4x
Force use of ANSI color
Output final state to SVG
dead-end checking
Shuffle order of colors before solving
Disable order by most constrained
Restrict storage to N nodes
Restrict storage to N MB (default 1024)
See this help text
Your solver will print the following information if option -q is used:
1. Puzzle Name
2. SearchFlag (see utils.c, line 65-68 to understand the flags)
3. Total Search Time, in seconds
4. Number of generated nodes
5. 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:
generating an executable called
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.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com