Spring ‘22 AI Homework 2: solutions
● Assigned: Jan 31
Due: Feb 7, before class
Submit: typeset doc or pdf via Brightspace
Copyright By PowCoder代写 加微信 powcoder
Local Search
The following is known as the KNAPSACK problem. You have a knapsack and a collection of valuable objects. Each object O has a weight O.W and a value O.V. There is a maximum M on the total weight that you can carry. You have a target value T. The question is, can you choose objects to pack so that their total value is at least T and their total weight is at most M?
For instance, suppose that T = 23, M = 13 and you have the following objects
● Suppose that we want to use a hill climbing algorithm to solve this with the following state space and heuristic function:
● A state is any set of objects.
● An operator is either to add an object to the set; to delete an object in the set; or to swap
an object in the set with an object outside the set.
● For any set S, let Weight(S) and Value(S) be the total weight and total value of the set.
Define the error function Error(S) = max(Weight(S)-M,0) + max(T-Value(S),0). Then the problem is to find a set S for which Error(S)=0.
For example, if S = {A,B} then Error(S) = max(15-13,0) + max(23-21,0) = 2+2 = 4. If S= {A} then Error(S) = max(11-13,0) + max(23-13,0) = 0+10 = 10.
Tiebreaker: In case of a tie in Error, use the higher Value, if that is equal, use the lower Weight
1. [4 pts.] Trace the execution of hill climbing from a start state of {A,D}. Use basic hill climbing, so no sideways motion or restarts.
2. [3 pts.] Also using basic hill climbing, trace the execution of hill climbing from a start state of {A,B}, and explain what was different from part 1.
3. [3 pts.] Consider now the general case where there are N objects under consideration (not the example above). What is the size of the state space? What is maximal number of neighbors of any state?
1. search for T>=23, M<=13, start from {A D} Enumerate 3 add, 2 delete, 6 swap
State W {AD}15
{ABD}19 {ACD}22 {ADE}17 {A} 11 {D} 4 {BD}8 {DE}6 {CD}11 {AB}15 {AC}18 {AE}13
V Error 20 5
25 6 31 9 28 4 13 10 7 16 15 8 12 11 18 5 21 4 24 5 18 5
Choose {A D E} over {A B} due to value tiebreaker
Enumerate 3 add, 2 delete, 6 swap No history, so {A D} should show up State W V Error
{A D E} 17 25 4
{A B D E} 21 33 8 {A C D E} 24 36 11 {AD}15 20 5 {AE}13 18 5 {DE}6 12 11 {BDE}10 20 3 {ABE}17 26 4
{ABD}19 28 6 {CDE}13 23 0 {ACE}20 29 7 {ACD}22 31 9
Choose {C D E}, and Goal achieved.
2. search for T>=23, M<=13, start from {A B}
Enumerate 3 add, 2 delete, 6 swap
State W {AB}15
{A B C} 22 {A B D} 19 {A B E} 17 {A} 11 {B} 4 {BC}11 {AC}18 {AD}15 {BD}8 {BE}6 {AE}13
V Error 21 4
32 9 28 6 26 4 13 10 8 15 19 4 24 5 20 5 15 8 13 10 18 5
No reduction in error available, no sideways motion allowed – failure.
If sideways motion was allowed, we might have gotten to ABE to ADE, and from there we know success will happen from part 1.
3. For each item, you have a binary decision whether it is in or out of the set, so State-space = 2^N
In each state with say K elements in the knapsack, you have: K deletions + N-K additions + K*(N-K) swaps
If you simplify and change K->x you get a quadratic
-x^2+ Nx +N
Since this is a negative quadratic, it has a max, which we can solve for by taking the derivative and solving for 0
-2x+N=0 ; x = N/2
So the most neighbors will occur at K=N/2 and is (N^2)*/4 + N
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com