AI 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
Copyright By PowCoder代写 加微信 powcoder
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
Object A B C DE
Value 138 117 5
Weight 11 4 7 4 2
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
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)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com