Finde ein lokales Minimum in einem 2-D-Array [duplizieren]

Das gleiche Problem wird in der Web-Version des Buches Algorithmen von Robert Sedgewick und Kevin Wayne erwähnt. (Siehe Abschnitt "Creative-Probleme", Problem 19) .

Der Hinweis auf das Problem, das der Autor in diesem Link gegeben hat, lautet:

Finde das Minimum in Zeile N / 2, überprüfe die Nachbarn p und q in der Spalte, wenn p oder q kleiner ist, dann wiederhole in dieser Hälfte.

Ein besserer Ansatz wäre: Finde das Minimum in der Zeile N / 2, überprüfe alle Einträge in der Spalte, wenn wir einen kleineren Eintrag in der Spalte bekommen, dann wiederhole in der Zeile, wo der kleinere Spalteneintrag gehört.

z. Für das Array darunter ist N = 5:

Schritt 1: Die mittlere Zeile ist [ 4 5 6 -1 77 ]. dh. Zeilennummer 3.

Schritt 2: Der Mindesteintrag in der aktuellen Zeile ist -1 .

Schritt 3: Spaltennachbarn für den Mindesteintrag (zB -1 ) sind 5 und -2 . -2 ist der minimale Nachbar. Es ist in der 4. Reihe.

Fahren Sie mit den Schritten 2-3 fort, bis wir das lokale Min erhalten.

BEARBEITEN:

Zum Beispiel im Kommentar von @anuja erwähnt (das Hauptproblem ist für n-by-n-Array. Dieser Eingang ist 3-by-4-Array, aber wir können damit arbeiten) :

Schritt 1: Die mittlere Zeile ist [5 1 6 -1] . dh. Zeilennummer 2.

Schritt 2: Der Mindesteintrag in der aktuellen Zeile ist -1 .

Schritt 3: Spaltennachbarn für den Mindesteintrag (zB -1 ) sind 4 und -2 . -2 ist der minimale Spaltennachbarn. Es ist in der 3. Reihe.

Iterieren zu Schritt 2: -2 ist am kleinsten in seiner Reihe und am kleinsten unter seinen Spaltennachbarn. Also enden wir mit -2 als Ausgabe für das lokale Minimum.

Aktualisieren : Diese Antwort geht davon aus, dass Kanten keine lokalen Minima sind, da sie von den vier Vergleichen in der ursprünglichen Problembeschreibung nicht als solche definiert sind. In diesem Fall ist diese Antwort richtig (es ist nicht möglich). Wenn Sie die Frage neu definieren, dass Kanten lokale Minima sein können, dann enthält jede Matrix mindestens ein lokales Minimum - und Sie können daher einen "Teile-und-herrsche" -Ansatz verwenden.

Wenn Kantenzellen nicht lokale Minima sein können:

Es gibt keine Lösung für die gestellte Frage. Ein N-mal-N-Array braucht nur O (N ^ 2), um die Elemente zu lesen. Da es irgendwo in der Matrix ein einzelnes lokales Minimum geben könnte, ist dies nachweislich notwendig.

Wenn Sie nach einem O (N ^ 2) -Algorithmus fragen wollen, dann braucht man nicht einfach jedes Element zu durchlaufen und es mit seinen 4 Nachbarn zu vergleichen, es dauert O (N ^ 2).

Entweder hast du die Interviewfrage falsch verstanden (und da war mehr dran), oder das ist nur eine Bagatellübung.

Beweis :

Diese Matrix hat genau ein lokales Minimum (M [x, y]) und ihre Position ist unabhängig von den Werten in den anderen Zellen. Daher stellen die anderen Zellen keine Informationen über ihre Position bereit, und daher ist es unmöglich, ein System zu finden, das besser als erwartet (N ^ 2/2) durchsuchte Zellen = O (N ^ 2).

(Mit anderen Worten, Sie können auch eine nahe Nullmatrix M [i, j] = 0 suchen, mit Ausnahme von M [x, y] = -1 für die Minima.)

Dieser Beweis hängt davon ab, dass man in Schritt 1 eine Matrix ohne lokale Minima konstruieren kann. Wenn Randzellen mögliche lokale Minima sind, muss jede Matrix eine haben, und dieser Beweis gilt nicht mehr.

Besuche eine zufällige Zelle. Wenn einer der vier Nachbarn einen kleineren Wert hat: Gehe zu dieser Zelle. Wenn keiner der Nachbarn kleiner ist, sind Sie in einem lokalen Minimum. Es wird etwas schwieriger Schleifen zu vermeiden, wenn Zellen mit gleichen Werten möglich sind.

Aktualisierung:

Anstatt einen Nachbarn zu besuchen, könnten wir den kleinsten Nachbarn auswählen.

Die schwierigste Topologie scheint der Fall von zwei "konzentrischen" Spiralen zu sein, von denen eine als spiralförmiger Deich funktioniert. Das würde im schlimmsten Fall immer noch etwa N / 2 Schritte dauern. (mit N = Anzahl der Zellen.)