Problem Set 1
AI课后作业代写 The “Best Vertex Cover” problem is defined as follows: Input: An undirected graph G, in which each vertex is marked by a positive cost; and a
The “Best Vertex Cover” problem is defined as follows:
Input: An undirected graph G, in which each vertex is marked by a positive cost; and a total budget T.
Goal: A set of vertices S such that (a) every edge in G has at least one end in S and (b) the total cost of the vertices in S is at most B.
For instance, in Graph 1 below, with T = 20, a solution is { A,C,D }. In Graph 2, with T = 20, a solution is { H,J }
Problem 1 AI课后作业代写
Consider the following state space for systematically solving the problem:
State: A set of vertices whose total cost is at most T.
Successor to state S: Add some vertex V to S such that (a) V is alphabetically later than the vertices in S (to guarantee systematic search); (b) V covers some edge that is uncovered in S (otherwise it’s pointless); (c) the total cost is no greater than T.
Start state: The empty set.
Goal state: A state that covers all the edges.
Show the part of the state space that would be generated if you use depth-first search in this state space to find the solution to graph 2 with T = 23. You should show this as a tree. I strongly recommend that you use the left-to-right typewriter format illustrated in the Powerpoint slides, thus:
Problem 2
Show the states generated in doing a breadth-first search of the state space in problem 1.
Problem 3
A. Describe an instance of Best Vertex Cover where doing abreadth-first search will construct 1000 (or more) times as many states as doing a depth-first search.
B. Describe an instance of Best Vertex Cover where doing a depth-first search will construct 1000 (or more) times as many states as doing a breadth-first search. (Hint: There is an instance where the correct solution contains only one vertex.)
Problem 4 AI课后作业代写
Consider the Best Vertex Cover on a graph in general with n vertices (not on the specific examples above).
What is the maximal depth D of the state space? What is the branching factor B?
Give a bound on the number of states in the state space (you should be able to get a bound much smaller than BD.)
Problem 5 AI课后作业代写
Consider trying to solve Best Vertex Cover using hill climbing in the following state space.
State: Any set of vertices.
Neighbors of state S: Either add one vertex to S or delete one vertex from S.
Error function:
Max(0,(Total cost of the vertices in S)-T) +
the sum of the costs of all the uncovered edges E,
where the cost of an edge is considered to be the cost of its cheaper end.
For example, in graph 1, suppose S= { D,E } and T = 20. Cost(D)=10. Cost(E)=13. The uncovered edges are A-B and A-C, both of cost 3. So Error(S) = Max(0,10+13- 20)+3+3 = 9.
What is the sequence of states encountered doing simple hill-climbing in this space, starting from state { D,E }?
更多代写：Haskell代写 考试助攻 英国金融工程代写 金融Essay代写范文 教育学英文论文代写 speech代写代做
