From f15cc7d7c8af024204823e82f9d243106a50f2c9 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Tue, 18 Nov 2014 11:34:13 +0100 Subject: [PATCH] cleaned up code --- report/report.tex | 13 ++++++- report/src/task14.pl | 18 --------- report/src/task14part1.pl | 44 +++++++++++++-------- report/src/task14part2.pl | 81 +++++++++++++++++++++++++-------------- 4 files changed, 92 insertions(+), 64 deletions(-) delete mode 100644 report/src/task14.pl diff --git a/report/report.tex b/report/report.tex index e6ecd30..7f6f722 100644 --- a/report/report.tex +++ b/report/report.tex @@ -2,12 +2,11 @@ \usepackage{fullpage} \usepackage{floatrow} -\usepackage{lipsum} \usepackage{enumerate} \usepackage{amsmath} \usepackage{amssymb} \usepackage{minted} -\usepackage[hidelinks]{hyperref} +\usepackage{hyperref} \usepackage{tikz} \author{Mart Lubbers\and Caspar Safarlou} @@ -23,6 +22,16 @@ \everymath{\displaystyle} \floatsetup[listing]{style=Plaintop} +\hypersetup{ + pdfborder={0 0 0}, + pdftitle={Knowledge Representation and Reasoning: Assignment 1}, + pdfauthor={Mart \& Caspar}, + pdfsubject={Knowledge Representation and Reasoning}, + pdfproducer={Mart Lubbers}, + pdfkeywords={Sokoban,Planning,Prolog,Hittingsets,Conflicsets}, + colorlinks=false +} + \definecolor{mintedbackground}{rgb}{0.95,0.95,0.95} \newmintedfile[prologcode]{prolog}{ bgcolor=mintedbackground, diff --git a/report/src/task14.pl b/report/src/task14.pl deleted file mode 100644 index 74f01a7..0000000 --- a/report/src/task14.pl +++ /dev/null @@ -1,18 +0,0 @@ -:- [diagnosis]. - -generateHittingSetTree(SD, COMP, OBS, HS, HSTREE) :- %test with problem1(SD,COMP,OBS), generateHittingSetTree(SD,COMP,OBS,[],HSTREE). This needs to report node([a1], [node([a2], [leaf])]). - tp(SD, COMP, OBS, HS, CS) -> generateParts(SD, COMP, OBS, HS, CS, HSTREE) ; generateParts(_,_,_,_, [], HSTREE). %second part of the OR is needed to translate an empty conflict set into a leaf. - -generateParts(_,_,_,_, [],leaf).%generates leaf if at the end of all possible conflict sets in a branch -generateParts(SD, COMP, OBS, HS, CS, node(CS, RESTOFTREE)) :- %generates node if the conflict set isn't empty and goes on. - repairBranch(SD, COMP, OBS, HS, CS, RESTOFTREE). %repairs the branch by branching out for each item in the conflict set and generating new conflict sets for the next node - - -repairBranch(SD, COMP, OBS, HS, [CONFLICTITEM], [BRANCH]) :- %single item left in conflict set - append(HS, [CONFLICTITEM], HSNEW), %add the used conflict set item for this branch to the new hitting set - generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCH). %find the next new conflict set with the new hitted item -repairBranch(SD, COMP, OBS, HS, [CSHEAD|CSTAIL], [BRANCHHEAD|BRANCHTAIL]) :- %multiple items left in conflict set - append(HS, [CSHEAD], HSNEW), %add the used conflict set item for this branch to the new hitting set - generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCHHEAD), %find the next new conflict set with the new hitted item - repairBranch(SD, COMP, OBS, HS, CSTAIL, BRANCHTAIL). %goes on in recursion for each item in the conflict set of the current node - \ No newline at end of file diff --git a/report/src/task14part1.pl b/report/src/task14part1.pl index 74f01a7..bb1aa53 100644 --- a/report/src/task14part1.pl +++ b/report/src/task14part1.pl @@ -1,18 +1,32 @@ :- [diagnosis]. -generateHittingSetTree(SD, COMP, OBS, HS, HSTREE) :- %test with problem1(SD,COMP,OBS), generateHittingSetTree(SD,COMP,OBS,[],HSTREE). This needs to report node([a1], [node([a2], [leaf])]). - tp(SD, COMP, OBS, HS, CS) -> generateParts(SD, COMP, OBS, HS, CS, HSTREE) ; generateParts(_,_,_,_, [], HSTREE). %second part of the OR is needed to translate an empty conflict set into a leaf. +%test with problem1(SD,COMP,OBS), +%generateHittingSetTree(SD,COMP,OBS,[],HSTREE). This needs to report node([a1], +%[node([a2], [leaf])]). +%second part of the OR is needed to translate an empty conflict set into a leaf. +generateHittingSetTree(SD, COMP, OBS, HS, HSTREE) :- + tp(SD, COMP, OBS, HS, CS) -> generateParts(SD, COMP, OBS, HS, CS, HSTREE); + generateParts(_,_,_,_, [], HSTREE). + +%generates leaf if at the end of all possible conflict sets in a branch +generateParts(_,_,_,_, [],leaf). +%generates node if the conflict set isn't empty and goes on. +generateParts(SD, COMP, OBS, HS, CS, node(CS, RESTOFTREE)) :- + %repairs the branch by branching out for each item in the conflict set and + %generating new conflict sets for the next node + repairBranch(SD, COMP, OBS, HS, CS, RESTOFTREE). -generateParts(_,_,_,_, [],leaf).%generates leaf if at the end of all possible conflict sets in a branch -generateParts(SD, COMP, OBS, HS, CS, node(CS, RESTOFTREE)) :- %generates node if the conflict set isn't empty and goes on. - repairBranch(SD, COMP, OBS, HS, CS, RESTOFTREE). %repairs the branch by branching out for each item in the conflict set and generating new conflict sets for the next node - - -repairBranch(SD, COMP, OBS, HS, [CONFLICTITEM], [BRANCH]) :- %single item left in conflict set - append(HS, [CONFLICTITEM], HSNEW), %add the used conflict set item for this branch to the new hitting set - generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCH). %find the next new conflict set with the new hitted item -repairBranch(SD, COMP, OBS, HS, [CSHEAD|CSTAIL], [BRANCHHEAD|BRANCHTAIL]) :- %multiple items left in conflict set - append(HS, [CSHEAD], HSNEW), %add the used conflict set item for this branch to the new hitting set - generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCHHEAD), %find the next new conflict set with the new hitted item - repairBranch(SD, COMP, OBS, HS, CSTAIL, BRANCHTAIL). %goes on in recursion for each item in the conflict set of the current node - \ No newline at end of file +%single item left in conflict set +repairBranch(SD, COMP, OBS, HS, [CONFLICTITEM], [BRANCH]) :- + %add the used conflict set item for this branch to the new hitting set + append(HS, [CONFLICTITEM], HSNEW), + %find the next new conflict set with the new hitted item + generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCH). +%multiple items left in conflict set +repairBranch(SD, COMP, OBS, HS, [CSHEAD|CSTAIL], [BRANCHHEAD|BRANCHTAIL]) :- + %add the used conflict set item for this branch to the new hitting set + append(HS, [CSHEAD], HSNEW), + %find the next new conflict set with the new hitted item + generateHittingSetTree(SD, COMP, OBS, HSNEW, BRANCHHEAD), + %goes on in recursion for each item in the conflict set of the current node + repairBranch(SD, COMP, OBS, HS, CSTAIL, BRANCHTAIL). diff --git a/report/src/task14part2.pl b/report/src/task14part2.pl index 1a5dd26..ebbe8fa 100644 --- a/report/src/task14part2.pl +++ b/report/src/task14part2.pl @@ -1,33 +1,56 @@ -:- [task14part1] - +:- [task14part1]. +% Adding a variable for the current path extractDiagnoses(HSTree,Diagnoses):- - extractDiagnoses2(HSTree, Diagnoses, []). %adding a variable for the current path - -extractDiagnoses2(leaf, [PATHEND], PATHEND). %set path in set and end recursion when leaf had been reached -extractDiagnoses2(node([], []), [], PATH). %finished clearing empty node -extractDiagnoses2(node([CSHEAD|CSTAIL], [CSHEADBRANCH|CSTAILBRANCHES]), DIAGNOSESSET, CURRENTPATH) :- - append(CURRENTPATH, [CSHEAD], NEWPATH), %add new visited conflict item to the visited path - append(DEPTHPATHS, WIDTHPATHS, DIAGNOSESSET), %recursively collects all paths from the recursive calls into the depth and the width and puts them into the DIAGNOSESSET - extractDiagnoses2(CSHEADBRANCH,DEPTHPATHS,NEWPATH), %continues into the depth of the branch - extractDiagnoses2(node(CSTAIL, CSTAILBRANCHES), WIDTHPATHS, CURRENTPATH). %calls on all conflict items in the width of the branch - -getLengthSmallestSet([DIAGNOSIS], DIAGNOSISLENGTH):- %computes length of smallest diagnosis - length(DIAGNOSIS,DIAGNOSISLENGTH). %calls length single diagnosis -getLengthSmallestSet([HEADDIAGNOSIS|RESTOFDIAGNOSES], Minimal):- - getLengthSmallestSet(RESTOFDIAGNOSES, RESTLENGTH), %recursively gets the length of tail - length(HEADDIAGNOSIS,HEADLENGTH), %initialises length of the head diagnosis - Minimal is min(HEADLENGTH, RESTLENGTH). %gets minimal length of diagnoses + extractDiagnoses2(HSTree, Diagnoses, []). + +% Set path in set and end recursion when leaf had been reached +extractDiagnoses2(leaf, [PathEnd], PathEnd). +% Finished clearing empty node +extractDiagnoses2(node([], []), [], _). +extractDiagnoses2(node([CsHead|CsTail], [CsHeadBranch|CsTailBranches]), + DiagnosesSet, CurrentPath) :- + % Add new visited conflict item to the visited path + append(CurrentPath, [CsHead], NewPath), + % Recursively collects all paths from the recursive calls into the depth + % and the width and puts them into the DiagnosesSet + append(DepthPaths, WidthPaths, DiagnosesSet), + % Continues into the depth of the branch + extractDiagnoses2(CsHeadBranch,DepthPaths,NewPath), + % Calls on all conflict items in the width of the branch + extractDiagnoses2(node(CsTail, CsTailBranches), WidthPaths, CurrentPath). + +% Computes length of smallest diagnosis +getLengthSmallestSet([Diagnosis], DiagnosisLength):- + % Calls length single diagnosis + length(Diagnosis,DiagnosisLength). +getLengthSmallestSet([HeadDiagnosis|RestOfDiagnoses], Minimal):- + % Recursively gets the length of tail + getLengthSmallestSet(RestOfDiagnoses, RestLength), + % Initialises length of the head diagnosis + length(HeadDiagnosis,HeadLength), + % Gets minimal length of diagnoses + Minimal is min(HeadLength, RestLength). filterLength(X,Y):- - length(Y, LENGTHY), - X \== LENGTHY. %checks if the set isn't bigger than the checked set - -getSubsetMinimalDiagnoses(DIAGNOSESSETS, MINIMALDIAGNOSESSETS):- %deze functie moet opnieuw geschreven worden, hij moet de subsetminimal opleveren en niet de kleinste diagnoses - getLengthSmallestSet(DIAGNOSESSETS,LENGTH),!, - exclude(filterLength(LENGTH), DIAGNOSESSETS, MINIMALDIAGNOSESSETS). %excludes sets that are bigger than the smallest set - -subsetMinimalDiagnoses(SD, COMP, OBS, MINIMALDIAGNOSESSETS) :- %function that returns minimal hitting sets from a problem - generateHittingSetTree(SD, COMP, OBS, [], HSTREE), %generate hitting tree - extractDiagnoses(HSTREE, DIAGNOSESSETS), %get diagnoses out of the hitting tree - getSubsetMinimalDiagnoses(DIAGNOSESSETS, MINIMALDIAGNOSESSETS). %determine subset minimal diagnoses \ No newline at end of file + length(Y, LengthY), + %checks if the set isn't bigger than the checked set + X \== LengthY. + +% Deze functie moet opnieuw geschreven worden, hij moet de subsetminimal +% opleveren en niet de kleinste diagnoses +getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets):- + getLengthSmallestSet(DiagnosesSets,Length),!, + % Excludes sets that are bigger than the smallest set + exclude(filterLength(Length), DiagnosesSets, MinimalDiagnosesSets). + +% Function that returns minimal hitting sets from a problem +subsetMinimalDiagnoses(SD, COMP, OBS, MinimalDiagnosesSets) :- + % Generate hitting tree + generateHittingSetTree(SD, COMP, OBS, [], HsTree), + write(HsTree), + % Get diagnoses out of the hitting tree + extractDiagnoses(HsTree, DiagnosesSets), + write(DiagnosesSets), + % Determine subset minimal diagnoses + getSubsetMinimalDiagnoses(DiagnosesSets, MinimalDiagnosesSets). -- 2.20.1