Tout d'abord, formalisons votre problème d'optimisation en spécifiant l'entrée, la sortie et la mesure pour chaque solution possible (j'espère que cela vous intéresse) :
Étant donné un tableau A d'entiers positifs et un entier positif P , séparer le tableau A en P des sous-réseaux qui ne se chevauchent pas, de sorte que la différence entre la somme de chaque sous-réseau et la somme parfaite des sous-réseaux (somme( A )/ P ) est minimal.
Entrée : Tableau A d'entiers positifs ; P est un nombre entier positif.
Sortie : Tableau SA de P des nombres entiers non négatifs représentant la longueur de chaque sous-réseau de A où la somme des longueurs de ces sous-réseaux est égale à la longueur de A .
Mesure : abs(sum( sa )-somme( A )/ P ) est minimal pour chaque sa ∈ { sa sa \= ( A <em>i </em> , , A <em>i </em>+ <em>SA </em><em>j </em> ) pour i \= (Σ SA <em>j </em> ), j de 0 à P -1}.
En entrée y sortie définissent l'ensemble des solutions valides. Les mesure définit une mesure permettant de comparer plusieurs solutions valides. Et puisque nous recherchons une solution qui présente le moins de différence avec la solution parfaite (problème de minimisation), mesure devrait également être minime.
Avec ces informations, il est assez facile de mettre en œuvre le programme measure (ici en Python) :
def measure(a, sa):
sigma = sum(a)/len(sa)
diff = 0
i = 0
for j in xrange(0, len(sa)):
diff += abs(sum(a[i:i+sa[j]])-sigma)
i += sa[j]
return diff
print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8
Il est maintenant un peu plus difficile de trouver une solution optimale.
Nous pouvons utiliser le Algorithme de retour en arrière pour trouver des solutions valables et utiliser le mesure pour les évaluer. Nous essayons toutes les combinaisons possibles de P nombres entiers non négatifs dont la somme est égale à la longueur( A ) pour représenter toutes les solutions valides possibles. Bien que cela garantisse de ne pas manquer une solution valable, il s'agit essentiellement d'une approche brute, avec l'avantage de pouvoir omettre certaines branches qui ne peuvent pas être meilleures que notre meilleure solution. Par exemple, dans l'exemple ci-dessus, nous n'aurions pas besoin de tester les solutions avec [9, ] ( mesure > 38) si nous avons déjà une solution avec mesure ≤ 38.
En suivant le modèle de pseudocode de Wikipedia, notre bt se présente comme suit :
def bt(c):
global P, optimum, optimum_diff
if reject(P,c):
return
if accept(P,c):
print "%r with %d" % (c, measure(P,c))
if measure(P,c) < optimum_diff:
optimum = c
optimum_diff = measure(P,c)
return
s = first(P,c)
while s is not None:
bt(list(s))
s = next(P,s)
Les variables globales P , optimum y optimum_diff représente l'instance du problème contenant les valeurs de A , P y sigma ainsi que la solution optimale et sa mesure :
class MinimalSumOfSubArraySumsProblem:
def __init__(self, a, p):
self.a = a
self.p = p
self.sigma = sum(a)/p
Ensuite, nous spécifions le reject y accept qui sont assez simples :
def reject(P,c):
return optimum_diff < measure(P,c)
def accept(P,c):
return None not in c
Il s'agit simplement de rejeter tout candidat dont la mesure est déjà supérieure à notre solution optimale. Et nous acceptons toute solution valide.
En measure est également légèrement modifiée en raison du fait que la fonction c peut désormais contenir None valeurs :
def measure(P, c):
diff = 0
i = 0
for j in xrange(0, P.p):
if c[j] is None:
break;
diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
i += c[j]
return diff
Les deux autres fonctionnent first y next sont un peu plus compliquées :
def first(P,c):
t = 0
is_complete = True
for i in xrange(0, len(c)):
if c[i] is None:
if i+1 < len(c):
c[i] = 0
else:
c[i] = len(P.a) - t
is_complete = False
break;
else:
t += c[i]
if is_complete:
return None
return c
def next(P,s):
t = 0
for i in xrange(0, len(s)):
t += s[i]
if i+1 >= len(s) or s[i+1] is None:
if t+1 > len(P.a):
return None
else:
s[i] += 1
return s
En principe, first soit remplace le None dans la liste avec l'un ou l'autre des éléments suivants 0 si ce n'est pas la dernière valeur de la liste ou avec le reste pour représenter une solution valide (petite optimisation ici) si c'est la dernière valeur de la liste, ou il retourne None s'il n'y a pas de None dans la liste. next incrémente simplement l'entier le plus à droite de un ou renvoie None si une augmentation entraîne un dépassement de la limite totale.
Il ne vous reste plus qu'à créer une instance de problème, à initialiser les variables globales et à appeler bt avec la racine :
P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)
