problem-statement.tex 2.79 KB
 Michael Keller committed Apr 19, 2022 1 2 \chapter{Problem Statement}  Michael Keller committed May 11, 2022 3 4 \section{Integer Version}  Michael Keller committed May 15, 2022 5 We are given four inputs:  Michael Keller committed Apr 19, 2022 6 7 8 9 10 11 12 13 14 15 16 17 \begin{enumerate} \item The field dimensions, denoted as $X$ for the number of pixels on the x-axis and $Y$ correspondingly. Both $X, Y \in \N$. \item The types of crop we would like to plant. We let $C\in \N$ denote the number of different crop types we would like to plant and $\Cps := \{c_1, \cdots, c_{C}\}$ as the set of all crops. \item A function $R: \Cps^2 \to [-1, 1]$ that measures the synergy between two crops. The higher the value of $R(c_a, c_b)$, the more crop $c_a$ likes $c_b$. \item A probability distribution $D$ over our crops $\Cps$ that tells us how many pixels of the field should  Michael Keller committed Apr 19, 2022 18 19  contain a certain crop. $D$ should satisfy $D(c) \cdot X \cdot Y \in \N \quad \forall c \in \Cps$.  Michael Keller committed Apr 19, 2022 20 \end{enumerate}  Michael Keller committed Apr 19, 2022 21 Further let us define a neighborhood function that gives  Michael Keller committed May 15, 2022 22 us all the neighboring pixels of a given pixel:  Michael Keller committed Apr 19, 2022 23 \begin{displaymath}  Michael Keller committed May 11, 2022 24  N((x, y)) = \{(a, b) \in \N^2 \ | \ a < X \land b < Y \land \abs{a - x} \leq 1 \land \abs{b - y} \leq 1 \land (a, b) \neq (x, y) \}  Michael Keller committed Apr 19, 2022 25 \end{displaymath}  Michael Keller committed Apr 19, 2022 26 27 and we are looking for a matrix $F \in \Cps^{X \times Y}$ that maximizes the following score function:  Michael Keller committed Apr 19, 2022 28 \begin{displaymath}  Michael Keller committed May 11, 2022 29  S(F, R) = \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} \sum_{n \in N((i, j))} R(F_{(i, j)}, F_n)  Michael Keller committed Apr 19, 2022 30 31 32 33 \end{displaymath} where we also fulfill the distribution constraint: \begin{align*} I((i, j), c) &= \begin{cases}  Michael Keller committed May 11, 2022 34  1 & F_{(i, j)} = c\\  Michael Keller committed Apr 19, 2022 35 36 37  0 & otherwise. \end{cases}\\ \forall c \in \Cps : D(c) \cdot X \cdot Y &= \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} I((i, j), c)  Michael Keller committed May 11, 2022 38 39 40 41 \end{align*} \section{Fractional Version}  Michael Keller committed May 15, 2022 42 43 We define the fractional version of pixel farming analogously to the integer version  Michael Keller committed May 11, 2022 44 45 46 47 with the following exception: Instead of searching for a Field $F \in \Cps^{X \times Y}$, we search for an $F' \in \R_+^{C \times X \times Y}$. The idea is that every pixel can contain not only a single  Michael Keller committed May 15, 2022 48 crop, but any combination of crops. To this end,  Michael Keller committed May 11, 2022 49 we introduce $C$ variables for every pixel to denote  Michael Keller committed May 15, 2022 50 51 52 the amount of each crop a pixel contains. For example, a pixel could contain half of a carrot, a quarter of an onion, and a quarter of broccoli.  Michael Keller committed May 11, 2022 53 54  We stress that we are interested in this version  Michael Keller committed May 15, 2022 55 56 57 of the pixel farming problem not for its practical applications but rather because it enables us to utilize more traditional methods for exploring  Michael Keller committed May 11, 2022 58 59 60 61 62 63 64 65 66 large search spaces. We define an analogous score function: \begin{align*} S(F', R) &= \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} \sum_{n \in N((i, j))} \sum_{c_i \in \Cps} \sum_{c_j \in \Cps} R(c_i, c_j) \cdot F_{(i, j)}^{c_i} \cdot F_{n}^{c_j} \end{align*} and solutions must fulfill a similar distribution constraint: \begin{align*} \forall c \in \Cps : D(c) \cdot X \cdot Y &= \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} F_{(i, j)}^c  Michael Keller committed Apr 19, 2022 67 \end{align*}