CS代考程序代写 prolog algorithm chain PROLOG Programming Assignment, CS540, Spring 2021, DUE March 2, 2021
PROLOG Programming Assignment, CS540, Spring 2021, DUE March 2, 2021
The assignment is to implement a Dynamic Programming algorithm to solve a (non-wrapping) Adjacent NK Landscape. Note that these could also be MAX-3SAT instances, but with bounded tree width. The trick is to note that the first variable only appears in the first subfunction. Then follow the chain of dependencies.
Implement this in Prolog. You can think of Dynamic Programming as traversing a graph or a list, creating a partial solution and a ¡°memo¡± function as it proceeds. The DP might resolve the prefix solution at any point. Or, DP
might work all the way to the end of the chain, and then pass the solution back to the beginning. complexity does not change, you can just wait until the end to pass back the solution.
Here is a simple non-wrapping Adjacent NK Landscape structure.
Of course, this is a k-bounded pseudo-Boolean function. So you add the sum of the subfunctions.
Here is a Prolog declaration of an adjacent NK Landscape optimization problem. eval_NK(Length, K, List-of-bits, OPT, List-of-tables)
Because the
Length is the total number of bits (Input), K is the number of bits per subfunction (Input), List-of-bits is the bit string stored as a list (Output), OPT: evaluation of the global optimum (Output), List-of-tables stores a table for each subfunction (Input).
For this Lab: K=2 or K=3. The number of subfunctions is always Length-K+1.
The subfunctions can be expressed as a list of evaluation ¡°tables¡±.
eval_NK(8, 2, [B1, B2, B3, B4, B5, B6, B7, B8], OPT,
[[1, 2, 3, 4], [4, 1, 2, 3], [2, 4, 3, 1], [3, 1, 4, 2], [4, 3, 1, 2], [1, 4, 2, 3], [3, 1, 2, 4]]).
Thus, F1(B1, B2) := [1,2,3,4] yields F1(00) = 1, F1(01) = 2, F1(10) = 3, F1(11) = 4 F2(B2, B3) := [4,1,2,3] yields F2(00) = 4, F2(01) = 1, F2(10) = 2, F2(11) = 3 F3(B3, B4) := [2,4,3,1] yields F3(00) = 2, F3(01) = 4, F3(10) = 3, F3(11) = 1
Hint: gettable([[1,2,3,4], [4,1,2,3], [2,4,3,1], [3,1,4,2], [4,3,1,2]]). getnext(X, Table) :- gettable(Table), member(X, Table).
Maximize f1(B1,B2) + f2(B2,B3) + f3(B3,B4)+ f4(B4,B5) + f5(B5,B6) + f6(B6,B7) + f7(B7,B8).
Note: You can break ties randomly (or cleverly, but it doesn¡¯t matter much). ALSO: PSUM(i) is determined by Max(B(i-1)).
Maximize f1(b1,b2,b3) + f2(b2,b3,b4) + f3(b3,b4,b5) + f4(b4,b5,b6) + f5(b5,b6,b7) +f6(b6,b7,b8)
HINT on the recursion below. AND you probably need another list or nested list to store state.
eval_NK(8, 2, [B1, B2, B3, B4, B5, B6, B7, B8], OPT,
[[1, 2, 3, 4], [4, 1, 2, 3], [2, 4, 3, 1], [3, 1, 4, 2], [4, 3, 1, 2], [1, 4, 2, 3], [3, 1, 2, 4]]) :-
B1 has a partial and waits.
eval_NK(7, 2, [B2, B3, B4, B5, B6, B7, B8], OPT,
[[4, 1, 2, 3], [2, 4, 3, 1], [3, 1, 4, 2], [4, 3, 1, 2], [1, 4, 2, 3], [3, 1, 2, 4]]) :-
B2 has a partial and waits.
eval_NK(6, 2, [B3, B4, B5, B6, B7, B8], OPT,
[[2, 4, 3, 1], [3, 1, 4, 2], [4, 3, 1, 2], [1, 4, 2, 3], [3, 1, 2, 4]]) :-
Termination/Base case:
eval_NK(2, 2, [B7, B8], OPT, [[3, 1, 2, 4]]). OR: eval_NK(1, 2, [B8], OPT, [[3,1,2,4]].
