Programming Assignment 1
Programming作业代写 Write two programs that solves the Best Vertex Cover problem, as described in Problem Set 1.The fifirst will use iterative deepening;
Assignment
Write two programs that solves the Best Vertex Cover problem, as described in Problem Set 1. The fifirst will use iterative deepening; the second will use simple hill climbing with random restart.
Input
Input should be a text fifile (or read from standard input) with the following contents.
- Line 1: The budget (a positive integer) and flflags: “V” for verbose output or “C” for compact output.For the hill-climbing program, the number of random restarts to run.
- Each vertex. Name (you may assume that this is a single alphabetic character) and cost (a positive integer), 1 per line.
- Blank line
- Each edge: the names of the two ends. 1 per line.
Examples are given below.
Search Programming作业代写
The programs should search through the state space until either:
a) A solution is found.
b) In iterative deepening, search to depth K fifinds no states at depth K. (That is, none of the states at depth K-1 have any successors). Thus, if there is no goal state to be found, the search to depth K will be identical to the search to depth K-1; then the program will terminate.
c) In hill climbing, each hill climb is carried out from a random starting state until it reaches a solution or a local maximum. A random starting point is constructed by going through the list of vertices and accepting or rejecting each with probability 1/2.
Output Programming作业代写
The program should print out to a text fifile or standard output:
- If a solution is found, the solution (just a sequence of vertices).
If no solution is found, then “No solution found”
- If the “verbose” flflag is set then a trace of the search sequence, as illustrated below.
Coding
Programs will be accepted in C, C++, Java, or Python.
Submit Programming作业代写
The source code for the two programs and a README fifile how to compile and run your code.
Grading
Grading: 8 points for correctly running code. 2 points for well-written code. A programming assignment
count equally with a problem set in computing the overall grade.
Late policy Programming作业代写
Programming assignments due at the beginning of class on the due date. I will accept assignments late with a penalty of 1 point out of 10 for each week late (fractions of a week are rounded up) up to 2 weeks late.
There are some additional sample inputs and outputs linked to the assignment on the web.
Sample Inputs and Outputs
Additional sample I/O pairs will be posted later.
Input for iterative deepening program, for graph 1. Budget=25
25 V
A 3
B 5
C 6
D 10
E 13
A B
A C
B D
C E
D E
Output Programming作业代写
Depth = 1
A Cost=3.
B Cost=5.
C Cost=6.
D Cost=10.
E Cost=13.
Depth=2
A Cost=3.
A B Cost=8.
A C Cost=9.
A D Cost=13.
A E Cost=16.
B Cost=5.
B C Cost=11.
B D Cost=15.
B E Cost=18.
C Cost=6.
C D Cost=16.
C E Cost=19.
D Cost=10.
D E Cost=23.
E Cost=13.
Depth=3
A Cost=3.
A B Cost=8.
A B C Cost=15.
A B D Cost=18.
A B E Cost=21.
Found solution A B E Cost=21.
The input for hill climbing on the same graph with the same budget is the same, except that you have to indicate the number of random restarts on the top line. E.g.
25 V 2
for a budget of 15, with two random restarts, verbose output.
In verbose output for hill climbing, you should indicate the value of the Error function as well as the cost for a state, and show all the neighbors that are being tested. (The order in which you enumerate neighbors doesn’t matter.)
Sample output Programming作业代写
Randomly chosen start state: E
E Cost=13. Error=11
Neighbors:
A E Cost=16. Error=6
B E Cost=18. Error=6
C E Cost=19. Error=12
D E Cost=23. Error=14
{} Cost=0. Error=27
Move to A E. Cost=16. Error=6
Neighbors
E Cost=13. Error=11
A B E Cost=21. Error=6
A C E Cost=22. Error=12
A D E Cost=26. Error=11
A Cost=13. Error=11
Search failed
Randomly chosen start state A B C
A B C Cost=14. Error=10
Neighbors
B C Cost=11. Error=10
A C Cost=9. Error=15
A B Cost=8. Error=16
A B C D Cost=24. Error=9
A B C E Cost=27. Error=12
Move to A B C D Cost=24. Error=9
Neighbors
B C D Cost=21. Error=6
A C D Cost=19. Error=4
A B C Cost=14. Error=10
A B D Cost=18. Error=9
A B E Cost=21. Error=6
Move to A C D Cost=19. Error=4
Neighbors
C D Cost=16. Error=4
A B C D Cost=24. Error=9
A D Cost=13. Error=6
A C Cost=9. Error=15
A C D E Cost=32. Error=17
Search failed
No solution found.
其他代写：assignment代写 analysis代写 code代写 assembly代写 essay代写 homework代写 Exercise代写 加拿大代写 英国代写 作业代写 CS代写 Data Analysis代写 data代写 澳大利亚代写 app代写 algorithm代写 作业加急 北美代写 北美作业代写
