helpers.tex 17.4 KB
Newer Older
Michael Keller's avatar
Michael Keller committed
1
2
3
4
\chapter{Helpful Statements}

\section{Growing solutions}

Michael Keller's avatar
Michael Keller committed
5
6
7
8
9
10
11
12
13
14
We have seen that the general problem is
NP complete. However, small problems can
still be computed by simply testing out
all possible solutions. We aim to demonstrate
that we can build solutions for larger fields
with the same score to field size ratio. These
solutions may not be optimal, but in some
situations may lead to good quality results quickly.

For the sake of a clearer presentation
Michael Keller's avatar
Michael Keller committed
15
we demonstrate a method that stretches the
Michael Keller's avatar
Michael Keller committed
16
17
18
19
20
21
22
23
24
25
26
27
solution by the same factor in both the $x$
and $y$ direction. Consider an algorithm
that is given a small optimal solution $sol$
of size $X \times Y$ that we would like to
stretch by an odd factor of $f$. We propose
the following method for generating
a larger solution $sol'$. We use $0$ indexing
for cleaner formulas:
\begin{align*}
    sol'_{i, j} &= sol_{a, b} & & i \in \{0, \dots, f \cdot (X-1)\} & j \in \{0, \dots, f \cdot (Y-1)\}
\end{align*}
\begin{displaymath}
Michael Keller's avatar
Michael Keller committed
28
    f \in \{ 2i + 1 \ | \ i \in \N \}
Michael Keller's avatar
Michael Keller committed
29
30
\end{displaymath}
\begin{displaymath}
Michael Keller's avatar
Michael Keller committed
31
    a = \lfloor i / f \rfloor + ((i + \lfloor i / f \rfloor) \text{ mod } 2) \quad \quad  b = \lfloor j / f \rfloor + ((j + \lfloor j / f \rfloor) \text{ mod } 2)
Michael Keller's avatar
Michael Keller committed
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
\end{displaymath}
which is a bit puzzling in its formal form.
The idea is that we want to multiply the
connections for all non-border pixels the
same amount of time. To achieve
this we try to reuse all of the good
intercrop relationships that are hopefully
present in the small field. We essentially
"ping pong" between all of the connections
$f$ times. Here is an example
for $f = 3$:
\begin{displaymath}
    \begin{bmatrix}
        1 & 2 & 3\\
        4 & 5 & 6\\
        7 & 8 & 9\\
    \end{bmatrix}
    \to
    \begin{bmatrix}
        1 & 2 & 1 & 2 & 3 & 2 & 3\\
        4 & 5 & 4 & 5 & 6 & 5 & 6\\
        1 & 2 & 1 & 2 & 3 & 2 & 3\\
        4 & 5 & 4 & 5 & 6 & 5 & 6\\
        7 & 8 & 7 & 8 & 9 & 8 & 9\\
        4 & 5 & 4 & 5 & 6 & 5 & 6\\
        7 & 8 & 7 & 8 & 9 & 8 & 9\\
    \end{bmatrix}
\end{displaymath}
Here the only non-border pixel is
pixel $5$. In the small solution
it is connected to all other
pixels exactly once. The reader
is invited to verify that pixel
$5$ in the grown solution is connected
to every other pixel exactly $f^2 = 9$
times.

Next we introduce the concept of relative
score. We define it as:
\begin{displaymath}
    \text{Relative Score} := \frac{\text{score}}{\text{maximum possible score}}
\end{displaymath}
where for the maximum possible score we use
the standard bound discussed in the section
on bounds. Hence if the score for our
small field is $s$ then the relative score
is:
\begin{displaymath}
    \frac{s}{8XY - 6X - 6Y + 4}
\end{displaymath}
Michael Keller's avatar
Michael Keller committed
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
We are now able to formulate the following theorem:
\begin{theorem}
    For any solution to a field there exists
    a factor by which we can scale up the field
    such that the relative score doesn't
    worsen and we only slightly
    violate the distribution constraint.
\end{theorem}
\begin{proof}
    We first bound the score for
    the grown field $s'$ from below:
    \begin{align*}
        s' 
        &\geq f^2 \cdot s - 2 \cdot 3 \cdot (f \cdot (X-1) + 1) - 2 \cdot 3 \cdot (f \cdot (Y-1) + 1) + 4\\
        &\geq f^2 \cdot s - 6 \cdot (f \cdot X - f + 1) - 6 \cdot (f \cdot Y - f + 1) + 4\\
        &\geq f^2 \cdot s - 6f \cdot X + 6f - 6 - 6f \cdot Y + 6f - 6 + 4\\
        &\geq f^2 \cdot s - 6f \cdot (X + Y - 2) -8\\
        &\geq f^2 \cdot s - 6f \cdot (X + Y)
    \end{align*}
    which means our new relative
    score can be bounded from below by:
    \begin{align*}
        &\frac{s'}{8 \cdot (f (X-1) + 1) \cdot (f (Y-1) + 1) - 6 \cdot (f (X-1) + 1) - 6 \cdot (f (Y-1) + 1) + 4}\\
        &= \frac{s'}{8 \cdot (f X - f + 1) \cdot (f Y - f + 1) - 6 \cdot (f X - f + 1) - 6 \cdot (f Y - f + 1) + 4}\\
        &= \frac{s'}{8f^2XY - 8f^2X - 8f^2Y + 2fX + 2fY - 4f + 8f^2}\\
        &= \frac{s'}{8f^2XY - 8f^2X - 8f^2Y + 2f \cdot (X + Y - 2) + 8f^2}\\
        &= \frac{s'}{8f^2 (XY - X - Y + 1) + 2f \cdot (X + Y - 2)}\\
        &\geq \frac{f^2 \cdot s - 6f \cdot (X + Y)}{8f^2 (XY - X - Y + 1) + 2f \cdot (X + Y - 2)}
    \end{align*}
    Which in turn allows us to find
    the following condition on $f$
    that guarantees our property:
    \begin{align*}
        \frac{s}{8XY - 6X - 6Y + 4} &\leq \frac{f^2 \cdot s - 6f \cdot (X + Y)}{8f^2 (XY - X - Y + 1) + 2f \cdot (X + Y - 2)}\\
        \frac{s}{8XY - 6X - 6Y + 4} &\leq \frac{f \cdot s - 6 \cdot (X + Y)}{8f (XY - X - Y + 1) + 2 \cdot (X + Y - 2)}\\
        - 2fsX - 2fsY + 4fs + 2s \cdot (X + Y - 2) &\leq - 6 \cdot (X + Y) \cdot (8XY - 6X - 6Y + 4)\\
        f \cdot 2s \cdot (X + Y - 2) - 2s \cdot (X + Y - 2) &\geq 6 \cdot (X + Y) \cdot (8XY - 6X - 6Y + 4)\\
        f &\geq \frac{6 \cdot (X + Y) \cdot (8XY - 6X - 6Y + 4)}{2s \cdot (X + Y - 2)} + 1
    \end{align*}
    which means if $f$ is at least what
    we bound it by here the relative score
    will not worsen.

    Lastly we consider that we slightly
    violate the distribution constraint
    for the crops that are planted
    in pixels on the border. Concretely
    every crop planted in a corner
    would need to be planted:
    \begin{displaymath}
        f^2 - (f-1)^2 = 2f - 1
    \end{displaymath}
    more times and crops planted
    in other places on the border would
    need to be planted $f$ more times.
    It should be stated that this would also
    require the grown field to be made even larger
    to accommodate the extra plants.

    It is worth noting however that the
    violation in the problem constraints
    is only linear, while in general the total
    number of planted pixels grows quadratically.
    Hence it is somewhat reasonable to ignore
    these violation on fields that are grown by very
    large factors in order to receive the guarantee
    of not worsening the relational score.
\end{proof}
Michael Keller's avatar
Michael Keller committed
150
151


152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
\section{Creating integer solutions from fractional solutions}

If we were able to take a field that can
contain multiple crops in a pixel and transform
it into a solution of the same quality
where every pixel contains exactly one crop, this
would enable us to try additional standard
optimization techniques. Of course the field
with fractional amounts of crops in pixels has
to meet the distribution requirement of the
pixel farming problem as well as only contain
positive or $0$ amounts of planted crop in a pixel.

\subsection{The standard method}

First we introduce a method that has good results
on large fields and requires no conditions of $R$.

\begin{theorem}
Michael Keller's avatar
worke    
Michael Keller committed
171
    \label{makeInt1}
172
173
174
175
176
177
178
179
180
181
    A fractional pixel farming solution can be
    transformed to a fractional solution with at least
    the same score where up to $4 \cdot \binom{C}{2}$
    pixels are still fractional. All other pixels
    contain only one crop.
\end{theorem}

\begin{proof}
    The key insight for this statement is that the
    score function changes linearly when swapping
Michael Keller's avatar
Michael Keller committed
182
    crops between non-neighboring pixels. Imagine
183
184
185
186
187
    two non-neighboring pixels that both contain
    the crops $c_1$ and $c_2$:
    \FloatBarrier
    \begin{figure}[h]
        \centering
Michael Keller's avatar
Michael Keller committed
188
        \begin{tikzpicture}[->,>=stealth',auto,node distance=3cm,thick,main node/.style={rectangle,draw,font=\sffamily\Large}]
189
190
191
192
193

            \node[main node] (1) {U};
            \node[main node] (2) [right of=1] {V};

            \path[every node/.style={font=\sffamily\small}]
Michael Keller's avatar
Michael Keller committed
194
            (1) edge[bend left] node [above] {$\lambda \cdot c_1$} (2)
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
            (2) edge[bend left] node [below] {$\lambda \cdot c_2$} (1);
        \end{tikzpicture}
    \end{figure}
    \FloatBarrier

    Because the neighborhoods remain constant, the shift
    function above changes the score linearly. This means
    there is always a direction in which we can swap
    crops without making the score worse. We perform the
    swap until at least one of the two pixels is unable
    to continue with swapping (i.e. runs out of crop
    to give to the other pixel). Therefore, every time we
    swap like this, we eliminate at least one crop
    from at least one fractional pixel.

Michael Keller's avatar
Michael Keller committed
210
211
212
    Next we argue that it is not necessary
    to swap between neighboring pixels for this result.
    Consider the field
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
    below. If we only swap between pixels that have
    the same color, then we never have to swap between
    neighboring pixels. It is always possible to color
    a rectangle field in this fashion with $4$ colors.
    \FloatBarrier
    \begin{figure}[h]
        \centering
            \begin{tikzpicture}[x=1cm]
                \foreach \x in {0,...,3} \foreach \y in {0,...,3}
                {
                    \pgfmathparse{mod(\x+\y,2) ? (mod(\x,2) ? "red" : "green") : (mod(\x,2) ? "blue" : "gray")}
                    \edef\colour{\pgfmathresult}
                    \path[fill=\colour] (\x,\y) rectangle ++ (1,1);
                }
                \draw (0,0)--(0,4)--(4,4)--(4,0)--cycle;
            \end{tikzpicture}
    \end{figure}
    \FloatBarrier

Michael Keller's avatar
Michael Keller committed
232
233
234
    Further, we argue that iterating this method terminates.
    While pixels of the same color that both contain the same two
    crops exist, we perform the swap as outlined above. Eventually,
235
236
237
238
239
240
241
242
243
244
    because we get rid of at least one fractional crop every time
    we swap, we must reach a state for a pixel color where
    no two pixels contain two of the same crop. Because
    only a finite amount of fractional crops can exist in
    a field, we must terminate in finite time.
    
    A state where no two pixels contain the same crop
    means in the worst case there are up to $\binom{C}{2}$
    pixels that each contain two crops. All other pixels
    must now contain exactly one unit of one crop. Because
Michael Keller's avatar
Michael Keller committed
245
    there are four colors among which we swap,
246
247
248
249
250
251
252
253
254
255
    in the worst case we end up with $4 \cdot \binom{C}{2}$
    pixels that are still fractional.
\end{proof}


\subsection{The advanced method}

There might be situations where up to $4 \cdot \binom{C}{2}$
still fractional pixels are unacceptable. This might be the
case in relatively small fields with relatively large amounts
Michael Keller's avatar
Michael Keller committed
256
of different crops. Here the following, slightly stronger,
257
statement with a condition on $R$ might be helpful:
258
259

\begin{theorem}
Michael Keller's avatar
worke    
Michael Keller committed
260
    \label{makeInt2}
261
262
263
264
265
266
267
268
269
270
271
272
273
    If every crop prefers all other crops over itself,
    then a fractional pixel farming solution can be
    transformed to a fractional solution with at least
    the same score where up to $\binom{C}{2}$
    pixels are still fractional. All other pixels
    contain only one crop.
\end{theorem}

\begin{proof}
    The general proof strategy is the same
    as with the previous theorem. The change we make is
    that we allow swapping of crops between neighboring
    pixels.
274

Michael Keller's avatar
Michael Keller committed
275
    We now need to know what condition must be
276
277
278
    met to ensure that swapping in either direction
    even among neighboring pixels is never detrimental.
    
Michael Keller's avatar
Michael Keller committed
279
    Let us consider the change in the score function $\Delta S$
Michael Keller's avatar
Michael Keller committed
280
    when swapping $c_\alpha, c_\beta \in \Cps$ between
Michael Keller's avatar
Michael Keller committed
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
    two neighboring pixels $u$ and $v$. Because the score change
    generated with the neighboring set $N(u) \cup N(v) \setminus \{u, v\}$
    (the gray pixels in the sketch below) is linear, as these
    neighboring pixels stay constant, we will ignore them for now.
    \FloatBarrier
    \begin{figure}[h]
        \centering
        \begin{tikzpicture}[->,>=stealth',auto,node distance=10mm,thick,main node/.style={rectangle,draw,font=\sffamily\Large}]

            \node[main node] (1) {U};
            \node[main node] (2) [right of=1] {V};
            \node[main node, fill=black!20,] (3) [below of=1] {N};
            \node[main node, fill=black!20,] (4) [right of=3] {N};
            \node[main node, fill=black!20,] (5) [right of=4] {N};
            \node[main node, fill=black!20,] (6) [above of=5] {N};
            \node[main node, fill=black!20,] (7) [above of=6] {N};
            \node[main node, fill=black!20,] (8) [left of=7] {N};
            \node[main node, fill=black!20,] (9) [left of=8] {N};
            \node[main node, fill=black!20,] (10) [left of=9] {N};
            \node[main node, fill=black!20,] (11) [below of=10] {N};
            \node[main node, fill=black!20,] (12) [below of=11] {N};

Michael Keller's avatar
Michael Keller committed
303
304
            \path[every node/.style={font=\sffamily\small}]
            (1) edge[bend left] node [above] {$c_\alpha$} (2)
Michael Keller's avatar
Michael Keller committed
305
306
307
308
309
            (2) edge[bend left] node [below] {$c_\beta$} (1);
        \end{tikzpicture}
    \end{figure}
    \FloatBarrier
    The interesting score change is the following quadratic one
Michael Keller's avatar
Michael Keller committed
310
311
312
313
314
    between the pixels $u$ and $v$. Here $p_c$ denotes
    the amount of crop $c$ pixel $p$ contains before
    the swap. $p_c'$ is defined analogously for after
    the swap.

Michael Keller's avatar
Michael Keller committed
315
    \begin{align*}
Michael Keller's avatar
Michael Keller committed
316
317
318
319
320
321
322
323
324
325
326
327
328
        &\sum_{c_i \in \Cps} \sum_{c_j \in \Cps} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &=  \sum_{c_i \in \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &+  \sum_{c_i \in \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &+  \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &+  \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
Michael Keller's avatar
Michael Keller committed
329
    \end{align*}
Michael Keller's avatar
Michael Keller committed
330
    We can now utilize that:
Michael Keller's avatar
Michael Keller committed
331
    \begin{align*}
Michael Keller's avatar
Michael Keller committed
332
333
        u'_\alpha &= u_\alpha - \lambda & v'_\alpha &= v_\alpha + \lambda\\
        u'_\beta &= u_\beta + \lambda & v'_\beta &= v_\beta - \lambda\\
Michael Keller's avatar
Michael Keller committed
334
    \end{align*}
Michael Keller's avatar
Michael Keller committed
335
    which gives us:
Michael Keller's avatar
Michael Keller committed
336
    \begin{align*}
Michael Keller's avatar
Michael Keller committed
337
338
339
340
341
342
343
344
345
346
347
348
349
        &\sum_{c_i \in \Cps} \sum_{c_j \in \Cps} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &=  \sum_{c_i \in \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &+  \sum_{c_i \in \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v_{j} - u_i \cdot v_{j})\\
        &+  \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u_i \cdot v'_{j} - u_i \cdot v_{j})\\
        &+  \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u_i \cdot v_{j} - u_i \cdot v_{j})
Michael Keller's avatar
Michael Keller committed
350
    \end{align*}
Michael Keller's avatar
Michael Keller committed
351
    where the last term is simply $0$ and the second
Michael Keller's avatar
Michael Keller committed
352
353
    and third terms are linear functions in $\lambda$.
    We again focus only on the quadratic term:
Michael Keller's avatar
Michael Keller committed
354
    \begin{align*}
Michael Keller's avatar
Michael Keller committed
355
356
357
358
359
360
361
362
363
364
365
            &\sum_{c_i \in \{c_\alpha, c_\beta \}}
            \sum_{c_j \in \{c_\alpha, c_\beta \}}
            R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\
            &= R(c_\alpha, c_\alpha) \cdot (u'_\alpha \cdot v'_{\alpha} - u_\alpha \cdot v_{\alpha})\\
            &+ R(c_\alpha, c_\beta) \cdot (u'_\alpha \cdot v'_{\beta} - u_\alpha \cdot v_{\beta})\\
            &+ R(c_\beta, c_\alpha) \cdot (u'_\beta \cdot v'_{\alpha} - u_\beta \cdot v_{\alpha})\\
            &+ R(c_\beta, c_\beta) \cdot (u'_\beta \cdot v'_{\beta} - u_\beta \cdot v_{\beta})\\
            &= R(c_\alpha, c_\alpha) \cdot ((u_\alpha - \lambda) \cdot (v_\alpha + \lambda)- u_\alpha \cdot v_{\alpha})\\
            &+ R(c_\alpha, c_\beta) \cdot ((u_\alpha - \lambda) \cdot (v_\beta - \lambda) - u_\alpha \cdot v_{\beta})\\
            &+ R(c_\beta, c_\alpha) \cdot ((u_\beta + \lambda) \cdot (v_\alpha + \lambda) - u_\beta \cdot v_{\alpha})\\
            &+ R(c_\beta, c_\beta) \cdot ((u_\beta + \lambda) \cdot (v_\beta - \lambda) - u_\beta \cdot v_{\beta})\\
Michael Keller's avatar
.    
Michael Keller committed
366
            &= R(c_\alpha, c_\alpha) \cdot (u_\alpha \cdot \lambda - v_\alpha \cdot \lambda - \lambda^2)\\
Michael Keller's avatar
.    
Michael Keller committed
367
            &- R(c_\alpha, c_\beta) \cdot (u_\alpha \cdot \lambda + v_\beta \cdot \lambda - \lambda^2)\\
Michael Keller's avatar
.    
Michael Keller committed
368
            &+ R(c_\beta, c_\alpha) \cdot (u_\beta \cdot \lambda + v_\alpha \cdot \lambda + \lambda^2)\\
Michael Keller's avatar
.    
Michael Keller committed
369
370
371
372
373
374
            &- R(c_\beta, c_\beta) \cdot (u_\beta \cdot \lambda - v_\beta \cdot \lambda + \lambda^2)\\
            &= \lambda^2 \cdot \left ( R(c_\alpha, c_\beta) + R(c_\beta, c_\alpha) - R(c_\alpha, c_\alpha) - R(c_\beta, c_\beta) \right )\\
            &+ \lambda \cdot (R(c_\alpha, c_\alpha) - R(c_\alpha, c_\beta)) \cdot u_\alpha\\
            &+ \lambda \cdot (R(c_\beta, c_\alpha) - R(c_\beta, c_\beta)) \cdot u_\beta\\
            &+ \lambda \cdot (R(c_\beta, c_\alpha) - R(c_\alpha, c_\alpha)) \cdot v_\alpha\\
            &+ \lambda \cdot (R(c_\beta, c_\beta) - R(c_\alpha, c_\beta)) \cdot v_\beta
Michael Keller's avatar
Michael Keller committed
375
    \end{align*}
Michael Keller's avatar
Michael Keller committed
376
    Of special note here is the quadratic term.
Michael Keller's avatar
Michael Keller committed
377
    If every crop likes all the other crops
Michael Keller's avatar
Michael Keller committed
378
379
380
381
382
383
384
    at least as much as it likes itself,
    then the quadratic term is positive. The quadratic
    term being positive means we can always swap
    in at least one direction without
    the score getting worse. The optimal swap
    direction is determined by all of the linear
    functions in $\lambda$ we put to the side
Michael Keller's avatar
Michael Keller committed
385
    throughout this proof. Therefore,
Michael Keller's avatar
Michael Keller committed
386
387
388
389
390
391
392
393
    a relationship function $R$ fulfilling
    $R(c_i, c_j) \geq R(c_i, c_i)$ ensures there is
    always a good way to swap crops among
    neighboring pixels.

    Being allowed to swap even amongst neighboring
    pixels allows us to disregard the pattern
    structure we had for the standard swapping method
Michael Keller's avatar
Michael Keller committed
394
395
396
397
    and we can, by the same reasoning, conclude
    that this new method has
    at most $\binom{C}{2}$ still fractional pixels
    after terminating.
398
\end{proof}