CS代考 Logic Programming in Prolog

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