Comment traverser tous les chemins possibles vers une solution et choisir le chemin optimal

Je suis un débutant à Java. Donc, j'utilise cette approche naïve pour trouver le résultat pour votre problème. Je calcule la somme de la rangée et la somme de la colonne et de la recherche de la valeur minimale et de l'incrémentation de +1 en conséquence. Lorsque je rencontre la même valeur pour la rangée et la colonne, c'est lorsque j'essaie de contenir les valeurs de ligne d'itération et de colonne précédentes et à obtenir le tout à partir de là et y incrémentez-le.

aussi, j'ai pris soin de Nexn Matrix Mais aussi pour matrice MXN. p>

ci-dessous est mon approche de ce problème: p>

try {
            for (k = 0; k < 4; k++) {
            int rowSum[] = new int[arr.length];
            int columnSum[] = new int[arr[0].length];

            // Gets the sum for rows

            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < ((arr[0].length)); j++) {
                    rowSum[i] = rowSum[i] + arr[i][j];
                }
            }
            System.out.println("Row sum is: " + Arrays.toString(rowSum));

            // Gets the sum for columns

            for (int j = 0; j < arr[0].length; j++) {
                for (int i = 0; i < (arr.length); i++) {
                    columnSum[j] = columnSum[j] + arr[i][j];
                }
            }

            System.out.println("Column sum is: " + Arrays.toString(columnSum));

            // to find the smallest

            int minRowSumValue = rowSum[0];
            for (int i = 0; i < rowSum.length; i++) {
                if (rowSum[i] < minRowSumValue) {
                    minRowSumValue = rowSum[i];
                }
            }
            System.out.println("Min row sum value is: " + minRowSumValue);

            int minColSumValue = columnSum[0];
            for (int i = 0; i < columnSum.length; i++) {
                if (columnSum[i] < minColSumValue) {
                    minColSumValue = columnSum[i];
                }
            }
            System.out.println("Min column sum value is: " + minColSumValue);

            if (minRowSumValue < minColSumValue) {
                int a = getArrayIndex(rowSum, minRowSumValue);
                for (int i = a; i < arr.length; i++) {
                    for (int j = 0; j < ((arr[0].length)); j++) {
                        arr[i][j] = arr[i][j] + 1;
                    }
                    oldMinSumColValue = minColSumValue;
                    oldMinSumRowValue = 0;
                    finalSum += minRowSumValue;
                    break;
                }

            } else if (minColSumValue < minRowSumValue) {
                int a = getArrayIndex(columnSum, minColSumValue);
                for (int j = a; j < arr[0].length; j++) {
                    for (int i = 0; i < (arr.length); i++) {
                        arr[i][j] = arr[i][j] + 1;
                    }
                    oldMinSumRowValue = minRowSumValue;
                    oldMinSumColValue = 0;
                    finalSum += minColSumValue;
                    break;
                }
            } else if(minRowSumValue == minColSumValue) {
                if (oldMinSumRowValue != 0) {
                    int a = getArrayIndex(rowSum, oldMinSumRowValue);
                    for (int i = a; i < arr.length; i++) {
                        for (int j = 0; j < ((arr[0].length)); j++) {
                            arr[i][j] = arr[i][j] + 1;
                        }
                        finalSum += minRowSumValue;
                        break;
                    }
                } else {
                    int a = getArrayIndex(columnSum, oldMinSumColValue);
                    for (int j = a; j < arr[0].length; j++) {
                        for (int i = 0; i < (arr.length); i++) {
                            arr[i][j] = arr[i][j] + 1;
                        }
                        finalSum += minColSumValue;
                        break;
                    }
                }
            }
            System.out.println("\nArray is: " + Arrays.deepToString(arr));
        }
        System.out.println("\n\nFinal Array after "+k+" steps is: " + Arrays.deepToString(arr));

        System.out.println("\nFinal sum value is: "+finalSum);

    } catch (Exception e) {
        // TODO: handle exception
        System.out.println("Exception is: " + e);
    }

ci-dessous est mon code. Lorsqu'il rencontre un boîtier ambigu (lorsque les valeurs minimales peuvent être trouvées dans la rangée et la colonne), il essaie les cas et émet un minimum.

Pour chaque itération, il trie deux listes de valeurs n code> . La complexité est donc O (c * k * n log n) code>, où c code> est le nombre de chemins distincts. Je crois que cela est assez proche de l'optimal (en termes de complexité de la force brute), puisque chaque itération, exactement n + 1 code> changera et nous devons donc au moins toucher chacun d'entre eux (Sauf bien sûr, une autre perspicacité algorithmique nous permet de ne toucher que quelques-uns d'entre eux). Selon les valeurs de k code> et n code>, cela pourrait ou pourrait ne pas être assez bon. Pour le cas 2, il fonctionne en un peu plus de 1 seconde. P> xxx pré>

Il peut également imprimer le chemin qu'il choisit si vous fournissez -v code> argument:

Java Minrowcol Minrowcol.test -V P> blockQuote>

Il existe d'autres options: P>

-Quick strong> - Cela réduira le nombre de cas explorés en utilisant des heuristiques. Les heuristiques peuvent être spécifiées avec d'autres options de
-prefer_col strong> - Cela préférera la colonne sur la ligne (par défaut préfère la ligne)
-user_sum_count strong> - cela utilisera la multiplicité de la somme p> BlockQuote>

Pour un petit boîtier de test comme suit: P>

30050

Vous n'avez pas vraiment besoin de garder la matrice entière, juste des sommes, de la rangée et de la colonne.

Compte tenu d'une matrice NXN, laissez Sumbyrow être un vecteur de longueur n qui contient la somme de chaque rangée du Matrix, et laissez Sumbycol être la même chose en ce qui concerne les colonnes. Dans votre exemple, ces vecteurs seraient: p> xxx pré>

maintenant, quel que soit l'indice réel de la ligne minimale [colonne] Nous pouvons être sûrs d'une chose: qu'à la suivante itération Le vecteur SumbyRow [col] aurait un élément incrémenté par N (parce que nous en ajoutant un à chaque élément de cette ligne [colonne]) et le SumbyCol [la ligne] aurait ajouté à chacun de ses éléments (car quelle que soit la somme. Était, nous en ajoutant un à un et un seul des éléments qui le composent). P>

afin que nous puissions vous débarrasser de la grosse matrice laid et de travailler avec ces deux vecteurs. Le raisonnement ci-dessus suggère également un moyen de mettre en œuvre l'itération, à savoir: p>

from numpy import matrix
import numpy as np
n = 2
k = 4
A = matrix([[1,3],
            [2,4]
            ])

sc = [0]*n
sr = [0]*n
for i in range(0,n):
    sc[i] = sum( A.A[:,i] )
    sr[i] = sum( A.A[i,:] )
output=0

def whichmin(c,r, iter):
    if(iter < 0):
        return 1
    r[np.argmin(r)] += n
    c[np.argmin(c)] += n
    if ( np.amin(c) < np.amin(r) ):
        return 1
    elif ( np.amin(r) < np.amin(c) ):
        return 0
    else :
        return whichmin(c,r, (iter -1) )

for j in range(0,k):
    minc = np.amin(sc)
    minr = np.amin(sr)
    if (minc < minr):
        incrindex = np.argmin(sc)
        sc[incrindex]+=n
        sr = [x+1 for x in sr]
        output += minc
    elif (minr < minc):
        incrindex = np.argmin(sr)
        sr[incrindex]+=n
        sc = [x+1 for x in sc]
        output += minr
    else :
        min = whichmin(sc.copy(),sr.copy(), (n - i) )
        if (min==1):
            incrindex = np.argmin(sc)
            sc[incrindex]+=n
            sr = [x+1 for x in sr]
            output += minc
        else:
            incrindex = np.argmin(sr)
            sr[incrindex]+=n
            sc = [x+1 for x in sc]
            output += minr

print(output)
print(sc)
print(sr)