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 klasse MijnRoosterZoeker die de interface RoosterZoeker1 implementeert.
Deze klasse moet een methode int zoek(Rooster rooster) implementeren die, een gegeven Rooster2 binnenkrijgt en een lokaal minimum teruggeeft.
De klasse Rooster bevat 3 methodes:
int get(x,y) geeft het element op rij x en kolom y van het gegeven rooster terug.int getbreedte() geeft de breedte van het rooster terug.int gethoogte() geeft de hoogte van het rooster terug.De graaf wordt voorgesteld door een matrix, bijvoorbeeld:
\[\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.