From d07651b380b0fd0af59f9341442d3bb824e22e08 Mon Sep 17 00:00:00 2001 From: Mart Lubbers Date: Thu, 19 Jun 2014 21:47:46 +0200 Subject: [PATCH] Fixed the new algo, report almost finished --- LubbersReport.tex | 56 ++++++++++-- LubbersSolver.java | 214 ++++++++++++++++----------------------------- Makefile | 7 +- 3 files changed, 126 insertions(+), 151 deletions(-) diff --git a/LubbersReport.tex b/LubbersReport.tex index abda695..e175b99 100644 --- a/LubbersReport.tex +++ b/LubbersReport.tex @@ -2,9 +2,15 @@ \usepackage{listings} \usepackage[dvipdfm]{hyperref} +\usepackage{color} +\usepackage{amssymb} + +\definecolor{javared}{rgb}{0.6,0,0} +\definecolor{javagreen}{rgb}{0.25,0.5,0.35} +\definecolor{javapurple}{rgb}{0.5,0,0.35} \lstset{ - basicstyle=\footnotesize, + basicstyle=\scriptsize, breaklines=true, numbers=left, numberstyle=\tiny, @@ -46,10 +52,11 @@ all the compatibility values between pets and children is the maximum possible. \subsection{Brute Force} The first approach was to implement a brute force algorithm which calculates every possible combination of pets and children and then takes the one with the -highest value. This corresponds with the pseudocode specified in -Listing~\ref{lst:brute_force}. The algorithm, due to calculating all the values -has a minimal complexity of $n!$. This is because there are $n!$ permutations -possible for $n$ children. +highest value. This corresponds with the pseudocode specified together with a +rough estimate of the complexity in Listing~\ref{lst:brute_force}. The +algorithm, due to calculating all the values the algorithm has a complexity +within $\mathcal{O}(n!)$. +This is because there are $n!$ permutations possible for $n$ children. \begin{lstlisting}[ caption={Brute Force approach}, label={lst:brute_force}, @@ -60,10 +67,43 @@ c1 - put compatibility in list c1 - return maximum compatibility rating from list \end{lstlisting} - -\subsection{Improvements} +\subsection{Improved algorithm} +The improved algorithm makes use of the fact that some rows only have very few +positive compatibilities. If you handle the rows/columns in the order from +little to lots of entries with compatibilites $1$ then a greedy approach will +suffice. This corresponds with the pseudocode specified together with a rough +estimate of the complexity in Listing~\ref{lst:improved}. The algorithm has a +complexity lies in the $\mathcal{O}(nm)$ because the main loop repeats at +maximum $n$ or $m$ times and the searching within the loop has a complexity of +$n$ if the loop runs $m$ times and $m$ otherwise. +\begin{lstlisting}[ + caption={Improved approach}, + label={lst:improved}, + keywords={[3]while,create,put,return,find,remove} +] +n - create list result of length n and initialize with -1 +n+m - create list rows/columns that contain pairs of indices and sums of values +nlgn - sort the rows and columns list on ascending sum +(n+m)/2 - while there are still unused values in the lists +c1 - pick the lowest value from the lists +c2 - remove the value +max(n, m) - find the lowest value in the corresponding antagonist +c2 - remove the antagonist +c3 - put the row/column pair in the results list +c4 - return the results list +\end{lstlisting} \section{Conclusion} -\end{document} +\newpage +\section{Appendices} +\subsection{\textit{\href{http://www.java.com}{Java}} source} +\lstinputlisting[ + language=java, + keywordstyle=\color{javapurple}\bfseries, + stringstyle=\color{javared}, + commentstyle=\color{javagreen}, + stepnumber=2 +]{LubbersSolver.java} +\end{document} diff --git a/LubbersSolver.java b/LubbersSolver.java index a1b88a0..8a280b0 100755 --- a/LubbersSolver.java +++ b/LubbersSolver.java @@ -1,162 +1,94 @@ -import java.util.ArrayList; -import java.util.LinkedList; -import java.util.Collections; -import java.util.Random; -import java.util.Arrays; -import java.util.List; -import java.util.Comparator; import java.util.AbstractMap.SimpleEntry; +import java.util.Arrays; +import java.util.Collections; import java.util.Comparator; -import java.util.PriorityQueue; - +import java.util.LinkedList; /** - * Class that implements the pot problem solver. - * - * @author Mart Lubbers + * Class that implements the pet problem solver. + * + * @author Mart Lubbers, s4109503 */ public class LubbersSolver implements IPetproblemSolver { - - public class Tuple implements Comparable - { - public int k; - public int v; - - public Tuple(int k, int v) - { - this.k = k; - this.v = v; - } - - /** - * Overrides compareTo so that the priorityqueue is ordered ascending - * - * @param a the entry to compare with - * @return comparison value - */ - @Override - public int compareTo(Tuple a) - { - //note that the values are swapped, so that the sort will be reversed - return Integer.compare(a.v, this.v); - } - - @Override - public String toString() - { - return k + ": " + v; - } - } - @Override - public int[] solve(int n, int m, int[][] compatibility) - { + public int[] solve(int n, int m, int[][] compatibility) { + // Create initial result list of of length n and fill with -1 int[] result = new int[n]; - - // Set to -1 initially - for (int i = 0; i < result.length; i++) - result[i] = -1; - - // Sum rows and columns - PriorityQueue row_sums = new PriorityQueue(n); - PriorityQueue col_sums = new PriorityQueue(m); - - int[] running_row_sums = new int[n]; - int[] running_col_sums = new int[m]; - - // Sum - for (int j = 0; j < m; j++) - { - for (int i = 0; i < n; i++) - { - running_row_sums[i] += compatibility[i][j]; - running_col_sums[j] += compatibility[i][j]; + Arrays.fill(result, -1); + + // Create the lists that define the sums of the rows and columns + LinkedList> rows = new LinkedList>(); + LinkedList> cols = new LinkedList>(); + + // Calculate the sums + int[] col_sums = new int[m]; + for (int i = 0, sum = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + sum += compatibility[i][j]; + col_sums[j] += compatibility[i][j]; } + rows.add(new SimpleEntry(i, sum)); } - - // Add running sums to queues - for (int i = 0; i < running_row_sums.length; i++) - row_sums.add(new Tuple(i, running_row_sums[i])); - - for (int i = 0; i < running_col_sums.length; i++) - col_sums.add(new Tuple(i, running_col_sums[i])); - - - // Select smallest sum (in rows/cols) - // Get 1-indices for that sum's index - // Select smallest from those indices - while (!row_sums.isEmpty() && !col_sums.isEmpty()){ - Tuple lowestIndexRow = row_sums.peek(); - Tuple lowestIndexCol = col_sums.peek(); - - boolean useRow = false; - - if (lowestIndexRow.v < lowestIndexCol.v) - useRow = true; - - // Get 1-indices - if (useRow) - { - row_sums.remove(); - - // Get smallest - int smallestValue = Integer.MAX_VALUE; - Tuple smallestKey = null; - - for (Tuple e : col_sums) - { - if (e.v < smallestValue && compatibility[lowestIndexRow.k][e.k] == 1) - { - smallestKey = e; - smallestValue = e.v; + for (int i = 0; i < m; i++) { + cols.add(new SimpleEntry(i, col_sums[i])); + } + //Sort the lists so the rows and columns with the least amount of positive compatibilities + Comparator> comp = new Comparator>() { + @Override + public int compare(SimpleEntry a, SimpleEntry b) { + return a.getValue().compareTo(b.getValue()); + } + }; + Collections.sort(rows, comp); + Collections.sort(cols, comp); + + /* 1. Find the row or column with the lowest sum(least available matches) + * Because the rows and columns are sorted on value the first item is the lowest + * 2. Find the match with the lowest sum and still positive compatibility for that row or column + * 3. Select smallest from those indices + */ + SimpleEntry MINIMUM = new SimpleEntry(-1, Integer.MAX_VALUE); + while (!(rows.isEmpty() || cols.isEmpty())) { + //1. Find the row or column with the lowest sum(least available matches) + SimpleEntry row_l = rows.peekFirst(); + SimpleEntry col_l = cols.peekFirst(); + + //2. The row is the lowest + if (row_l.getValue() < col_l.getValue()) { + //Remove the current lowest row sum + rows.remove(row_l); + //3. Find smallest column that has compatibility 1 + SimpleEntry smallest = MINIMUM; + for (SimpleEntry e : cols) { + if (e.getValue() < smallest.getValue() && compatibility[row_l.getKey()][e.getKey()] == 1) { + smallest = e; } } - - // No candidates in this list, continue - if (smallestKey == null) + //No pets left that have a positive compatibility + if (smallest.getKey() == -1) { continue; - - int col_index = smallestKey.k; - col_sums.remove(smallestKey); - - result[lowestIndexRow.k] = col_index; - } - else - { - col_sums.remove(); - - // Get smallest - int smallestValue = Integer.MAX_VALUE; - Tuple smallestKey = null; - - for (Tuple e : row_sums) - { - if (e.v < smallestValue && compatibility[e.k][lowestIndexCol.k] == 1) - { - smallestKey = e; - smallestValue = e.v; + } + cols.remove(smallest); + result[row_l.getKey()] = smallest.getKey(); + //2. The column is the lowest + } else { + //Remove the current lowest column sum + cols.remove(col_l); + //3. Find smallest row that has compatibility 1 + SimpleEntry smallest = MINIMUM; + for (SimpleEntry e : rows) { + if (e.getValue() < smallest.getValue() && compatibility[e.getKey()][col_l.getKey()] == 1) { + smallest = e; } } - - // No candidates in this list, continue - if (smallestKey == null) + //No pets left that have a positive compatibility + if (smallest.getKey() == -1) { continue; - - int row_index = smallestKey.k; - row_sums.remove(smallestKey); - - result[row_index] = lowestIndexCol.k; + } + rows.remove(smallest); + result[smallest.getKey()] = col_l.getKey(); } } - - int score = 0; - - for (int i = 0; i < result.length; i++) - score += result[i] == -1 ? 0 : 1; - - System.out.println("Score: " + score); - return result; } - } diff --git a/Makefile b/Makefile index 974967e..1a7bbb2 100644 --- a/Makefile +++ b/Makefile @@ -10,5 +10,8 @@ test: javac -cp /usr/share/java/junit.jar:/usr/share/java/junit4.jar *.java java org.junit.runner.JUnitCore PetTest -clean: - rm -vf *.{class,aux,log,out,pdf,toc,dvi} +clean: cleanprime + rm -vf *.pdf + +cleanprime: + rm -vf *.{class,aux,log,out,toc,dvi} -- 2.20.1