Programme JavaScript pour les matrices de Markov

Une matrice est un tableau bidimensionnel qui comporte un certain nombre de lignes et chaque ligne a le même nombre de colonnes. Le nombre de lignes et de colonnes peut être utilisé pour obtenir l'élément à n'importe quel index spécifique. Pour une matrice de Markov, la somme de chaque ligne doit être égale à 1. Nous allons implémenter un code qui crée une nouvelle matrice de Markov et détermine si la matrice actuellement donnée est une matrice de Markov.

Introduction au problème

Dans la question donnée, nous devons écrire un code pour générer une matrice de Markov en utilisant des données binaires c'est-à-dire en utilisant uniquement des zéros et des uns car nous savons qu'une matrice de Markov est une matrice dans laquelle la somme des lignes doit être égale à 1. (Cela ne veut pas dire qu'il s'agit uniquement de nombres binaires), cela signifie qu'il y aura un 1 dans chaque ligne et que les autres éléments seront des zéros.

Le programme que nous allons implémenter n'est qu'un cas particulier de matrice de Markov.

Pour le deuxième code, nous obtiendrons une matrice et devrons trouver si la matrice actuelle est une matrice de Markov. Regardons ces deux codes -

Créer une matrice de Markov

Dans la section actuelle, nous utilisons les nombres binaires 0 et 1 pour créer une matrice de Markov. Regardons d'abord la méthode, puis nous passerons à l'implémentation du code -

Méthode

Dans ce code, nous allons créer une matrice en utilisant un nouveau mot-clé et un nouveau tableau. Pour chaque index du tableau, nous allons créer à nouveau un tableau pour le remplir.

Pour chaque ligne de la matrice, en utilisant la fonction aléatoire, nous obtiendrons un nombre aléatoire compris dans la plage du nombre de colonnes et remplirons cette colonne de la ligne actuelle avec 1 et les autres avec 0.

Enfin, nous retournerons la matrice.

Exemple

// creating a Markov's Matrix using binary digits
// defining the rows and columns
var row = 4
var col = 5
function MarkovMat(row, col){

   // creating an array of size row
   var arr = new Array(row);

   // traversing over the created array
   for(var i = 0; i < row; i++){

      // creating an array of size column
      var brr = new Array(col);
      brr.fill(0) // making every element zero of current array

      // generating random number
      var k = Math.floor(Math.random()*5);

      // marking kth index as 1
      brr[k] = 1

      // adding columns to the current row
      arr[i] = brr;
   }

   // printing the values
   console.log(arr)
}

// calling the function
MarkovMat(row,col)

Complexité temporelle et spatiale

Dans le code ci-dessus, nous avons déplacé la matrice complète et pour chaque mouvement ou parcours, nous obtenons à chaque fois des nombres aléatoires, ce qui prend un temps constant. Par conséquent, la complexité temporelle du code ci-dessus est O(N*M), où N est le nombre de lignes et M est le nombre de colonnes.

La complexité de l'espace est exactement égale à la taille de la matrice, et nous n'utilisons aucun espace supplémentaire. Par conséquent, la complexité spatiale du code ci-dessus est O(N*M).

Vérifiez si la matrice actuelle est markovienne

Dans la partie actuelle, on nous donne une matrice et nous devons trouver si la matrice actuelle est une matrice de Markov. Regardons d'abord la méthode, puis nous passerons à l'implémentation du code -

Méthode

Dans ce code, nous allons simplement parcourir la matrice et obtenir son décompte pour chaque ligne. Si le décompte de la ligne courante est 1, alors on passe à la ligne suivante, sinon on renvoie la matrice courante qui n'est pas une matrice de Markov.

Exemple

// function to check whether the current matrix is
// markov or not
function isMarkov(mat){
   var rows = mat.length
   var col = mat[0].length;

   // checking the sum of each row
   for(var i = 0; i < rows;i++){
      var count = 0;
      for(var j =0; j<col; j++) {
         count += mat[i][j];
      }
      if(count != 1){
         console.log("The given matrix is not Markov's Matrix");
         return
      }
   }
   console.log("The given matrix is Markov's Matrix");
}

// defining the matrix1
matrix1 = [[0.5, 0, 0.5], [0.5, 0.25, 0.25], [1, 0.0, 0], [0.33, 0.34, 0.33]]
console.log("For the matrix1: ")
isMarkov(matrix1)

// defining the matrix2
matrix2 = [[0.5, 1, 0.5], [0.5, 0.25, 0.25], [1, 0.0, 0], [0.33, 0.34, 0.33]]
console.log("For the matrix2: ")
isMarkov(matrix2)

Complexité temporelle et spatiale

Dans le code ci-dessus, nous parcourons la matrice et stockons la somme de chaque colonne, ce qui rend la complexité temporelle du code ci-dessus O(N*M).

Nous n'utilisons aucun espace supplémentaire dans le code ci-dessus, ce qui rend la complexité de l'espace O(1).

Conclusion

Dans ce tutoriel, nous avons implémenté un programme JavaScript pour les matrices de Markov. Pour une matrice de Markov, la somme de chaque ligne doit être égale à 1. Nous avons implémenté un code qui utilise une fonction de génération de nombres aléatoires pour générer une matrice de Markov binaire dans une complexité temporelle O(N*M) et dans le même espace. De plus, nous avons implémenté un code qui vérifie si la matrice actuelle est une matrice de Markov en un temps O(N*M).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!