Matrix(Array) minimieren...

[l4mer]

Hi mates,

Ich benötige eine Methode, welche mir eine gegebene Matrix mittels dem "Matrix-Minimum-Verfahren" minimiert und ein Basislösung ausgibt. Einlesen der Daten sowie erstellen des Arrays aka der Matrix ist kein Problem. Habe bis jetzt eine Methode(Schleife) welche jeweils das Minimum in der Matrix sucht und mittels einfacher if-else Anweisung entweder eine Spalte oder eine Zeile löscht und anschließend den Inhalt in ein neues Array schreibt was entsprechend kleiner ist...funktioniert soweit auch alles und jetzt kommt meine Frage, welche bestimmt total doof klingt.
Wie übergebe ich jetzt der Schleife das kleinere Array um dieses nun wieder zu verkleinern? Da ich mich erst seit einem Jahr intensiv mit dem Programmieren beschäftige und ich denke das diese Frage eher eine Allgemeine Frage bzw. Verständnisfrage ist...bin ich über jeden Tipp dankbar.
Cheers

 

[JStein52]

Meinst du so was:

        int[][] array = null;
        int[][] daten = {{1,2,3},{3,4,5},{6,6,6}};
        int[][] neueDaten = {{1,3,5}, {2,4,6},{7,8,9}};
      
        array = daten;
        for (int i=0; i<3;i++) {
            for(int j=0;j<3; j++) {
                System.out.print(array[i][j]);
            }
            System.out.println();
        }
        array = neueDaten;
        for (int i=0; i<3;i++) {
            for(int j=0;j<3; j++) {
                System.out.print(array[i][j]);
            }
            System.out.println();
        }

Du hast eine Referenz auf ein zweidimensionales Array namens array. Wohin diese nun zeigt kannst du ja beliebig festlegen.

 

[l4mer]

Erstmal danke...naja nich ganz das Problem ist das es eine Matrix wo nicht sagen die ist immer 4x4 die kann auch 5x5 sein...dein Vorschlag ist nicht falsch aber nicht was ich suche...ich will eine Algorithmus schreiben und kann jetzt nicht 4 arrays deklarieren und und jedes mal mit for-Schleifen und if-else fragen was passiert...entweder ich stehe gerade sowas von auf dem Schlauch oder es gibt eine andere Möglichkeit xD...versteht man überhaupt das Problem

Edit Ich glaube ich brauche erstmal Abstand und nen klaren Kopf, for fuck sake

 

[JStein52]

Die Matrix muss doch nicht immer 4x4 sein. Das war nur Zufall dass bei mir die zweite genauso gross war wie die erste. Du wolltest doch wissen wie du deiner Schleife ein anderes (grösser, kleiner, egal) Array mitgibst. Und was ich dir sagen wollte ist: du arbeitest in der Schleife immer mit einer bestimmten Referenz auf die aktuell Matrix. Und für die nexte Schleife setzt du einfach die Referenz auf die verkleinerte Matrix.

 

[l4mer]

Ja, dass habe ich kapiert danke...sagen wir ich will die Matrix zum Schluss auf einen Eintrag reduzieren...muss ich jetzt wirklich 5 oder mehr Referenzen setzen 10 for-Schleifen usw. schreiben

Ich stelle mir das irgendwie "effizienter" vor xD

 

[JStein52]

Du hast doch gesagt am Ende eines Schleifendurchlaufs hast du aus einer grossen Matrix eine kleinere gemacht. Und die willst du jetzt wieder verkleinern oder ? dann setzt du einfach die Referenz die vorher auf die grosse Matrisx zeigt am Ende deiner Schleife auf die verkleinerte Matrix und machst das selbe wieder.
Hast du denn schon ein Stück Code zum anschauen ?

 

[klauskarambulut]

Letmeduckduckgothisforyou:
https://duckduckgo.com/?q=Matrix-Minimum-Verfahren

Der erste Eintrag dann:
https://de.wikipedia.org/wiki/Matrixminimumverfahren

 

[l4mer]

Ich poste jetzt einfach mal meinen Code...und danke klauskaramulut aber die Funktionsweise is mir klar

 

[l4mer]

package basislösung;

public class MatrixMin {

  
    public void minimieren(int[][] transportmatrix){
          
      
        int[][] neue=null;
      
        int min=Integer.MAX_VALUE;
      
        int sum_kapazität = 0;  
        int sum_bedarf = 0;
      
        int[] spalte = new int[5];
        int s_index= 0;
        int[] zeile = new int[5];
        int z_index= 0;
      
        int l = 0;
        int x = 0;
        int y = 0;
      
        int[][] werte = new int[9][2];                                                //m+n-1 Basislösungen...9
              
        for(int i=1;i<transportmatrix.length-1;i++){
            for(int j=6;j<transportmatrix[i].length;j++){
                int u = transportmatrix[i][j];
                spalte[s_index]=u;
                s_index++;
            }          
        }
      
        for( int i : spalte) {                                          
            sum_kapazität += i;                  
        }
      
      
        for(int i=6;i<transportmatrix.length;i++){
            for(int j=1;j<transportmatrix[i].length-1;j++){
                int u = transportmatrix[i][j];
                zeile[z_index]=u;
                z_index++;
            }
        }
                                                                                          
        for( int i : zeile) {
            sum_bedarf += i;
        }
      
        //System.out.println(sum_kapazität+" "+sum_bedarf);
      
        //while(sum_kapazität != 0 && sum_bedarf != 0){
        //    System.out.println("lol");
        //}
        //
        //
        //
        //hier ist mein problem ich verkleinere die transportmatrix nachfolgend und schreibe alles in ein kleiners array=mini
        //entweder mit einer spalte weniger oder eben mit einer zeile weniger...
        //
        //jetzt muss ich diese matrix mini eben wieder um eine zeile oder spalte verringern werden bis 9(m+n-1) variablen gefunden wurden
        //ich weiß nicht wie ich mein problem weiter erklärn soll...
        //
        //
              
for(int ro=0;ro<3;ro++){                                                        //Schleife bis Matrix minimiert ist, Abbruch ist m+n-1=9
          
        System.out.println("Angebot"+sum_kapazität+"Nachfrage"+sum_bedarf);
  
        for (int r = 1; r < transportmatrix.length-1; r++){                                                                       
              for (int c = 1; c < transportmatrix[r].length-1; c++){
                  if(transportmatrix[r][c] < min){
                    min = transportmatrix[r][c];
                  }
              }
        }          
        System.out.println("Kleinste Element in der Matrix: "+"("+min+")");
      
        for(int i=1;i<transportmatrix.length-1;i++){
            for(int j=1;j<transportmatrix[i].length-1;j++){
                    l = transportmatrix[i][j];                  
                if(l==min){  
                    x=j;
                    y=i;
                    System.out.println(i+" "+j+" Position im Array: "+"("+l+")");
                }                          
            }                  
        }
      
        int bedarf = transportmatrix[6][x];                                            //letztes Element der Spalte...
        int kapazität = transportmatrix[y][6];                                         //letztes Element der Zeile...
      
        for(int w=1;w<transportmatrix.length;w++){
            for(int v=1;v<transportmatrix[w].length;v++){
                int u = transportmatrix[w][v];
                System.out.print(u+"\t");
            }
            System.out.println();
        }
      
      
      
        if(bedarf>kapazität){//Zeile löschen                                                    //Check ob Zeile oder Spalte gelöscht wird...
          
          
          
            int[][] mini = new int[transportmatrix.length-1][transportmatrix[0].length];        //Neue, verkleinerte Matrix mit einer Zeile weniger...
          
            System.out.println();
          
            int mini_row = 0;
            int mini_column = 0;
          
            transportmatrix[y][6]=0;                                              
            transportmatrix[6][x]=bedarf-kapazität;
              
            werte[ro][0] = kapazität;                                                //Kosten und Variable werden in Zwischenmatrix geschrieben...
            werte[ro][1] = min;
          
                for(int r = 1; r < y; r++){                                            //Schleife zum holen der Elemente und verschieben in neue Matrix mit gelöschter Zeile bzw. Spalte
                    for(int c = 1; c < transportmatrix[r].length; c++){
                        int u=transportmatrix[r][c];
                        mini[mini_row][mini_column]=u;
                        mini_column++;
                        //System.out.print(u+"\t");
                    }
                    mini_column=0;
                    mini_row++;
                    //System.out.println();
                }              
                for(int r = y+1; r < transportmatrix.length; r++){                                          
                    for(int c = 1; c < transportmatrix[r].length; c++){
                        int u=transportmatrix[r][c];
                        mini[mini_row][mini_column]=u;
                        mini_column++;
                        //System.out.print(u+"\t");
                    }
                    mini_column=0;
                    mini_row++;
                    //System.out.println();
                }              
              
                for(int z=0;z<mini.length-1;z++){
                    for(int o=0;o<mini[z].length-1;o++){
                        int u = mini[z][o];
                        System.out.print(u+"\t");
                    }
                    System.out.println();
                }
              
                neue=mini;
                      
        }else{//Spalte löschen
          
            int[][] mini = new int[transportmatrix.length][transportmatrix[0].length-1];        //Neue, verkleinerte Matrix mit einer Spalte weniger...
          
            System.out.println();
          
            int mini_row = 0;
            int mini_column = 0;
          
          
            transportmatrix[y][6]=kapazität-bedarf;                                              
            transportmatrix[6][x]=0;
          
            werte[ro][0] = bedarf;                                                    //Kosten und Variable werden in Zwischenmatrix geschrieben...
            werte[ro][1] = min;
          
              
                for(int r = 1; r < transportmatrix.length; r++){                    //Schleife zum holen der Elemente und verschieben in neue Matrix mit gelöschter Zeile bzw. Spalte
                    for(int c = 1; c < x; c++){
                        int u=transportmatrix[r][c];
                        mini[mini_column][mini_row]=u;
                        mini_row++;
                        //System.out.print(u+"\t");
                    }
                    mini_row=0;
                    mini_column++;
                    //System.out.println();
                }  
                              
                mini_row=x-1;                                                        //sonst Out-of-Bound Exception....
                mini_column=0;
              
                for(int r = 1; r < transportmatrix.length; r++){                  
                    for(int c = x+1; c < transportmatrix[r].length; c++){
                        int u=transportmatrix[r][c];
                        mini[mini_column][mini_row]=u;
                        mini_row++;
                        //System.out.print(u+"\t");
                    }
                    mini_row=x-1;
                    mini_column++;
                    //System.out.println();
                }  
              
              
                for(int z=0;z<mini.length-1;z++){
                    for(int o=0;o<mini[z].length-1;o++){
                        int u = mini[z][o];
                        System.out.print(u+"\t");
                    }
                    System.out.println();
                }
              
                neue=mini;          
        }
        System.out.println();
      
    }
      
          
  
    for(int z=0;z<werte.length;z++){
        for(int o=0;o<werte[z].length;o++){
            int u = werte[z][o];
            System.out.print(u+" ");
        }
        System.out.println();
    }
  
              
    }
}

 

[klauskarambulut]

und danke klauskaramulut aber die Funktionsweise is mir klar

Sehr schön, dass dir das klar ist. "Und die willst du jetzt wieder verkleinern oder ?" könnte vielleicht bedeuten das ihm das nicht klar ist und es deine Aufgabe ist dafür zu sorgen, dass ihm das klar wird.

Gefällt dir den der Code?

Das ist totaler Schrott, den sich niemand durchliest.

Ein rekursiver Ansatz:

public void minimize(int[][] cost){
  if(isEmpty(cost)) {
    System.out.println("Done! - Cost Matrix is empty");
    return;
  }
  int row = findMinCostRowIndex(cost);
  int col = findMinCostColumnIndex(cost, row);
  
  int costPerPiece = getCostPerPiece(cost, row, col);
  int amount = moveAmount(cost, row, col);

  System.out.printf("Move %d pieces with cost: %d from %d to %d%n", amount, costPerPiece, row, col);

  int availableSupply = findSupplyFor(cost, row);
  int availableDemand = findDemandFor(cost, col);

  int[][] reducedCost = cost;
  if(amount == availableSupply) {
    reducedCost = removeRow(reducedCost, row);
  }
  if(amount == availableDemand) {
    reducedCost = removeColumn(reducedCost, col);
  }
  
  //Recursiver Aufruf
  minimize(reducedCost);
}

Warum ist das jetzt besser? Es sind keine Schleifen mehr vorhanden. Auch keine geschachtelten Schleifen.
Der Code spricht. Eine Methode passt zumindest noch auf eine Bildschirmseite.
Die einzelnen Methoden sind einfacher, klar definiert und können besser getestet, weil einzeln angesprochen werden.

Beispiel einer dieser einfachen Methoden

 int findMinCostColumnIndex(cost, row) {
  int minIndex = 0;
  for(int i = 1; i < cost[row].length; i++) {
    if(cost[row][i] < cost[row][minIndex]) {
      minIndex = i;
    }
  }
  return minIndex;
}

int findMinCostRowIndex(cost) {
  int minRowIdx = 0;
  int minColIdx = findMinCostColumnIndex(cost, 0);
  for(int i = 1; i < cost.length; i++) {
    int currentMinColIdx = findMinCostColumnIndex(cost, i);
    if(cost[i][currentMinColIdx] < cost[minRowIdx][minColIdx]) {
      minRowIdx = i;
      minColIdx = currentMinColIdx;  
    }
  }
  return minRowIdx;
}