\subsection{Implementation of the hitting-set algorithm}
\subsubsection{Task 12: Generate conflict}
Can be found in \textit{./src/task12.pl} or in Listing~\ref{task12}.
+\\ \\The tp command runs through a list of commands, which we will discuss here in the same order:
+\\Subtract: removes the components assumed to be abnormal from the set of all components and puts these in NormComp (the predicates assumed to be normal.).
+\\Maplist: maps the function Normal over all pairs of NormComp (the predicates assumed to be normal) into S, letting S be NormComp, but with all predicates X becoming ~ab(X).
+\\Append3: appends SD (list of first-order formula), S (normal predicates) and OBS (the observed (ground) facts) into Theory (that which is actually going to be tested, SD ∪ OBS ∪ {¬Ab(c) | c ∈ CS}, needed to be proven inconsistent if CS is going to be a valid conflict set).
+\\Conjunction: turns every element of Theory into conjunctions. These conjunctions are F (the formula that needs to be tested for inconsistency).
+\\Ground: constructs the ground formula that needs to be proven if it’s inconsistent. It establishes all logical symbols in the new formula F2 using all the logic rules in order and instantiates the existential and global variables using COMP (the set of all components).
+\\Break: stopping the prolog stack here so no backtracking will be done.
+\\Prove/1: Tries to establish the truth of the negated F2 formula and keeps backtracking until some solution is found.
+\\Prove/2: Finds the proof established in the statement above and puts the proof into Proof.
+\\Flatten: Breaks down the structure of the proof into its elements into FlatProof.
+\\Include: filters the abnormal elements from the FlatProof and puts them into Abs.
+\\Maplist: removes the ab() predicate from each component and puts them into CompProof.
+\\List-to-set: turns CompProof into CompSorted by turning the list(CompProof) into a set (CompSorted) that is sorted (which is not necessary) but which does not contain any duplicate elements.
+\\Subtract: removes any elements that were already considered abnormal from CompSorted and puts them in the final result of the function: CS.
+\\Break: another break to prevent prolog from backtracking after a result has been found.
+\\ \\In conclusion, tp determines the conflict set for a certain system with certain observations done on it and with certain assumptions on parts of the system.
+\newpage
\subsubsection{Task 13: Define your data structure}
-Can be found in \textit{./src/hs.pl} or in Listing~\ref{hs}.
+We use the nodes and leaves for our data structure. A node contains two lists. The first one contains a list of edge labels. The second one contains a list of new nodes or leaves. Both lists in the node predicate need to have the same size, since each edge label corresponds to a branch.
+\\ \\Good examples:
+\\Tree 1: node([a,b,],[leaf,leaf]).
+\\Tree 2: node([a,b],[node([c,d],[leaf,leaf]),leaf]).
+\\Wrong examples:
+\\Tree 3: node([a,b],[node([c,a],[leaf,leaf]),leaf]).
+\\Tree 4: node([a,b,c],[node([b,c],[leaf,leaf]),leaf]).
+\\ \\Tree 3 has a duplicate edge label in a path from root to leaf and thus is an incorrect hitting-set tree. Tree 4 is missing an entire branch for the edge label in the root.
+\\ \\Our isHittingSetTree(Tree) can be found in \textit{./src/hs.pl} or in Listing~\ref{hs}.
\begin{figure}[H]
- \caption{Examples of good hitting set trees}
+ \caption{Tree 1 and Tree 2}
\begin{tikzpicture} [grow=down]
\node[bag] {\{$a, b\}$}
child {
\end{figure}
\begin{figure}[H]
- \caption{Examples of bad hitting set trees due to duplicate edge labels}
+ \caption{Tree 3 and Tree 4}
\begin{tikzpicture} [grow=down]
\node[bag] {\{$a, b\}$}
child {
node[right] {$b$}
};
\end{tikzpicture}
+\begin{tikzpicture} [grow=down]
+ \node[bag] {\{$a, b,c\}$}
+ child {
+ node[bag] {$\{b, c\}$}
+ child {
+ node[end, label=below:$\checkmark$]{}
+ edge from parent
+ node[left] {$b$}
+ }
+ child {
+ node[end, label=below:$\checkmark$]{}
+ edge from parent
+ node[left] {$c$}
+ }
+ edge from parent
+ node[left] {$a$}
+ }
+ child {
+ node[end, label=below:$\checkmark$]{}
+ edge from parent
+ node[right] {$b$}
+ };
+ \end{tikzpicture}
\end{figure}
+\newpage
\subsubsection{Task 14: Implementation}
-Can be found in \textit{./src/task14part1.pl} or in Listing~\ref{task14part1}.
-Can be found in \textit{./src/task14part2.pl} or in Listing~\ref{task14part2}.
+How we generate hitting-set trees can be found in \textit{./src/task14part1.pl} or in Listing~\ref{task14part1}.
+\\How we extract diagnoses and get the subset minimal diagnoses can be found in \textit{./src/task14part2.pl} or in Listing~\ref{task14part2}.
+\\Problem 1:
+\\Hitting-set tree = node([a1], [node([a2], [leaf])]),
+\\Diagnoses = [[a1, a2]]
+\\Smallest Diagnoses = [[a1, a2]]
+\\ \\Problem 2:
+\\HS = node([a1, a2], [leaf, leaf]),
+\\DIAG = [[a1], [a2]]
+\\MIN = [[a1], [a2]]
+\\ \\Problem 3:
+\\HS = node([a1, o1, a2], [node([a2, o1], [leaf, leaf]), leaf, node([a1, o1], [leaf, leaf])]),
+\\DIAG = [[a1, a2], [a1, o1], [o1], [a2, a1], [a2, o1]],
+\\MIN = [[o1]]
+\\ \\Fulladder:
+\\HS = node([a1, x1, a2, r1, x2], [node([a2, x2, x1], [node([x1, x2], [leaf, leaf]), node([a2, r1, x1], [leaf, leaf, leaf]), leaf]), leaf, node([a1, x1, x2], [node([x1, x2], [leaf, leaf]), leaf, leaf]), node([a1, x1, a2|...], [node([a2|...], [node(..., ...)|...]), leaf, node(..., ...)|...]), node([a1, x1|...], [node([...|...], [...|...]), leaf|...])]),
+\\DIAG = [[a1, a2, x1], [a1, a2, x2], [a1, x2, a2], [a1, x2, r1], [a1, x2, x1], [a1, x1], [x1], [a2|...], [...|...]|...],
+\\MIN = [[x1]]
+\\ \\We had problems implementing how we can get subset-minimal subsets from all possible diagnoses, so we just tried to find the smallest diagnoses as another challenge. All our results are correct, since they correspond to our calculations done by hand or to the answers on the slides. A big problem we had was how to generate conflict set using tp. With some help of the internet, we found the prolog if-then-else construction, which is nice, but doesn't feel like real logic programming. Thus this is a point where improvement is possible (be it maybe not an optimalization). We think we lost track of the getting subset-minimal subsets when we first made the function that extracts all possible diagnoses, maybe we had to get those while running through the hitting set tree. Our code looks very efficient on the outside, at least to us, but when we were tracing calls we found alot of repetitions sometimes, so maybe break statements to reduce backtracking would be a nice improvement in some places. And of course, other improvements for, for example pruning the hitting-set tree, can be implemented.
\ No newline at end of file
repositories / ker1415-1.git / blobdiff