DP in Prolog

% My friend asked me to post this code. Take a look!

%

% Write a predicate buy(Stores,Links,MinCustomers) that determines the
% minimum number of customers required to buy all the items on sale in
% an outlet with a given list of Stores and Links connecting them. The
% customers will buy all sales in the Stores one by one, and travel 
% between stores along the available Links. A Store is a term 
% store(Name,Capacity,Bankrupt,Waiting), where: Name is a unique name, 
% Capacity is the number of customers required to buy all the sales in
% the store, Bankrupt is the number of customers bankrupt after buying 
% all sales in the store, and Waiting are the number of customers that
% remain in the store to wait for more sales. Any remaining customers 
% after a store sale that are not Waiting or Bankrupt, can move on to 
% shop in the next store. A link connects two stores, and is represented 
% by a term link(Namel,Name2) (you can assume that the Stores and Links 
% form a connected graph). In your plan, you are free to start at any 
% store, but you should travel at most once in either direction along a 
% link.
% 
% Example:
% buy([store(a,5,5,5),store(b,5,1,1),store(c,10,5,5)],
%     [link(a,b),link(b,c)],
%     MinCustomers).
%
% expecting MinCustomers=17
%
% Implementation: XSB
% Solution:
% Find min-cost hamilton path by dynamic programming (state compressing)
% Total number of states: 2^n * n, n denotes the number of vertice in the
% graph Val[s][j] denotes the min-cost of state s which ends at vertice j.
% The ith bit of s is set if the path has visited vertice i.

:- [basics].
:- [listutil].

buy(Stores, Links, MinCustomers):- 
  length(Stores, N),
  get_directed_links(Links, Lk),
  append(Links, Lk, Mp),
  End is (1 << N),
  dp(1, End, [[0]], Stores, Mp, MinCustomers).

get_directed_links([], []).
get_directed_links([H | T], [L | R]):-
  link(U, V) = H, L = link(V, U), get_directed_links(T, R).

get_min_element(End, End, Col, Stores, Best, Best).
get_min_element(Itr, End, Col, Stores, Cur, Best):-
  Itr1 is Itr + 1,
  ith(Itr1, Stores, Store),
  store(S, C, B, W) = Store,
  ith(Itr1, Col, V),
  P is V,
  (
    (
      P < Cur,
      get_min_element(Itr1, End, Col, Stores, P, Best)
    );
    (
      get_min_element(Itr1, End, Col, Stores, Cur, Best)
    )
  ).

% dynamic programming
dp(End, End, Val, Stores, Map, MinCustomers):-
  ith(End, Val, Col),
  length(Stores, L),
  get_min_element(0, L, Col, Stores, 10000000000, MinCustomers).

dp(Itr, End, Val, Stores, Map, MinCustomers):-
  length(Stores, L),
  search(Itr, 0, L, Val, [], New, Stores, Map),
  append(Val, [New], NewVal),
  Itr1 is Itr + 1,
  dp(Itr1, End, NewVal, Stores, Map, MinCustomers).

search(Level, End, End, Val, New, New, Stores, Map).
search(Level, Itr, End, Val, Cur, New, Stores, Map):-
  Itr1 is Itr + 1,
  X is Level /\ (1 << Itr),
  (
    (
      X is 0,
      append(Cur, [1000000000], Cur1),
      search(Level, Itr1, End, Val, Cur1, New, Stores, Map)
    );
    (
      Level1 is Level - X,
      (
        (
          Level1 is 0,
   I is Itr + 1,
   ith(I, Stores, Store),
   store(S, C, B, R) = Store,
   append(Cur, [C], Cur1),
   search(Level, Itr1, End, Val, Cur1, New, Stores, Map)
 );
 (
   J is Level1 + 1,
   ith(J, Val, Col),
   search1(Itr, 0, End, Col, 1000000000, Best, Stores, Map),
   K is Itr + 1,
   ith(K, Stores, Store),
   store(S, C, B, R) = Store,
   append(Cur, [Best], Cur1),
   search(Level, Itr1, End, Val, Cur1, New, Stores, Map)
 )
      )
    )
  ).

search1(I, End, End, Col, Best, Best, Stores, Map).
search1(I, J, End, Col, Cur, Best, Stores, Map):-
  K is I + 1,
  L is J + 1,
  ith(K, Stores, Store),
  store(S, C, B, W) = Store,
  (
    /* I and J is connected */
    (
      is_connect(J, I, Stores, Map),
      X is J + 1,
      ith(X, Col, V),
      VV is V + B + W,
      (
 (
   VV >= C,
   (
     (
       VV >= Cur,
       search1(I, L, End, Col, Cur, Best, Stores, Map)
     );
     (
       search1(I, L, End, Col, VV, Best, Stores, Map)
     )
   )
 );
 (
   (
     C >= Cur,
     search1(I, L, End, Col, Cur, Best, Stores, Map)
   );
   (
     search1(I, L, End, Col, C, Best, Stores, Map)
   )
 )
      )
    );
    /* I and J is not connected */
    (
      search1(I, L, End, Col, Cur, Best, Stores, Map)
    )
  ).

is_connect(I, J, Stores, Map):-
  X is I + 1,
  Y is J + 1,
  ith(X, Stores, Store1),
  store(N1, C1, B1, W1) = Store1,
  ith(Y, Stores, Store2),
  store(N2, C2, B2, W2) = Store2,
  member(link(N1, N2), Map).