Teilmatrix suchen

[mkla]

Sorry, hab keinen besseren Titel gefunden!

Aalso ich hab folgendes Problem und zwar hab ich eine quadratische Matrix mit 0 und 1 gefüllt z.B.:
1 0 0 1 0 1
0 1 0 1 1 1
1 0 1 1 1 1
1 1 1 1 1 0
0 1 1 1 1 1
0 1 0 1 1 0
... und soll davon die größte Teilmatrix finden, die nur mit 1 gefüllt ist. Also in diesem Beispiel begint sie an der Position 2, 2 und ist 3 Teile lang. Das soll ausgegeben werden.

Wir haben zur Realisierung einen Tipp bekommen und zwar sollen wir eine Hilfsmatrix erstellen, die die Länge immer gleich mitzählt. In diesem Beispiel würde das so aussehen:
1 0 0 1 0 1
0 1 0 2 2 1
1 0 3 2 1 1
1 2 2 2 1 0
0 1 1 2 1 1
0 1 0 1 1 0
.. und die 3 zeigt mir dann Position und Länge an.

Ich habe jetzt aber ein Problem mit der Belegung des zweiten Arrays ... nämlich eine Endlosschleife und ich finde einfach nicht, wo der Fehler ist. Vielleicht kann mir dabei jemand helfen?? (Hab das zweite Array b[][] übrigens immer mit 0 vorbelegt)
Mein Code für das Belegen der b-Matrix sieht folgendermaßen aus:

	for (int i = b.length - 2; i > 0; i--) {
		for (int j = b[i].length - 2; j > 0; j--) {
			if (a[i][j] == 1 && b[i+1][j] == 1 && b[i][j+1] == 1 && b[i+1][j+1] == 1) {
				b[i][j] = b[i-1][j-1] + 1;
			}
			else {
				b[i][j] = a[i][j];
			}
		}
	}

.. tja? ich hab einfach keinen plan mehr, sitz jetzt schon 2 stunden ..

 

[XHelp]

Wie deine Hilfmatrix zustande kommt ist mir völlig rätselhaft...

Muss dass besonders effizient sein? Die einfachste Lösung wäre wohl alle Möglichkeiten durchzugehen. Bei dieser Matrix wärst du (soweit ich mich nicht verreichnet habe) bei 441 Möglichkeiten, wobei du durch geschickte Abbruchbedingungen auch diese Anzahl reduzieren kannst

 

[SlaterB]

bei dem Code ist meiner Ansicht nach keine Endlosschleife möglich, baue Ausgaben ein, welches i und welches j gerade bearbeitet wird,
kommen da unendlich viele?

die Hilfsmatrix ist ziemlich geschickt, das solltest du nutzen, nur ist der Code dazu noch nicht allzu richtig:
> b[j] = b[i-1][j-1] + 1;
was hat dann auf einmal i-1 damit zu tun? gäbe ne Exception wenn du in Zeile 0 bist (was bisher unverständlicherweise ausgeschlossen ist),
nein, es ist allein interessant was weiter rechts und unten los ist, also maximal +1

> if (.. b[i+1][j] == 1 ..
nicht nur die 1 testen, wenn rechts und unten 2 steht dann kommt ins aktuelle Feld eine 3,
vergleiche lediglich, ob das Feld rechts + das unten gleich sind, welche Zahl ist egal,
selbst bei rechts + unten gleich Zahl 0 wäre 0+1 = 1 der richtige Wert fürs aktuelle Feld


poste am besten ein vollständiges Programm auch mit Deklaration des Arrays welches du verwendest,
zu Beginn mit 3x3 oder 4x4 anfangen damit es nicht zu unübersichtlich

 

[FArt]

Kadane ist ein gutes Stichwort.
Find The Sub-matrix With The Maximum Sum | Xi's Note
techInterview Discussion - Kadane's 2D
Maximum subarray sum problem - Algorithms

 

[SlaterB]

für generelle Ideen ist das ein Stichwort, für dieses Problem aber zu allgemein, zu komplex,
der Algorithmus ist doch schon fertig, geht dann bei diesem einfacheren Problem auch in O(n^2)

 

[mkla]

danke, die matrix stellt er jetzt richtig auf! puh!
bin mir nur grad nicht sicher wie ich am besten das maximum dieser zweiten matrix suche ... muss ich da wirklich immer jeden wert mit allen drei nachbarwerten (rechts und unten) vergleichen??

 

[XHelp]

Wie sieht denn deine Hilfsmatrix aus?
In deinem Beispiel müsste eine 2x5 Matrix rauskommen.

 

[SlaterB]

mit den Nachbarn musst du jetzt nichts mehr vergleichen, einfach die komplette Matrix durchgehen und den höchsten Wert finden,
wann immer ein Kandidat kommt, dann diesen zusammen mit Position merken, danach weiter durchlaufen bis eben eine größere Zahl kommt und diese dann merken,

das ganze könnte auch schon während des Aufbaus der zweiten Matrix geschehen

@XHelp
nur quadratische, sonst geht die Suche nicht bzw. die findet nur diese
die Hilfsmatrix ist ganz oben als zweite gepostet, die mit der 3 drin, das ist die gesuchte Position

 

[mkla]

lol stimmt, ja ist klar, dass ich da nicht selbst draufgekommen bin ... ich seh die algorithmen vor lauter java nicht mehr ) haha.

ich hab jetzt nur einen fehler bei der Ausgabe und versteh nicht so ganz weshalb.
und zwar wenn ich eine 4x4 Matrix eingebe z.B.
1 0 0 1
1 1 1 0
0 1 1 0
1 0 1 1
gibt er richtig die Position 1 1 und die Länge 2 aus.
Bei meinem Beispiel von ganz oben gibt er richtig die Länge 3 aus , aber Position 3 2 (??) wieso??

Das ist mein Befehl zum Suchen:

			if (b[i][j] > b[pos_i][pos_j]) {
			pos_i = i;
			pos_j = j;
			max = b[i][j];
			}

pos_i und pos_j sind die Positionen, max ist der Wert der Länge .. ähhh, ja?

 

[mkla]

hab jetzt noch mehrere Sachen ausprobiert ... und es stimmt wirklich überall bis auf die eine Matrix?? Ich glaub ich poste mal den kompletten Code g

/***********************************************************************
* Lisa Leitner		Matrikelnummer: 1020143                            *
*                                                                      *
* Dieses Programm sortiert ein String-Array lexikographisch aufsteigend*
* Dafür wird wiederholt das letzte Wort gesucht und nach hinten        *
* getauscht.                                                           *
*                                                                      *
* Die zu sortierenden Wörter sollen als Kommandozeilenargument         *
* eingegeben werden (also z.B. java Bsp14 Proseminar Blatt07 Banane)   *
*                                                                      *
* Fehlt die Eingabe, soll das Programm keinen Laufzeitfehler erzeugen. *
***********************************************************************/

public class Bsp15 {

	public static void main(String[] args) {
	int n;
	int max = 0;
	int pos_i = 0;
	int pos_j = 0;
	
	System.out.println("Geben Sie die Groesse n der n*n-Matrix ein: ");
	n = SavitchIn.readLineInt();
	
	// Anlegen der beiden Arrays, b ist um eins größer, damit die 0-Werte für die nicht vorhanden Nachbarn verwendet werden können
	int a[][] = new int[n][n];
	int b[][] = new int[n+1][n+1];
	
	System.out.println("Geben Sie " + n*n + " Zahlen ein, immer entweder 0 oder 1:");
	// Befüllen der Matrix a und b zu Beginn nur mit 0en
	b[0][0] = 0;
	for (int i = 0; i < a.length; i++) {
		for (int j = 0; j < a[i].length; j++) {
			a[i][j] = SavitchIn.readInt();
			b[i+1][j+1] = 0;
		}
	}
	
	// richtiges Befüllen der Matrix b (nach dem Schema)
	/* weil von rechts unten befüllen Beginn bei b.length-2
	(die 0en die rechts und unterhalb stehen sollen ignoriert 
	werden, die brauchen ja nicht verändert werden */
	for (int i = b.length - 2; i >= 0; i--) {
		for (int j = b[i].length - 2; j >= 0; j--) {
			// wenn der Wert von a 1 ist (also zur Teilmatrix gehört) UND alle anderen Werte daneben auch zur Teilmatrix gehören (>1) dann soll die Länge der Teilmatrix um eins erhöht werden
			if (a[i][j] == 1 && b[i+1][j] > 0 && b[i][j+1] > 0 && b[i+1][j+1] > 0) {
				b[i][j] = b[i+1][j+1] + 1; // die Länge der alten Teilmatrix steht schräg rechts unten, weil quadratisch, wird um eins erhöht
			}
			else {
				b[i][j] = a[i][j]; // sonst übernimmt er den Wert aus der eingebene Matrix
			}
			// Vergleiche, welches die größte Zahl bisher ist und merke Position und Länge
			if (b[i][j] > b[pos_i][pos_j]) { 
			/* aber nur dann, wenn b[i][j] ECHT groesser ist als das alte gespeicherte, 
			sonst soll ja die zweite Position gemerkt werden, weil sie groesser ist 
			als die neue (abwärtszählende for-Schleife) */
			pos_i = i;
			pos_j = j;
			max = b[i][j];
			}
		}
	}
	
	// Ausgabe des Ergebnisses
	System.out.println("Laenge der Teilmatrix: " + max + " an der Stelle: " + pos_i + " " + pos_j);
	
	}
}

 

[XHelp]

@XHelp
nur quadratische, sonst geht die Suche nicht bzw. die findet nur diese
die Hilfsmatrix ist ganz oben als zweite gepostet, die mit der 3 drin, das ist die gesuchte Position

Ah... jetzt ergibt der Thread auch mehr Sinn für mich

 

[SlaterB]

kann ich spontan nicht erkennen, ein vollständiges Programm wäre hilfreich (edit: ist jetzt ja da, ich schaue)

ansonsten auch millimeter genau komplett selber herauszufinden,
baue einfach lauter System.out.println()-Meldungen ein,
schon erhälst du ein Log a la

untersuche Position 0,0 - Wert ist 1, vergleiche mit bisherigen Max 0 an Position -1,-1
nehme 1 von 0,0 als neues Maximum,
untersuche Position 1,0 - Wert ist 1, vergleiche mit bisherigen Max 1 an Position 0,0
untersuche Position 2,0 - Wert ist 1, vergleiche mit bisherigen Max 1 an Position 0,0
...
untersuche Position 2,2 - Wert ist 3, vergleiche mit bisherigen Max 2 an Position 4,1
...
...
...
Ende der Untersuchung, Max-Position ist 2,2 mit Wert 3

entweder ist aus dem Log schon alles ersichtlich, oder wenn es unbekannte Sprünge gibt dann schauen welcher Code dazwischen liegt und noch genauer, notfalls zwischen jeder einzelnen Code-Zeile, den Zustand ausgeben,

so ist Fehlersuche reine Fleißarbeit, fast ohne erforderliches Denken,
professioneller gehts mit Debugger-Tools

 

[mkla]

super tipp, den muss ich mir merken ..!
hab den fehler jetzt auch gefunden in meiner hilfsmatrix steht angeblich zweimal die drei oO
muss ich nochmal überprüfen vorher war das nicht so ...

 

[SlaterB]

was ist denn das für ein Programm, gibst du für jeden Test die 36 Zahlen neu ein?
dann wirst du noch nicht oft getestet haben..

die eine wahnsinnige einfache und gute Verbesserung:

		n = 6;
		int a[][] = { 
				{ 1, 0, 0, 1, 0, 1, }, 
				{ 0, 1, 0, 1, 1, 1, },
				{ 1, 0, 1, 1, 1, 1, }, 
				{ 1, 1, 1, 1, 1, 0, },
				{ 0, 1, 1, 1, 1, 1, }, 
				{ 0, 1, 0, 1, 1, 0, }, };

Benutzereingaben kannst du am Ende noch wieder einbauen..,

so, und das Problem ist schlicht, dass dein b nicht der Hilfsmatrix im ersten Posting entspricht, nie angeschaut?
Ausgabe z.B. mit

		System.out.println("b: ");
		for (int i = 0; i < b.length; i++) {
			for (int j = 0; j < b[i].length; j++) {
				System.out.print(b[i][j]+" ");
			}
			System.out.println();
		}

------

die Berechnung für b ist falsch, deshalb kommt folgende Matrix raus

b: 
1 0 0 1 0 1 0 
0 1 0 2 2 1 0 
1 0 3 2 1 1 0 
1 2 3 2 1 0 0 
0 1 1 2 1 1 0 
0 1 0 1 1 0 0 
0 0 0 0 0 0 0

du gehst diagonal, das ist schlecht, da war dein Code im ersten Posting noch näher dran, wichtig sind allein die beiden Felder rechts und unten,
schau dir nochmal die richtige Hilfs-Matrix an:

1 0 0 1 0 1
0 1 0 2 2 1
1 0 3 2 1 1
1 2 2 2 1 0
0 1 1 2 1 1
0 1 0 1 1 0

die 3 kommt weil weiter rechts und unten 2 steht, die 2 dort weil jeweils aus 1 erhöht,
ganz einfache Regel: "steht rechts x und unten x dann bin ich x+1"
ok, ob im eigenen Feld ne 1 steht ist auch wichtig, das hast du ja bereits
edit:
oh, meine Regel stimmt auch nicht, wenn rechts 2 steht und unten 1, dann kommt ja auch ne 2 hin,
also neue Regel: 'ich bin Minimum(unten, rechts) +1, wenn selber ne 1 in Originalmatrix',
versuche das zu programmieren oder ähnliches, bist du die richtige Hilfsmatrix b erhälst


und teste unbedingt mit weiteren Matrixen, z.B. mit höchste Teilmatrix in allen 4 Ecken, ob das jeweils gefunden wird

 

[mkla]

oh doch, habs schon einige male eingegeben, da traust du mir nicht viel zu *g*

bin auch schon draufgekommen ,dass der code für die matrix b falsch ist.
aber nach der regel "steht rechts x und unten x bin ich x+1" kommt doch auch nicht die selbe raus ... z.B. wenn rechts 2 und unten 1 steht, ist das feld doch immer noch 2 (in dem beispiel) und nicht was anderes ??

aah ich glaub ich verzweifel noch daran .. x)

 

[mkla]

soo mit der neuen regel funktionierts .. danke ^^ daran bin ich die ganze zeit gescheitert ach man *g* wie viele stunden man mit so kleinen fehlern verbringen kann ...

 

[Michael...]

Hier ist ein Denkfehler:

[JAVA=47]b[j] = b[i+1][j+1] + 1; // die Länge der alten Teilmatrix steht schräg rechts unten, weil quadratisch, wird um eins erhöht[/code]