Zij gegeven een graaf \(G\) bestaande uit een \(n\times n\) rooster, m.a.w. een graaf bestaande uit cellen \((i,j)\) met \(1\leq i,j \leq n\), waarbij een cel \((i,j)\) verbonden is met een cel \((k,l)\) als en slechts als \(|i-k|+|j-l|=1\). Elke cel \(v\) in \(G\) is gelabeld met een gehele waarde \(x_v\). Je mag veronderstellen dat de waarden die de cellen labelen, allemaal verschillend zijn. Een cel \(v\) van \(G\) is een lokaal minimum als het label \(x_v\) kleiner is dan het label \(x_w\) voor alle cellen \(w\) die met \(v\) verbonden zijn.
Ontwerp en implementeer een algoritme dat een lokaal minimum in \(G\) bepaalt door slechts \(O(n)\) cellen van \(G\) te bevragen. (Merk op dat \(G\) \(n^2\) cellen heeft.)
Hint: Probeer het \(n \times n\) probleem te herleiden naar een \(n/2 \times n/2\) probleem in \(O(n)\) tijd.
Schrijf een Python-functie vindminimum(matrix: list) die een lokaal minimum in een gegeven roostergraaf bepaalt.
De graaf wordt voorgesteld door een matrix, die als een lijst van lijsten voorgesteld is.
Bijvoorbeeld:
[[129, 175, 115, 31, 134, 4, 102],
[137, 70, 140, 142, 38, 154, 158],
[79, 173, 60, 141, 182, 69, 13],
[68, 48, 147, 99, 157, 24, 67],
[94, 0, 86, 76, 51, 191, 28],
[160, 177, 120, 183, 114, 36, 105],
[143, 33, 104, 167, 27, 159, 54]]
Deze matrix ziet er als volgt uit:
\[\begin{pmatrix} \color{red}{129} & 175 & 115 & \color{red}{31} & 134 & \color{red}{4} & 102 \\ 137 & \color{red}{70} & 140 & 142 & \color{red}{38} & 154 & 158 \\ 79 & 173 & \color{red}{60} & 141 & 182 & 69 & \color{red}{13} \\ 68 & 48 & 147 & 99 & 157 & \color{red}{24} & 67 \\ 94 & \color{red}{0} & 86 & 76 & \color{red}{51} & 191 & \color{red}{28} \\ 160 & 177 & 120 & 183 & 114 & \color{red}{36} & 105 \\ 143 & \color{red}{33} & 104 & 167 & \color{red}{27} & 159 & \color{red}{54} \end{pmatrix}\]De lokale minima zijn hier in het rood geplaatst.
>>> vindminimum([[129, 175, 115, 31, 134, 4, 102],[137, 70, 140, 142, 38, 154, 158],[79, 173, 60, 141, 182, 69, 13],[68, 48, 147, 99, 157, 24, 67],[94, 0, 86, 76, 51, 191, 28],[160, 177, 120, 183, 114, 36, 105],[143, 33, 104, 167, 27, 159, 54]])
70 # Alle andere lokale maxima worden in de testen ook geaccepteerd