Logic Programming in Prolog
• Datastructures • Trees
– Representation
– Examples
Copyright By PowCoder代写 加微信 powcoder
– Binary search tree
– Representation – Graph problems
Logic Programming in Prolog
• Datastructures • Trees
– Representation
– Examples
– Binary search tree
– Representation – Graph problems
Binary Trees
• Treewhereeachelementhasoneparentanduptotwo children
– Common data structure
Binary Trees in Prolog
• Defineafactforanodeinthedatastructure
t(element, left, right)
– element is the value stored at the node
– left is the left subtree
– right is the right subtree
– an empty subtree can be marked with a ‘nil’
• Atreewithonlytherootnodeist(1,nil,nil)
• Abalancedbinarytreewiththreenodes
t(1,t(2,nil,nil),t(3,nil,nil)).
A Binary Tree
treeA(X) :- X= t(73,
t(5,nil,nil),
t(97,nil,nil)),
Inorder Traversal
inorder(nil).
inorder(t(Root,Left,Right)) :-
inorder(Left),
write(Root),
write(‘ ‘),
inorder(Right).
?- treeB(X), inorder(X).
5 31 73 83 97 101
X = t(73, t(31, t(5, nil, nil), nil), t(101, t(83, nil, t(97, nil, nil)), nil)).
Binary Search Tree
• Sortpredicate(assumingnoduplicates)
precedes(Key1, Key2) :- Key1 < Key2.
• Boundarycase:Searchedfornodefound
binarySearch(Key, t(Key, _, _)).
• Searchinleftsubtree
binarySearch(Key, t(Root, Left, _)) :- precedes(Key, Root), binarySearch(Key, Left).
• Searchinrightsubtree
binarySearch(Key, t(Root, _, Right)) :- precedes(Root, Key), binarySearch(Key, Right).
Element Insertion in a BST
• Boundarycaseinsertnewleafnode
insert(Key, nil, t(Key, nil, nil)).
• Insertnewnodeontheleft
insert(Key, t(Root, Left, Right), t(Root, LeftPlus, Right)) :-
precedes(Key, Root),
insert(Key, Left, LeftPlus).
• Insertnewnodeontheright
insert(Key, t(Root, Left, Right), t(Root, Left, RightPlus)) :-
precedes(Root, Key), insert(Key, Right, RightPlus).
Deleting a Key at the Root
• Boundarycasereplacekeywiththerightsubtree
deleteBST(Key, t(Key, nil, Right), Right).
• Boundarycasereplacekeywiththeleftsubtree
deleteBST(Key, t(Key, Left, nil), Left).
• Deleterootandreplacewithmaximumleftkey
deleteBST(Key, t(Key, Left, Right),
t(NewRoot, NewLeft, Right)) :-
removeMax(Left, NewLeft, NewRoot).
– argumentsofremoveMax
% removeMax(Tree,NewTree,Max)
Deleting any Key
• Searchontheleftsubtreeforkeytodelete
deleteBST(Key, t(Root, Left, Right),
t(Root, LeftSmaller, Right)) :-
precedes(Key, Root),
deleteBST(Key, Left, LeftSmaller).
• Searchontherightsubtreeforkeytodelete
deleteBST(Key, t(Root, Left, Right),
t(Root, Left, RightSmaller)) :-
precedes(Root, Key),
deleteBST(Key, Right, RightSmaller).
Deleting the Maximum Element
• boundarycaseright-mostnodeismaximum
removeMax(t(Max, Left, nil), Left, Max).
• recursionontherightoftherootnode(fortreenodes sorted with less than).
removeMax(t(Root, Left, Right),
t(Root, Left, RightSmaller), Max) :-
removeMax(Right, RightSmaller, Max).
General Graphs
• Abinarytreeisatree,andatreeisa(restricted)graph • Graphrepresentation
g([Node,...],[edge(Node1,Node2,Weight),...]).
– directed edge
edge(g(Ns,Edges),N1,N2,Weight):-
member(edge(N1,N2,Weight),Edges).
– undirected edge
edge(g(Ns,Edges),N1,N2,Weight):-
member(edge(N1,N2,Weight),Edges);
member(edge(N2,N1,Weight),Edges).
Neighbors of a Node
• Find all neighboring nodes and the connecting edge (use with edge/4 predicate).
neighbors(Graph,Node,Neighbors):- setof((N,Edge),edge(Graph,Node,N,Edge),Neighbors).
– Define a graph
graphA(X) :- X=g([a,b,c,d,e,f],
[edge(a,b,3),ledge(a,c,5), edge(a,d,7),
– Example queries
?- graphA(X), neighbors(X,c,V).
V = [ (a, 5)].
?- graphA(X), neighbors(X,a,V).
V = [ (b, 3), (c, 5), (d, 7)].
edge(e,f,1), edge(d,f,6)]).
Graph Coloring
color(g(Ns,Edges),Colors,GC):-
generate(Ns,Colors,GC),
test(Edges,GC).
generate([],_,[]). generate([N|Ns],Colors,[(N,C)|Q]):-
member(C,Colors),
generate(Ns,Colors,Q).
test([],_).
test([edge(N1,N2,_)|Es],GC):- member((N1,C1),GC),
member((N2,C2),GC),
test(Es,GC).
Graph Coloring Queries
?- graphA(X), color(X,[red,blue,white,green],V).
X = g([a, b, c, d, e, f], [edge(a, b, 3), edge(a, c, 5), edge(a, d, 7), edge(e, f, 1), edge(d, f, 6)]), V = [ (a, red), (b,
red), (f, white)] ;
V = [ (a, red), (b, blue), (c, blue), (d, blue), (e, red), (f, green)] ;
V = [ (a, red), (b, blue), (c, blue), (d, blue), (e, blue), (f, red)] ;
blue), (c, blue), (d, blue), (e,
Graph Problem: Labyrinth
link(0,1). % start = 0
link(1,2).
link(2,6).
link(6,5).
link(6,7).
link(5,4).
link(5,9).
link(9,8).
link(8,12).
link(9,10).
link(10,11).
link(9,13).
link(13,14).
link(14,15). % finish = 15
10 11 12 13 14 15
Labyrinth Solution
• Predicate generating undirected edges
successor(A,B) :- link(A,B). successor(A,B) :- link(B,A).
• Define the finish node
finish(15).
• Boundary case if finish is reached
pathFinder([Last|Path],[Last|Path]) :- finish(Last).
• Go to the next node in a depth first manner unless it is a loop
pathFinder([Curr|Path],Solution) :-
successor(Curr,Next),
\+member(Next,Path),write(Next),nl, pathFinder([Next,Curr|Path],Solution).
Example: Labyrinth
?- pathFinder([0],S).
S = [15, 14, 13, 9, 5, 6, 2, 1, 0] ;
• Binarytree
– tree representation – binary search tree – insert an element – delete an element
– graph representation – graph search
– graph coloring
– labyrinth
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com