problem-statement.tex 2.79 KB
Newer Older
Michael Keller's avatar
Michael Keller committed
1
2
\chapter{Problem Statement}

Michael Keller's avatar
Michael Keller committed
3
4
\section{Integer Version}

Michael Keller's avatar
Michael Keller committed
5
We are given four inputs:
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
18
19
    contain a certain crop. $D$ should satisfy
    $D(c) \cdot X \cdot Y \in \N \quad \forall c \in \Cps$.
Michael Keller's avatar
Michael Keller committed
20
\end{enumerate}
Michael Keller's avatar
Michael Keller committed
21
Further let us define a neighborhood function that gives
Michael Keller's avatar
Michael Keller committed
22
us all the neighboring pixels of a given pixel:
Michael Keller's avatar
Michael Keller committed
23
\begin{displaymath}
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
25
\end{displaymath}
Michael Keller's avatar
Michael Keller committed
26
27
and we are looking for a matrix $F \in \Cps^{X \times Y}$
that maximizes the following score function:
Michael Keller's avatar
Michael Keller committed
28
\begin{displaymath}
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
30
31
32
33
\end{displaymath}
where we also fulfill the distribution constraint:
\begin{align*}
    I((i, j), c) &= \begin{cases}
Michael Keller's avatar
Michael Keller committed
34
        1 & F_{(i, j)} = c\\
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
38
39
40
41
\end{align*}

\section{Fractional Version}

Michael Keller's avatar
Michael Keller committed
42
43
We define the fractional version of pixel farming
analogously to the integer version
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
48
crop, but any combination of crops. To this end,
Michael Keller's avatar
Michael Keller committed
49
we introduce $C$ variables for every pixel to denote
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
53
54

We stress that we are interested in this version
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
67
\end{align*}