algorithme pour trouver l'indice x y optimal tel que la somme des points dans chaque quadrant soit minimisée

Question

J'ai un tableau 2D qui contient divers points de données. Voir la figure 1. Je dois le diviser en 4 quadrants de manière à ce que la somme de tous les points dans chaque quadrant soit minimisée. La taille minimale de chaque quadrant est de 4x4, elle peut être supérieure mais pas inférieure et ne doit pas nécessairement être un carré. Un quadrant optimal pourrait avoir une taille de 5x3 par exemple.

Je dois trouver les indices optimaux x et y qui mèneront à des quadrants dont les sommes sont minimales.

Je vois ça comme un problème de répartition du poids. Je peux additionner toutes les valeurs de mon tableau 2D et j'obtiens une somme, S. Maintenant, je dois répartir plus ou moins également cette somme S entre 4 quadrants. Je sais que j'ai mentionné que la somme de chaque quadrant doit être la plus petite possible, mais il s'agit plutôt d'un minimum équilibré.

Answer 1

Vous pouvez additionner les valeurs de chaque quadrant de manière efficace en utilisant une fonction Tableau de la surface cumulée . C'est une matrice avec les mêmes dimensions que votre matrice où table[i][j] est la somme de tous les éléments de la matrice originale à travers les rangées 0 à i et les colonnes 0 à j.

Vous pouvez le calculer comme suit (pseudo-code) :

for i = 0 to rows
    row_sum = 0
    for j = 0 to columns
        row_sum += matrix[i][j]
        table[i][j] = row_sum
        if i > 0
            table[i][j] += table[i-1][j]

Le code ci-dessus conserve une somme courante sur chaque ligne, et l'ajoute à l'entrée du tableau de la ligne précédente dans la même colonne.

Vous pouvez ensuite utiliser ce tableau pour calculer la valeur de chaque quadrant, pour un fractionnement donné. Supposons que vous souhaitiez effectuer une division en quadrants horizontalement après la ligne i et verticalement après la colonne j, et que les quadrants soient les suivants :

a | b
--+--
c | d

Vous pouvez calculer les sommes des quadrants comme suit :

a = table[i][j]
b = table[i][columns-1] - a
c = table[rows-1][j] - a
d = table[rows-1][columns-1] - (a + b + c)

Ainsi, vous pouvez itérer sur la matrice et calculer les sommes des quadrants pour chaque emplacement de division possible en utilisant 4 tables de consultation et quelques additions et soustractions simples. Gardez la trace de l'emplacement le plus optimal (selon vos critères, par exemple la plus petite différence entre le quadrant minimum et le maximum) et vous obtiendrez votre réponse.

C'est O(n) sur le nombre d'éléments dans la matrice.