Solving Combinatorial Search
Problems Using B-Prolog
Neng-Fa Zhou
周 能法
The City University of New Yorkzhou@sci.brooklyn.cuny.edu
by Neng-Fa Zhou at Kyutech1

B-Prolog:
Prolog + Tabling + CLP(FD) Prolog– Rule-based relational language• SQL + Recursion + Unification + Backtracking

 Tabling– Memorize and reuse intermediate results• Suitable for dynamic programming problems

 CLP(FD)– Constraint Logic Programming over Finite Domains• Suitable for constraint satisfaction problems (NP-complete)
by Neng-Fa Zhou at Kyutech2

Prolog A program consists of relations defined byfacts and rules
 Unification
 Recursion
 Nondeterminism realized throughbacktracking

by Neng-Fa Zhou at Kyutech3Prolog – An example
app([],Ys,Ys).
app([X|Xs],Ys,[X|Zs]):app(Xs,Ys,Zs).

by Neng-Fa Zhou at Kyutech

4

Syntax of Prolog
 Term
• Atom– string of letters, digits, and '_' starting with a low-caseletter– string of characters enclosed in quotes• Number– integer & real

• Variable– string of letters, digits and '_' starting with a capital letteror '_'by Neng-Fa Zhou at Kyutech

5Syntax of Prolog (Cont)• Structure– f(t1,t2,...,tn)» f is an atom, called the functor of the structure» t1,t2,...,tn are terms• List– '.'(H,T) => [H|T]– '.'(1,'.'(2,'.'(3,[]))) => [1,2,3]

by Neng-Fa Zhou at Kyutech

6Syntax of Prolog (Cont)
 Clause• FactHead– p(t1,t2,...,tn)• Rule– H :- B1,B2,...,Bm.

Body

 Predicate• a sequence of clauses

 Program• a set of predicates Query

by Neng-Fa Zhou at Kyutech

7

Unification
 t1 = t2 succeeds if– t1 and t2 are identical– there exists a substitution q for the variables in
t1 and t2 such that t1q = t2q.
f(X,b)=f(a,Y).
X=a
Y=bq = {X/a, Y/b}

by Neng-Fa Zhou at Kyutech

8Unification: Examples?-X=1.
X=1?- f(a,b)=f(a,b).
yes?- a=b.
no?- f(X,Y)=f(a,b)
X=a
Y=b?-f(X,b)=f(a,Y).
X=a
Y=b?-X = f(X).
X=f(f(......

assignment
test

test
matching

unification

without occur checking

by Neng-Fa Zhou at Kyutech

9Operational Semantics of Prolog(Resolution)
G0:

initial queryGi:(A1,A2,...,An)
H:-B1,...,Bm
A1q=HqGi+1:(B1,...,Bm,A2,...,An)q

Succeed if Gk is empty for some k.
Backtrack if Gk is a dead end (no clause can be used).
by Neng-Fa Zhou at Kyutech

10Deductive Databaseparent(Parent,Child):-father(Parent,Child).
parent(Parent,Child):-mother(Parent,Child).
uncle(Uncle,Person) :brother(Uncle,Parent), parent(Parent,Person).
sibling(Sib1,Sib2) :-parent(Parent,Sib1), parent(Parent,Sib2),
Sib1 ¥= Sib2.

cousin(Cousin1,Cousin2) :parent(Parent1,Cousin1),
parent(Parent2,Cousin2),
sibling(Parent1,Parent2).
by Neng-Fa Zhou at Kyutech

11

Exercises
 Define the following relations– son(X,Y) -- X is a son of Y
– daughter(X,Y) -- X is a daughter of Y
– grandfather(X,Y) -- X is the grandfather of Y
– grandparent(X,Y) -- X is a grandparent of Y
– ancestor(X,Y) – X is an ancestor of Y

by Neng-Fa Zhou at Kyutech

12

Recursive Programming on Lists
 A list is a special structure whose functor is '.'/2– []– '.'(H,T)=> [H|T]– '.'(1,'.'(2,'.'(3,[])))=> [1,2,3]

 Unification of lists– [X|Xs]=[1,2,3]
X= 1
Xs=[2,3]– [1,2,3] = [1|[2|X]]
X=[3]– [1,2|3] = [1|X]
X=[2|3]by Neng-Fa Zhou at Kyutech

13

Relations on Lists
 isList(Xs)
isList([]).
isList([X|Xs]):-isList(Xs).

 member(X,Xs)

member(X,[X|Xs]).
member(X,[_|Xs]):-member(X,Xs).

 append(Xs,Ys,Zs)
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]):-append(Xs,Ys,Zs).

 length(Xs,N)
length([],0).
by Neng-Fa Zhou at Kyutech
length([X|Xs],N):-length(Xs,N1),N
is N1+1.

14

Exercise– reverse(Xs,Ys)

 Implement thefollowing predicates.
– length(Xs,N)• Ys is the reverse of Xs– sum(Xs,N)• N is the sum of theintegers in the list Xs• the length of Xs is N

– sum1(Xs,Ys)– last(X,Xs)• assume Xs is[x1,x2,...,xn], then Ys willbe [y1,y2,...,yn] where yi
is xi+1.

• X is the last element of
Xs.

– prefix(Pre,Xs)• Pre is a prefix of Xs.

– sort(L,SortedL)– suffix(Pos,Xs)• suffix is a postfix of Xs
by Neng-Fa Zhou at Kyutech• use the exchange sortalgorithm

15

Recursive Programming on
Binary Trees Representation of binary treesvoid-t(N, L,R) -- Example

empty tree
N : node
L : Left child
R : Right childat(a, t(b, void,void), t(c,void,void))bcby Neng-Fa Zhou at Kyutech

16

Relations on Binary Trees isBinaryTree(T)-- T is a binary tree
isBinaryTree(void).
isBinaryTree(t(N,L,R)):isBinaryTree(L),isBinaryTree(R).

 count(T,C) -- C is the number of nodes in T.
count(void,0).
count(t(N,L,R),N):count(L,N1),
count(R,N2),
N is N1+N2+1.

by Neng-Fa Zhou at Kyutech

17

Relations on Binary Trees (Cont.)
 preorder(T,L)• L is a pre-order traversal of the binary tree T.
preorder(void,[]).
preorder(t(N,Left,Right),L):preorder(Left,L1),
preorder(Right,L2),
append([N|L1],L2,L).

by Neng-Fa Zhou at Kyutech

18

Exercise Write the following predicates on binary

trees.
– leaves(T,L): L is the list of leaves in T.
The order is preserved.
– equal(T1,T2): T1 and T2 are the sametree.
– postorder(T,L): L is the post-order
traversal of T.
by Neng-Fa Zhou at Kyutech

19

Tabling (Why?) Eliminate infinite loops:-table path/2.
path(X,Y):-edge(X,Y).
path(X,Y):-edge(X,Z),path(Z,Y).

 Reduce redundant computations:-table fib/2.
fib(0,1).
fib(1,1).
fib(N,F):N>1,
N1 is N-1,fib(N1,F1),
N2 is N-2,fib(N2,F2),
F is F1+F2.
by Neng-Fa Zhou at Kyutech

20Mode-Directed Tabling Table mode declaration:-table p(M1,...,Mn):C.
– C: Cardinality limit– Modes• + : input• - : output• min: minimized• max: maximized
by Neng-Fa Zhou at Kyutech

21

Shortest Path Problem:-table sp(+,+,-,min).
sp(X,Y,[(X,Y)],W) :edge(X,Y,W).
sp(X,Y,[(X,Z)|Path],W) :edge(X,Z,W1),
sp(Z,Y,Path,W2),
W is W1+W2.

 sp(X,Y,P,W)– P is a shortest path between X and Y withweight W.
by Neng-Fa Zhou at Kyutech

22Knapsack Problem
http://probp.com/examples/tabling/knapsack.pl:- table knapsack(+,+,-,max).
knapsack(_,0,[],0).
knapsack([_|L],K,Selected,V) :knapsack(L,K,Selected,V).
knapsack([F|L],K,[F|Selected],V) :K1 is K - F, K1 >= 0,
knapsack(L,K1,Selected,V1),
V is V1 + 1.

 knapsack(L,K,Selected,V)– L: the list of items– K: the total capacity– Selected: the list of selected items– V: the length of Selectedby Neng-Fa Zhou at Kyutech

23

Exercises (Dynamic
Programming)
1. Maximum Value Contiguous Subsequence. Given asequence of n real numbers a1, ... an, determine acontiguous subsequence Ai ... Aj for which the sum ofelements in the subsequence is maximized.
2. Given two text strings A of length n and B of length m, youwant to transform A into B with a minimum number ofoperations of the following types: delete a character fromA, insert a character into A, or change some character in A
into a new character. The minimal number of suchoperations required to transform A into B is called the edit
distance between A and B.
by Neng-Fa Zhou at Kyutech24

CLP(FD) by Example (I) The rabbit and chicken problem

 The Kakuro puzzle The knapsack problem
 Exercises

by Neng-Fa Zhou at Kyutech

25

The Rabbit and Chicken Problem
 In a farmyard, there are only chickens and rabbits.
Its is known that there are 18 heads and 58 feet.
How many chickens and rabbits are there?
go:-[X,Y] :: 1..18,
X+Y #= 18,
2*X+4*Y #= 58,
labeling([X,Y]),
writeln([X,Y]).
by Neng-Fa Zhou at Kyutech

26

Break the Code Downgo:- go -- a predicate
 X,Y -- variables
 1..58 -- a domain[X,Y] :: 1..58,  X :: D -- a domain declaration
X+Y #= 18,
 E1 #= E2 -- equation (or2*X+4*Y #= 58,
equality constraint)labeling([X,Y]),
writeln([X,Y]).  labeling(Vars)-- find a

valuation for variables thatsatisfies the constraints
 writeln(T) -- a Prolog builtin
by Neng-Fa Zhou at Kyutech

27

Running the Program| ?- cl(rabbit)
Compiling::rabbit.pl
compiled in 0 milliseconds
loading::rabbit.out
yes| ?- go[7,11]by Neng-Fa Zhou at Kyutech

28

The Kakuro Puzzle
 Kakuro, another puzzle originated in Japan after Sudoku,
is a mathematical version of a crossword puzzle that uses
sums of digits instead of words. The objective of Kakuro
is to fill in the white squares with digits such that eachdown and across “word” has the given sum. No digit canbe used more than once in each “word”.

by Neng-Fa Zhou at Kyutech

29

An Example
X1

X2

X3

X4

X5

X7

X8

X6

X9 X10

X11 X12 X13 X14

go:Vars=[X1,X2,…,X16],
Vars :: 1..9,word([X1,X2],5),word([X3,X4,X5,X6],17),…
word([X10,X14],3),
labeling(Vars),
writeln(Vars).

X15 X16

A Kakuro puzzle

word(L,Sum):sum(L) #= Sum,
all_different(L).

by Neng-Fa Zhou at Kyutech

30

Break the Code Down sum(L) #= Sum

The sum of the elements in L makes Sum.
e.g., sum([X1,X2,X3]) #= Y is the same as
X1+X2+X3 #= Y.

 all_different(L)Every element in L is different.
by Neng-Fa Zhou at Kyutech

31

The Knapsack Problem
 A smuggler has a knapsack of 9 units. He can smuggle inbottles of whiskey of size 4 units, bottles of perfume ofsize 3 units, and cartons of cigarettes of size 2 units. The
profit of smuggling a bottle of whiskey, a bottle ofperfume or a carton of cigarettes is 15, 10 and 7,
respectively. If the smuggler will only take a trip, how can
he take to make the largest profit?
go:[W,P,C] :: 0..9,4*W+3*P+2*C #=< 9,
maxof(labeling([W,P,C]),15*W+10*P+7*C),
writeln([W,P,C]).
by Neng-Fa Zhou at Kyutech

32

Break the Code Down maxof(Goal,Exp)

Find an instance of Goal that is true andmaximizes Exp.

by Neng-Fa Zhou at Kyutech

33

Exercises
1.

2.

3.

Tickets to a carnival cost 250 JPY for students and 400
JPY for adults. If a group buys 10 tickets for a total of
3100 JPY, how many of the tickets are for students?
The product of the ages, in years, of three teenagers is4590. None of the teens are the same age. What are theages of the teenagers?
Suppose that you have 100 pennies, 100 nickels, and 100
dimes. Using at least one coin of each type, select 21
coins that have a total value of exactly $1.00. How manyof each type did you select?
by Neng-Fa Zhou at Kyutech

34

Exercises (Cont.)
4.

If m and n are positive integers, neither of which
is divisible by 10, and if mn = 10,000, find thesum m+n.

5.

The arithmetic cryptographic puzzle: Find distinct digits
for S, E, N, D, M, O, R, Y such that S and M are nonzero and the equation SEND+MORE=MONEY issatisfied.
A magic square of order 3x3 is an arrangement ofintegers from 1 to 9 such that all rows, all columns, andboth diagonals have the same sum.

6.

by Neng-Fa Zhou at Kyutech

35

Exercises (Cont.)
7.

8.

Place the numbers 2,3,4,5,6,7,8,9,10 in the boxes so thatthe sum of the numbers in the boxes of each of the four
circles is 27.
Sudoku puzzle.

by Neng-Fa Zhou at Kyutech

36

Exercises (Cont.)
9.

A factory has four workers w1,w2,w3,w4 and four
products p1,p2,p3,p4. The problem is to assign workers
to products so that each worker is assigned to one
product, each product is assigned to one worker, and the
profit maximized. The profit made by each worker
working on each product is given in the matrix.
p1 p2 p3 p4
w1 7
1
3
4
Profit matrix is: w2 8 2 5 1
w3 4
3
7
2
by Neng-Fa
w4 Zhou3at Kyutech
1
6
3

37

Review of CLP(FD) Declaration of domain variables• X :: L..U
• [X1,X2,...,Xn] :: L..U Constraints• Exp R Exp (– R is one of the following: #=, #¥=, #>, #>=, #<, #=<– Exp may contain +, -, *, /, //, mod, sum, min, max• all_different(L) Labeling• labeling(L)• minof(labeling(L),Exp) and maxof(labeling(L),Exp)
by Neng-Fa Zhou at Kyutech

38

CLP(FD) by Example (II) The graph coloring problem

 The N-queens problem
 The magic square problem
 Exercises

by Neng-Fa Zhou at Kyutech

39Graph Coloring Given a graph G=(V,E) and a set of colors,

assign a color to each vertex in V so that notwo adjacent vertices share the same color.
The map of Kyushu
FukuokaKagoshima
Kumamoto
MiyazakiNagasakiOita
Sagaby Neng-Fa Zhou at Kyutech

40Color the Map of Kyushu
go:Vars=[Cf,Cka,Cku,Cm,Cn,Co,Cs],
Vars :: [red,blue,purple],
Cf #¥= Cs,
Cf #¥= Co,…
labeling(Vars),
writeln(Vars).

 Atoms– red, blue, purple
by Neng-Fa Zhou at Kyutech

41

The N-Queens Problem
 Find a layout for the N queens on an NxN chessboard so that no queens

attack each other. Two queens attack each other if they are placed in thesame row, the same column, or the same diagonal.

Qi: the number of the row for the ith queen.
for each two different variables Qi and Qj
Qi #¥= Qj%not same row
abs(Qi-Qj) #¥= abs(i-j) %not same diagonal

by Neng-Fa Zhou at Kyutech

42

The N-Queens Problem (Cont.)
http://probp.com/examples/foreach/queens.pl
queens(N):length(Qs,N),
Qs :: 1..N,
foreach(I in 1..N-1, J in I+1..N,(Qs[I] #¥= Qs[J],abs(Qs[I]-Qs[J]) #¥= J-I)),labeling_ff(Qs),writeln(Qs).

by Neng-Fa Zhou at Kyutech

43

Break the Code Down
 length(L,N)?-length([a,b,c],N)N = 3?-length(L,3)
L = [_310,_318,_320]

 foreach(I1 in D1,…,In in Dn,Goal)?-L=[a,b,c],foreach(E in L, writeln(E))

 Array access notation A[I1,…,In]
by Neng-Fa Zhou at Kyutech

44

Break the Code Down labeling_ff(L)– Label the variables in L by selecting first avariable with the smallest domain. If there are
multiple variables with the same domain size,
then choose the left-most one (First-failprinciple).

by Neng-Fa Zhou at Kyutech

45

Magic Square A magic square of order NxN is an arrangement of integers

from 1 to N2 such that all rows, all columns, and bothprincipal diagonals have the same sum
X11X12 … X1n…

Xn1 Xn2…

Xnn

by Neng-Fa Zhou at Kyutech

46

Magic Square (Cont.)
http://probp.com/examples/foreach/magic.pl
go(N):new_array(Board,[N,N]),
NN is N*N,
Vars @= [Board[I,J] : I in 1..N, J in 1..N],
Vars :: 1..NN,
Sum is NN*(NN+1)//(2*N),
foreach(I in 1..N,sum([Board[I,J] : J in 1..N]) #= Sum),
foreach(J in 1..N,sum([Board[I,J] : I in 1..N]) #= Sum),sum([Board[I,I] : I in 1..N]) #= Sum,sum([Board[I,N-I+1] : I in 1..N]) #= Sum,
all_different(Vars),labeling([ffc],Vars),
writeln(Board).
by Neng-Fa Zhou at Kyutech

47

Break the Code Down
 List comprehension[T : E1 in D1, . . ., En in Dn,Goal]– Calls to @=/2?- L @= [X : X in 1..5].
L=[1,2,3,4,5]?-L @= [(A,I): A in [a,b], I in 1..2].
L= [(a,1),(a,2),(b,1),(b,2)]– Arithmetic constraintssum([A[I,J] : I in 1..N, J in 1..N]) #= N*N
by Neng-Fa Zhou at Kyutech

48

Exercises
1. Write a CLP(FD) program to test if themap of Japan is 3-colorable (can becolored with three colors).
2. Write a program in your favorite language
to generate a CLP(FD) program forsolving the magic square problem.

by Neng-Fa Zhou at Kyutech

49

Exercises (Cont.)
3. Find an integer programming problem andconvert it into CLP(FD).
4. Find a constraint satisfaction or
optimization problem and write a
CLP(FD) program to solve it.

by Neng-Fa Zhou at Kyutech

50

CLP(Boolean): A Special Case of
CLP(FD)

by Neng-Fa Zhou at Kyutech

51

CLP(FD) by Example (III) Maximum flow

 Scheduling Traveling salesman problem (TSP) Planning Routing Protein structure predication
by Neng-Fa Zhou at Kyutech52

Maximum Flow Problem
 Given a network G=(N,A) where N is a setof nodes and A is a set of arcs. Each arc (i,j)
in A has a capacity Cij which limits theamount of flow that can be sent throw it.
Find the maximum flow that can be sent
between a single source and a single sink.

by Neng-Fa Zhou at Kyutech

53

Maximum Flow Problem (Cont.)

Capacity matrix

by Neng-Fa Zhou at Kyutech54

Maximum Flow Problem (Cont.)
go:Vars=[X12,X13,X14,X27,X32,X36,X43,
X45,X58,X62,X65,X68,X76,X78],
X12 :: 0..3, X13 :: 0..2, X14 :: 0..3,
X27 :: 0..5, X32 :: 0..1, X36 :: 0..1,
X43 :: 0..2, X45 :: 0..2, X58 :: 0..5,
X62 :: 0..4, X65 :: 0..5, X68 :: 0..1,
X76 :: 0..2, X78 :: 0..3,
X12+X32+X62-X27 #= 0,
X13+X43-X32-X36 #= 0,
X14-X43-X45 #= 0,
X45+X65-X58 #= 0,
X36+X76-X62-X65-X68 #= 0,
X27-X76-X78 #= 0,
Max #= X58+X68+X78,
maxof(labeling(Vars),Max),
writeln(sol(Vars,Max)).
by Neng-Fa Zhou at Kyutech

55

Other Network Problems
 Routing– Find routes from sources and sinks in a graph Upgrading– Upgrade nodes in a network to meet certain
performance requirement with the minimumcost Tomography– Determine the paths for probing packages
by Neng-Fa Zhou at Kyutech

56

Scheduling Problem
 Four roommates are subscribing to four newspapers. The following

gives the amounts of time each person spend on each newspaper:
Person/Newspaper/Minutes=============================================
Person || Asahi | Nishi | Orient | Sankei
Akiko || 60 | 30 | 2 | 5
Bobby || 75 | 3 | 15 | 10
Cho ||
5 | 15 | 10 | 30
Dola || 90 | 1 | 1 | 1

Akiko gets up at 7:00, Bobby gets up at 7:15, Cho gets up at 7:15, andDola gets up at 8:00. Nobody can read more than one newspaper at atime and at any time a newspaper can be read by only one person.
Schedule the newspapers such that the four persons finish thenewspapers at an earliest possible time.
by Neng-Fa Zhou at Kyutech

57

Scheduling Problem (Cont.) Variables– For each activity, a variable is used to represent the start
time and another variable is used to represent the end time.
• A_Asahi : The start time for Akiko to read Asahi• EA_Asahi: The time when Akiko finishes reading Asahi

 Constraints– A_Asahi #>= 7*60 : Akiko gets up at 7:00
– Nobody can read more than one newspaper at a time
– A newspaper can be read by only one person at a time The objective function– Minimize the maximum end timeby Neng-Fa Zhou at Kyutech

58

Scheduling Problem (Cont.)
go:Vars = [A_Asahi,A_Nishi,A_Orient,A_Sankei,…],A_Asahi #>= 7*60, A_Nishi #>= 7*60, …
B_Asahi #>=7*60+15, B_Nishi #>= 7*60+15, …
…
cumulative([A_Asahi,A_Nishi,A_Orient,A_Sankei],[60,30,2,5],[1,1,1,1],1),…
EA_Asahi #= A_Asahi+60, EA_Nishi #= A_Nishi+30,…
max([EA_Asahi,EA_Nishi,…]) #= Max,
minof(labeling(Vars),Max),
writeln(Vars).

by Neng-Fa Zhou at Kyutech

59

Break the Code Down cumulative(Starts,Durations,Resources,Limit)

Let Starts be [S1,S2,...,Sn], Durations be [D1,D2,...,Dn] andResources be [R1,R2,...,Rn]. For each job i, Si represents the start
time, Di the duration, and Ri the units of resources needed. Limit is
the units of resources available at any time.
The jobs are mutually disjoint when Resources is [1,…,1] andLimit is 1.
Si #>= Sj+Dj #¥/ Sj #>= Si+Di (for i,j=1..n, i j)

by Neng-Fa Zhou at Kyutech

60

Traveling Salesman Problem
 Given an undirected graph G=(V,E), where

V is the set of nodes and E the set of edges,
each of which is associated with a positive
integer indicating the distance between thetwo nodes, find a shortest possible
Hamiltonian cycle that connects all thenodes.
by Neng-Fa Zhou at Kyutech

61

Traveling Salesman Problem(Cont.)
go:max_node_num(N), % Nodes are numbered 1,2, …, N
length(Vars,N),
decl_domains(Vars,1),
circuit(Vars),findall(edge(X,Y,W),edge(X,Y,W),Edges),collect_weights(Edges,Vars,Weights),
TotalWeight #= sum(Weights),
minof(labeling_ff(Vars),TotalWeight,writeln((Vars,TotalWeight))).
decl_domains([],_).
decl_domains([Var|Vars],X):findall(Y,edge(X,Y,_),Ys),
Var :: Ys,
X1 is X+1,
decl_domains(Vars,X1).
collect_weights([],_,[]).
collect_weights([edge(X,Y,W)|Es],Vars,[B*W|Ws]):nth(X,Vars,NX),nth(Y,Vars,NY),
B #<=> (NX#=Y #¥/ NY#=X),
collect_weights(Es,Vars,Ws).

by Neng-Fa Zhou at Kyutech

62

Break the Code Down circuit(L)Let L=[X1,X2,…,Xn]. A valuation
satisfies the constraint if 1->X1,2->X2,…, n->Xn forms a Hamilton cycle.
 minof(Goal,Obj,Report)
Call Report each time a solution is found.
 Reification constraints
B #<=> (NX#=Y #¥/ NY#=X),
by Neng-Fa Zhou at Kyutech

63Planning Blocks world problem

by Neng-Fa Zhou at Kyutech

64Planning (Cont.)
 States and variables (m blocks and n states)

S1 S2 … Sn
Si=(Bi1,Bi2,…,Bim)
Bij = k (block j is on top of block k,block 0 means the table) Constraints– Every transition Si -> Si+1 must be valid.
by Neng-Fa Zhou at Kyutech

65

Channel Routing

N1={t(1),b(3)}N2={b(1),t(2)}by Neng-Fa Zhou at Kyutech

66

Channel Routing (Cont.) Variables– For each net, use two variables L and T torepresent the layer and track respectively
 Constraints– No two line segments can overlap

 Objective functions– Minimize the length (or areas) of wires
by Neng-Fa Zhou at Kyutech

67

Protein Structure Predication

by Neng-Fa Zhou at Kyutech

68Protein Structure Predication(Cont.)
 Variables– Let R=r1,…,rn be a sequence of residues. A structure of
R is represented by a sequence of points in a threedimensional space p1,…,pn where pi=<xi,yi,zi>.
 Constraints– A structure forms a self-avoiding walk in the space The objective function– The energy is minimized

by Neng-Fa Zhou at Kyutech

69

Demo
 B-Prolog version 7.4– CLP(FD)+ CGLIB– www.probp.com/examples.htm

NJPLS-10-4, N.F. Zhou

70

Constraint Systems
 CLP systems– B-Prolog– BNR-Prolog– CHIP– CLP(R)– ECLiPSe - CISCO– GNU-Prolog– IF/Prolog– Prolog-IV– SICStus Other systems– 2LP– ILOG solver
– OPL
– Oz
– Gcode– Choco More information– Languages & compilers– Logic programming– Constraint programmingby Neng-Fa Zhou at Kyutech

71

Major References
 B-Prolog virtual machine– N.F. Zhou: Parameter Passing and Control Stack Management in Prolog
Implementation Revisited, ACM TOPLAS, 1996.
– N.F. Zhou: The Language Features and Architecture of B-Prolog, TPLP
special issue, 2011.
 Action rules and constraint solving– N.F. Zhou: Programming Finite-Domain Constraint Propagators in Action
Rules, TPLP, 2006.
– N.F. Zhou: Encoding Table Constraints in CLP(FD) Based on Pair-wise
AC, ICLP, 2009.
 Tabling– N.F. Zhou: T. Sato and Y.D. Shen: Linear Tabling Strategies andOptimizations, TPLP, 2008.
– N.F. Zhou: Y. Kameya and T. Sato, Mode-directed Tabling for …, Tools
for Artificial Intelligence, 2010. (submitted)
by Neng-Fa Zhou at Kyutech

72