Comment comprendre la dynamique de la solution de programmation linéaire de partitionnement?

J'ai du mal à comprendre la dynamique de la solution de programmation linéaire de partitionnement problème. Je suis à la lecture de la La Conception D'Un Algorithme Manuel et le problème est décrit dans la section 8.5. J'ai lu l'article d'innombrables fois, mais je suis tout simplement pas l'obtenir. Je pense que c'est une mauvaise explication (ce que j'ai lu jusqu'à maintenant, a été beaucoup mieux), mais je n'ai pas été en mesure de comprendre le problème assez bien à chercher une autre explication. Des liens vers de meilleures explications bienvenue!

J'ai trouvé une page avec un texte semblable au livre (peut-être à partir de la première édition de l'ouvrage): La Partition Problème.

Première question: Dans l'exemple dans le livre les partitions sont ordonnés du plus petit au plus grand. Est-ce juste une coïncidence? De ce que je peux voir l'ordre des éléments n'est pas significative pour l'algorithme.

C'est ma compréhension de la récursivité:

Permet d'utiliser la séquence suivante et la partition en 4:

{S1...Sn} =  100   150   200   250   300   350   400   450   500
k = 4

Deuxième question: Voici comment je pense que la récurrence de commencer - ai-je bien compris?

Le 1er récursivité:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
100   150   200   250   300 | 350 | 400 | 450 | 500 //done

La 2ème récursivité:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
100   150   200   250 | 300   350 | 400 | 450 | 500 //done

La 3e la récursivité est:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
100   150   200 | 250   300   350 | 400 | 450 | 500 //done

La 4ème récursivité:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
100   150 | 200   250   300   350 | 400 | 450 | 500 //done

La 5ème récursivité:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300   350 | 400 | 450 | 500 //1 partition to go
100 | 150   200   250   300   350 | 400 | 450 | 500 //done

La 6ème récursivité:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
100   150   200   250 | 300 | 350   400 | 450 | 500 //done

Le 7e la récursivité est:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
100   150   200 | 250   300 | 350   400 | 450 | 500 //done

Le 8e la récursivité est:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
100   150 | 200   250   300 | 350   400 | 450 | 500 //done

La 9e récursivité:

100   150   200   250   300   350   400   450 | 500 //3 partition to go
100   150   200   250   300   350   400 | 450 | 500 //2 partition to go 
100   150   200   250   300 | 350   400 | 450 | 500 //1 partition to go
100 | 150   200   250   300 | 350   400 | 450 | 500 //done

etc...

Voici le code tel qu'il apparaît dans le livre:

partition(int s[], int n, int k)
{
    int m[MAXN+1][MAXK+1];                  /* DP table for values */
    int d[MAXN+1][MAXK+1];                  /* DP table for dividers */
    int p[MAXN+1];                          /* prefix sums array */
    int cost;                               /* test split cost */
    int i,j,x;                              /* counters */

    p[0] = 0;                               /* construct prefix sums */
    for (i=1; i<=n; i++) p[i]=p[i-1]+s[i];

    for (i=1; i<=n; i++) m[i][3] = p[i];    /* initialize boundaries */
    for (j=1; j<=k; j++) m[1][j] = s[1];


    for (i=2; i<=n; i++)                    /* evaluate main recurrence */
        for (j=2; j<=k; j++) {
            m[i][j] = MAXINT;
            for (x=1; x<=(i-1); x++) {
                cost = max(m[x][j-1], p[i]-p[x]);
                if (m[i][j] > cost) {
                    m[i][j] = cost;
                    d[i][j] = x;
                }
            }
        }

    reconstruct_partition(s,d,n,k);         /* print book partition */
}

Question à propos de l'algorithme:

Quelles valeurs sont stockées dans le m et d?
Que signifie "coût" signifie? Est-ce simplement le total des éléments de valeurs au sein d'une partition? Ou est-il plus subtil sens?

BTW, même si vous ne pouvez pas répondre à mes questions, j'aimerais avoir des commentaires sur la qualité de la matière d'origine. J'aimerais une confirmation qu'il n'est pas juste moi qui trouve l'explication des pauvres (Il m'a fait sentir assez stoopid).
Je ne pense pas que vous trouverez beaucoup de gens ici en mesure de répondre à votre question, sans donner une brève explication du problème que vous devez résoudre. Il existe de nombreuses variantes de problèmes de partitionnement et le collage de longues tables de l'algorithme exécuté par la main n'a pas de halo rendre les choses plus claires.

InformationsquelleAutor Benedict Cohen | 2011-10-29

36

Être conscient qu'il y a une petite erreur dans l'explication de l'algorithme dans le livre, regardez dans le errata pour le texte "(*) Page 297".

Vos questions:
1. Non, les éléments n'ont pas besoin d'être triés, seulement contiguës (qui est, vous ne pouvez pas réorganiser)
2. Je crois que la façon la plus simple de visualiser l'algorithme est par traçage à la main le reconstruct_partition procédure, à l'aide de la droite de la table dans la figure 8.8 comme un guide
3. Dans le livre, il affirme que m[i][j] est "le minimum possible les coûts sur tous les partitionings de {s1, s2, ... , si}" dans j plages, où le coût d'une partition est les grandes somme des éléments dans l'une de ses parties". En d'autres termes, c'est le "plus petit maximum des sommes", si vous pardonnez l'abus de terminologie. D'autre part, d[i][j] magasins de la position de l'index qui a été utilisé pour faire une partition pour une paire i,j tel que défini avant
4. Pour le sens de "coût", voir la réponse précédente
Edit:

Voici ma mise en œuvre du linéaire de l'algorithme de partitionnement. Il est basé sur Skiena de l'algorithme, mais dans un pythonic façon; et il renvoie une liste des partitions.
```
from operator import itemgetter

def linear_partition(seq, k):
    if k <= 0:
        return []
    n = len(seq) - 1
    if k > n:
        return map(lambda x: [x], seq)
    table, solution = linear_partition_table(seq, k)
    k, ans = k-2, []
    while k >= 0:
        ans = [[seq[i] for i in xrange(solution[n-1][k]+1, n+1)]] + ans
        n, k = solution[n-1][k], k-1
    return [[seq[i] for i in xrange(0, n+1)]] + ans

def linear_partition_table(seq, k):
    n = len(seq)
    table = [[0] * k for x in xrange(n)]
    solution = [[0] * (k-1) for x in xrange(n-1)]
    for i in xrange(n):
        table[i][0] = seq[i] + (table[i-1][0] if i else 0)
    for j in xrange(k):
        table[0][j] = seq[0]
    for i in xrange(1, n):
        for j in xrange(1, k):
            table[i][j], solution[i-1][j-1] = min(
                ((max(table[x][j-1], table[i][0]-table[x][0]), x) for x in xrange(i)),
                key=itemgetter(0))
    return (table, solution)
```
- Merci, c'est de m'aider à parvenir à une conclusion. <rant>Malheureusement, ma conclusion est que le code tel qu'il apparaît dans le livre n'est pas seulement incroyable sait pas, c'est aussi plat erroné. Le résultat de l'exécution du code avec l'entrée 1,1,1,1,1,1,1,1,1 est 1,1,1,1,1|1|1,1, selon le texte, il doit être 1,1,1|1,1,1|1,1,1. Il est possible que j'ai mal interprété la sortie. Si c'est le cas, je le blâme sur le terrible de l'écriture et non pas pour vouloir d'essayer de ma part. Compte tenu de la façon dont beaucoup de bonnes critiques de ce livre a reçu le je suis surpris par cette.</rant>
- Les indices dans le code peut être très difficile d'obtenir un droit, mais après un beaucoup de jouer du violon, il a travaillé comme annoncés pour moi
- J'apprécierais vraiment si pourriez-vous poster votre version de travail.
- J'ai mis à jour ma réponse avec la mise en œuvre. regarde tout à fait différente de celle du livre, mais croyez-moi, c'est la même chose.
- Alternativement, on peut de frein jusqu'à la grande minmax ligne en deux 1. costs = [(max(table[x][j-1] , table[i][0] - table[x][0]),x) for x in xrange(i)] ... 2. (mincost, minx) = min(costs, key=lambda x: x[0])
- cet algorithme permet de pour des lignes vides. est celui qui est permis par l'algorithme?
- Est-il une page wikipédia pour ce problème? Je voudrais connaître d'autres solutions et l'analyse de la complexité
- Aucun, que je sache. La meilleure description est dans La Conception d'un Algorithme Manuel, et vous trouverez un lien vers le chapitre en question
- Le code ont un problème pour le cas seq=[10,1,1,1], k=3. Donc, dans ce cas, il a indice négatif dans la boucle while (n-1<0). Cependant, il peut produire des résultats corrects. Donc, je veux juste dire, de garder l'attention lorsque vous essayez de mettre en œuvre l'aide d'une autre langue.
InformationsquelleAutor Óscar López

J'ai mis en œuvre d'Oscar López algorithme sur PHP. N'hésitez pas à utiliser quand vous en avez besoin.

 /**
* Example: linear_partition([9,2,6,3,8,5,8,1,7,3,4], 3) => [[9,2,6,3],[8,5,8],[1,7,3,4]]
* @param array $seq
* @param int $k
* @return array
*/
protected function linear_partition(array $seq, $k)
{
if ($k <= 0) {
return array();
}
$n = count($seq) - 1;
if ($k > $n) {
return array_map(function ($x) {
return array($x);
}, $seq);
}
list($table, $solution) = $this->linear_partition_table($seq, $k);
$k = $k - 2;
$ans = array();
while ($k >= 0) {
$ans = array_merge(array(array_slice($seq, $solution[$n - 1][$k] + 1, $n - $solution[$n - 1][$k])), $ans);
$n = $solution[$n - 1][$k];
$k = $k - 1;
}
return array_merge(array(array_slice($seq, 0, $n + 1)), $ans);
}
protected function linear_partition_table($seq, $k)
{
$n = count($seq);
$table = array_fill(0, $n, array_fill(0, $k, 0));
$solution = array_fill(0, $n - 1, array_fill(0, $k - 1, 0));
for ($i = 0; $i < $n; $i++) {
$table[$i][0] = $seq[$i] + ($i ? $table[$i - 1][0] : 0);
}
for ($j = 0; $j < $k; $j++) {
$table[0][$j] = $seq[0];
}
for ($i = 1; $i < $n; $i++) {
for ($j = 1; $j < $k; $j++) {
$current_min = null;
$minx = PHP_INT_MAX;
for ($x = 0; $x < $i; $x++) {
$cost = max($table[$x][$j - 1], $table[$i][0] - $table[$x][0]);
if ($current_min === null || $cost < $current_min) {
$current_min = $cost;
$minx = $x;
}
}
$table[$i][$j] = $current_min;
$solution[$i - 1][$j - 1] = $minx;
}
}
return array($table, $solution);
}

InformationsquelleAutor WASD42

Ce qui suit est une version modifiée de la mise en œuvre de Skienna Linéaire de partitionnement de l'algorithme en python qui n'a pas de calculer le dernier k valeurs de la colonne à l'exception de la réponse elle-même : M[N][K] (une cellule de calcul ne dépend que de la précédente )

Un essai contre l'input {1,2,3,4,5,6,7,8,9} (utilisé dans Skienna de l'exemple dans le livre ), les rendements légèrement différente de la matrice M ( compte tenu de la modification ci-dessus), mais renvoie correctement le résultat final (dans cet exemple, le coût minimum de partitionnement de s en k varie de 17 , et la matrice D est utilisée pour imprimer la liste des diviseurs de positions qui mènent à cet optimum) .

import math
def partition(s, k):
# compute prefix sums
n = len(s)
p = [0 for _ in range(n)]
m = [[0 for _ in range(k)] for _ in range(n)]
d = [[0 for _ in range(k)] for _ in range(n)]
for i in range(n):
p[i] = p[i-1] + s[i]
# initialize boundary conditions
for i in range(n):
m[i][0] = p[i]
for i in range(k):
m[0][i] = s[0]
# Evaluate main recurrence
for i in range(1, n):
"""
omit calculating the last M's column cells 
except for the sought minimum cost M[N][K]
"""
if i != n - 1:
jlen = k - 1
else:
jlen = k
for j in range(1, jlen):
"""
- computes the minimum-cost partitioning  of the set {S1,S2,.., Si} into j partitions .
- this part should be investigated more closely .
"""
#
m[i][j] = math.inf
# This loop needs to be traced to understand it better
for x in range(i):
sup = max(m[x][j-1], p[i] - p[x])
if m[i][j] > sup:
m[i][j] = sup
# record which divider position was required to achieve the value s
d[i][j] = x+1
return s, d, n, k
def reconstruct_partition(S, D, N, K):
if K == 0:
for i in range(N):
print(S[i], end="_")
print(" | ", end="")
else:
reconstruct_partition(S, D, D[N-1][K-1], K-1)
for i in range(D[N-1][K-1], N):
print(S[i], end="_")
print(" | ", end="")
# MAIN PROGRAM
S, D, N, K = partition([1, 2, 3, 4, 5, 6, 7, 8, 9], 3)
reconstruct_partition(S, D, N, K)

InformationsquelleAutor mabbessi

Vous devez vous connecter pour publier un commentaire.