Trouver un minimum local en x n n la matrice en O(n) fois

Donc, ce n'est pas mon travail à domicile question, mais il est pris à partir de l'option devoirs de la coursera cours sur les algorithmes et structures de données (qui est maintenant terminée).

Vous êtes donné un n par n grille de numéros distincts. Un nombre est un minimum local si elle est plus petite que celle de tous ses voisins. (Un voisin d'un nombre est l'un immédiatement au-dessus, au-dessous, vers la gauche ou la droite. La plupart des numéros ont quatre voisins; les numéros sur le côté en ont trois, quatre coins ont deux.) Utiliser le diviser et conquérir la conception d'un algorithme de paradigme pour calculer un minimum local, avec seulement O(n) les comparaisons entre les paires de nombres. (Note: depuis il y a n² numéros dans l'entrée, vous ne pouvez pas se permettre de regarder tous. Astuce: Pensez à ce type de récidives serait le niveau désiré de la limite supérieure.)

Étant donné que les numéros ne sont pas dans n'importe quel ordre, je ne vois pas comment on peut s'en tirer avec quelque chose, mais O(n²) comparaisons.

Le faire dans O(log(n)) ou O(n) ?
Il y a n^2 éléments, de sorte que O(n) sera génial. Bien sûr, en O(log(n)) serait génial si possible
Nous avons également besoin d'être prudent sur ce n est. D'abord, vous avez dit n était le nombre de lignes et de colonnes qui signifie qu'il ya n^2 numéros. Chaque numéro a environ 4 voisins il y a donc à peu près 4*n^2/2 paires, oui? En termes de m étant le nombre de paires si nous sommes censés le faire dans O(m) alors que c'est O(n^2). Aussi, nous sommes juste de l'informatique en un seul minimum local n'est pas le moindre élément?
Oui, il pourrait y avoir un double comptage dans le 4*n^2/2, mais je pense qu'il est toujours en O(n^2). Et oui, nous voulons juste un seul minimum local, pas global.
J'ai édité le titre de cette question pour correspondre à son contenu. Il n'y a rien au sujet de "log n" ici, à tous. La question est en fait très clair. Je ne le sais pas encore, cependant.

InformationsquelleAutor Rohit Pandey | 2013-08-30

algorithm search

32

Nous pouvons adapter les Mots Comme Jared réponse, en regardant comment il peut aller mal.

L'idée dans sa réponse, ce qui est un bon un, est de "mettre la descente". Cela signifie simplement que, si vous êtes sur un élément, vérifiez si elle est un minimum local. Si oui, vous êtes fait; sinon, l'étape la plus petite de ses plus proches voisins. Finalement, cela doit se terminer parce que chaque étape est à un plus petit élément, et qui ne peuvent pas aller à l'infini dans le fini de tableau.

Le problème avec cette approche est que le "roulement" pouvez flâner dans tous les sens:
```
20 100 12  11 10 100  2
19 100 13 100  9 100  3
18 100 14 100  8 100  4
17  16 15 100  7   6  5
```
Si vous commencez dans le coin supérieur gauche et de "rouler " descente", la visite de près de la moitié des éléments dans le tableau. C'est trop, nous devons donc nous limiter un peu.

Commencer par l'examen de la colonne du milieu et de la rangée du milieu. Trouver le plus petit élément parmi tous ceux et commencer par là.

Rouler une étape "descente" de là à entrer dans l'un des quatre quadrants. Vous entrez dans l'un des quadrants, parce que les éléments adjacents dans la colonne du milieu et/ou de la ligne sont de plus grande taille, de sorte qu'une seule des deux quadrants adjacents peut être "descente".

Maintenant, considérons ce qui se passerait si vous "roulé descente" à partir de là. Évidemment, on finirait par atteindre un minimum local. (On va pas faire ça parce que ce serait trop long.) Mais, dans le cadre de rouler, vous ne laissez jamais le quadrant... Parce que pour ce faire, vous devez traverser le milieu de la colonne ou de la rangée du milieu, et aucun de ces éléments sont plus petits que celui où vous avez commencé. Donc quadrant contient un minimum local, quelque part.

Ainsi, dans le temps linéaire, nous avons identifié un quadrant qui doit contenir un minimum local, et nous avons réduit de n dans la moitié. Maintenant, juste une boucle.

Cet algorithme prend du temps 2n + 2n/2 + 2n/4 + ..., qui est égal à 4n, qui est O(n), de sorte que nous avons fini.

Fait intéressant, nous n'utilisons pas de "rouler en descente" très bien, à l'exception de la partie critique: Prouver que l'algorithme fonctionne.

[Mise à jour]

Comme Incassator souligne, cette réponse n'est pas tout à fait correct, parce que, après vous "juste recurse" vous pouvez rouler hors du quadrant nouveau...

La solution la plus simple est de rechercher le plus petit élément parmi la rangée du milieu, colonne du milieu, et de la limite avant de "rouler " descente".
- Nous sommes à la recherche pour un minimum local pas le minimum.
InformationsquelleAutor Nemo
14

La accepté de répondre par Nemo est sympa, mais pas tout à fait correcte:

Ainsi, dans le temps linéaire, nous avons identifié un quadrant qui doit contenir un minimum local, et nous avons réduit de n dans la moitié. Maintenant, juste une boucle.

Je me réfère à la "juste recurse" peu. Le problème est que l'on ne peut pas le faire directement, car sur la prochaine itération nous pourrions trouver un minimum local qui est pas un minimum local pour grille d'origine (x ci-dessous signifie que certains arbitraire grands nombres):
```
 x  x 39  x  x 50  x  x  x  x  x
 x  x 38  x  x 49  x  x  x  x  x
37 36 33 34 35 48  x  x  x  x  x
 x  x 32  x  1 10  x  x  x  x  x
 x  x 31  x  x 47  x  x  x  x  x
46 45 30 44 43 60 51 52 53 54 55
 x  x  2  x  x 56  x  x  x  x  x
 x  x  x  x  x 57  x  x  x  x  x
 x  x  x  x  x 58  x  x  x  x  x
 x  x  x  x  x 59  x  x  x  x  x
```
À la première itération, nous trouvons 10 pour être un minimum de milieu de ligne et de colonne du milieu. Nous allons à gauche (comme 1 est à moins de 10). Donc, notre prochaine itération est sur le quadrant supérieur gauche. Mais désormais minimum de milieu de ligne et de colonne va être 31 (ou 30 si quadrant frontières sont considérées comme faisant partie de celui-ci). Vous serez alors en conclure que c'est un minimum local. Mais il n'est pas de la grille.

Nous pouvons remédier à cette regrettable anomalie dans une variété de façons. Je l'ai résolu comme ceci:

À chaque itération en plus de la grille elle-même nous gardons la trace de courant minimum candidat (c'est le 1 dans l'exemple ci-dessus, après la première itération; dans l'état initial, nous pouvons dire minimum candidat est plus l'infini). Nous calculons minimum de milieu de ligne et de colonne et de le comparer au minimum candidat. Si ce dernier est plus petit nous recurse dans le quadrant contenant minimum candidat. Sinon on oublie précédente candidat et ensuite seulement de vérifier si de nouvelles milieu de la ligne/colonne minimum est en fait un minimum local. Et si non, alors recurse comme à l'habitude, quel que soit le quadrant nous en pente vers le bas à partir d'elle (et de suivre un nouveau minimum candidat).

Alternativement, vous pouvez modifier la procédure décrite dans vraisemblablement, MIT conférence: à chaque itération au lieu de chercher au milieu de la ligne/colonne, vous pouvez regarder au moyen de ligne/colonne et ligne de la grille. Ensuite, l'algorithme est de nouveau correct.

Vous choisissez la façon dont vous le souhaitez.
- Comment voulez-vous résoudre les liens, quand il y a 2 des minimums locaux dans une matrice. Pour E. g la matrice de {{9,10}, {15,8}} a deux des minimums locaux de viz. 9 (premier élément 0,0) et 8 (dernier élément (1,1))
- Vous êtes tenus de les trouver un minimum local. Selon celui que vous trouvez. Donc, si au cours d'une itération de l'algorithme que vous avez plusieurs éléments minimaux, vous procédez de l'une quelconque de celles-ci.
InformationsquelleAutor Incassator
7

Je pense que c'est en fait très facile.

Tourner le problème en 3-D de voir pourquoi l'algorithme fonctionne. Mettre la matrice sur une table. Prétendre le contraire sont des piliers qui s'étend de chaque cellule et que la hauteur de la colonne est directement proportionnelle à sa valeur. Mettre une boule sur n'importe quel pilier. Avoir le ballon tombe toujours sur la côté pilier qui est l'altitude la plus faible jusqu'à ce qu'il est à un minimum local.
- Cela donne la bonne réponse, mais c'est trop lent. La balle peut rouler en bas de la première colonne, deux pas à droite, en haut de la troisième colonne, deux pas à droite, en bas de la cinquième colonne... Tout le chemin jusqu'à ce qu'il débarque dans le coin opposé. (Il est facile de construire un exemple où cela se produit.) Qui touche la moitié de la places de, et la compare autour de quatre fois ce montant, qui est en O(n^2), pas de O(n).
- Sonne bien, mais est-il O(log(N))? Probablement, mais il vaut la peine d'ajouter de la complexité de l'analyse de la réponse je pense.
- Cette solution est O(n^2) je crois. Peu importe où vous commencez votre nemisis pouvez concevoir une paroi labyrinthe qui vous emmène à travers la moitié de la cellules.
- Assez juste, mais dans ce cas le pire des cas en O(n) algorithme existe réellement. Voir ma réponse. (Aussi, quand un problème comme cela, dit algorithme O(n), je crois que le "pire cas" est implicite. Si ils parlent des moyennes, ils ont l'habitude de le dire.)
InformationsquelleAutor Words Like Jared
1

Bien, c'est comment vous diviser et conquérir.

1) Diviser le n x n de la matrice en quatre n/2 x n/2 sous-matrices.

2) continuer à diviser les sous-matrices de manière récursive jusqu'à ce que vous vous retrouvez avec une matrice de 2 x 2

3) Vérifier si tout élément de matrice de 2 x 2 est un Minimum local.

Équation de récurrence est : T(n) = 4*T(n/2) + O(1)

4*T(n/2) pour 4 n/2 x n/2 sous-matrices et O(1) pour vérifier si 2 x 2 sous matrice de a un minimum local

Maître théorème dit que c'est une O(n^2) pire des cas lié.

Mais je pense que nous pouvons obtenir un meilleur des cas O(n) lié,

(" ALERTE ROUGE! ---DANS LE MEILLEUR DES CAS EST FAUX, TOUT FAUX---ALERTE ROUGE!").

si nous sortons de la récursivité de la pile après que nous avons trouvé un minimum local de l'étape 3.

Pseudocode:
```
private void FindlocalMin(matrix,rowIndex,colIndex,width){
    if(width == 1){ checkForLocalMinimum(matrix,rowIndex,colIndex); return;} //2x2 matrix
    FindlocalMin(matrix,rowIndex,colIndex,width/2);  
    FindlocalMin(matrix, (rowIndex + (width/2) + 1) ,colIndex,width/2);
    FindlocalMin(matrix,rowIndex, (colIndex + (width/2) + 1) ,width/2);
    FindlocalMin(matrix,(rowIndex + (width/2) + 1), (colIndex + (width/2) + 1) ,width/2);
}

private void checkForLocalMinimum(.........){
    if(found Local Minimum in 2x2 matrix){ exit recursion stack;} 
}
```
Ici est un l'implémentation java

InformationsquelleAutor Charan

Code Fonctionne pour les 3*3 ou plus de la matrice, développée par l'exercice d'Algorithmes 4ème Édition du Livre d'Exercice .

Il fonctionne comme Suit

Recherchez la ligne du milieu de la matrice donnée et trouver le minimum de ce
pour qu'un minimum d'recherchez ci-dessus et en dessous de l'élément pour s'assurer qu'il est un minimum local
si pas restreindre la recherche de la matrice par
1. Ligne : choisissez à côté de la moitié de la ligne dans laquelle le moindre élément de la ligne du milieu de l'élément.
2. colmun : choisir l'indice minimum de la ligne a été trouvé.
Répétez l'étape 1-3

public class MinimumOfMatrix {

private static int findLocalMinimum(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd) {

    int midRow = (rowStart + rowEnd) /2;
    int minPos = findMin(matrix, midRow, colStart, colEnd);

    if (minPos >= (colStart + colEnd) /2)
        colStart = (colStart + colEnd) /2;
    else
        colEnd = (colStart + colEnd) /2;

    if (matrix[midRow][minPos] < matrix[midRow + 1][minPos]
            && matrix[midRow][minPos] < matrix[midRow - 1][minPos]) {
        return matrix[midRow][minPos];
    } else if (matrix[midRow][minPos] > matrix[midRow + 1][minPos]) {
        return findLocalMinimum(matrix, midRow, rowEnd, colStart, colEnd);
    } else {
        return findLocalMinimum(matrix, rowStart, midRow, colStart, colEnd);
    }

}

private static int findMin(int[][] matrix, int midRow, int colStart, int colEnd) {
    int min = Integer.MAX_VALUE;
    int pos = -1;

    for (int i = colStart; i < colEnd; i++) {
        if (matrix[midRow][i] < min) {
            min = matrix[midRow][i];
            pos = i;
        }

    }

    return pos;
}

public static void main(String[] args) {
    //Best Case
    /*
     * int[][] matrix= { {1,-2,4,-6,1,8}, { -3,-6,-8,8,1,3}, {1,2,6,-2,-8,-6},
     * { -2,9,6,3,0,9}, {9,-1,-7,1,2,-6}, { -9,0,8,7,-6,9} };
     */

    //Two Iteration Down Case
    /*
     * int[][] matrix= { { 1,-2, 4,-6, 1, 8}, { -3,-6,-8, 8, 1, 3}, { 1, 2, 6, 9, 0,
     * 6}, { -2, 9, 6,-1,-1, 9}, { 9,-1,-7, 1, 2,-6}, { -9, 0, 8, 7,-6, 9} };
     */

    /*
     * //Left Down Case int[][] matrix= { { 1,-2, 4,-6, 0, 8}, { -3,-6,-8, 8,-2, 3},
     * { -2, 9, 6,-1, 1, 9}, { 1, 0, 6, 9, 2, 6}, { 9,-1,-7, 1, 2,-6}, { -9, 0, 8,
     * 7,-6, 9} };
     */

    int[][] matrix = { { 1, -2, 4, }, { -3, -6, -8, }, { -2, 9, 6, }

    };

    System.out.println(findLocalMinimum(matrix, 0, matrix.length, 0, matrix.length));

}

}

Pourquoi ce travail? Veuillez expliquer vos réponses
Il fonctionne comme Suit 1. Recherchez la ligne du milieu de la matrice donnée et trouver le minimum de 2. pour qu'un minimum d'recherchez ci-dessus et en dessous de l'élément pour s'assurer qu'il est local minimu 3. si pas de restreindre la recherche de la matrice par 1. Ligne : choisissez à côté de la moitié de la ligne dans laquelle le moindre élément de la ligne du milieu de l'élément. 2. colmun : choisir l'indice minimum de la ligne a été trouvé. 4. Répétez l'étape 1-3
Les questions dit que la matrice est constituée d'entiers distincts, mais j'ai de voir des répétitions dans vos exemples.

InformationsquelleAutor Vivek Bhojawala

Vous devez vous connecter pour publier un commentaire.