J'étudie comment une approche de conception par programmation dynamique est liée aux propriétés combinatoires sous-jacentes des problèmes.
Pour cela, je me penche sur l'instance canonique des problème de changement de pièces : Soit S = [d_1, d_2, ..., d_m] y n > 0 être un montant demandé. De combien de façons pouvons-nous additionner jusqu'à n en n'utilisant rien d'autre que les éléments de S ?
Si nous suivons un Programmation dynamique Pour concevoir un algorithme permettant de résoudre ce problème avec une complexité polynomiale, nous commencerions par examiner le problème et la façon dont il est lié à des sous-problèmes plus petits et plus simples. Cela permettrait d'obtenir un relation récursive décrivant un pas inductif représentant le problème en termes de solutions à ses sous-problèmes connexes. On peut alors mettre en œuvre soit un mémorisation technique ou une tabulation pour mettre en œuvre efficacement cette relation récursive de manière descendante ou ascendante, respectivement.
Une relation récursive pour résoudre cette instance du problème pourrait être la suivante (syntaxe Python 3.6 et indexation basée sur 0) :
def C(S, m, n):
if n < 0:
return 0
if n == 0:
return 1
if m <= 0:
return 0
count_wout_high_coin = C(S, m - 1, n)
count_with_high_coin = C(S, m, n - S[m - 1])
return count_wout_high_coin + count_with_high_coinCette relation récursive donne un nombre correct de solutions mais sans tenir compte de l'ordre. Cependant, cette relation :
def C(S, n):
if n < 0:
return 0
if n == 0:
return 1
return sum([C(S, n - coin) for coin in S])produit une quantité correcte de solutions tout en respectant la commande.
Je m'intéresse à la capture de motifs combinatoires plus subtils par le biais d'une relation de récursion qui peut être optimisée par la mémorisation/tabulation.
Par exemple, cette relation :
def C(S, m, n, p):
if n < 0:
return 0
if n == 0 and not p:
return 1
if n == 0 and p:
return 0
if m == 0:
return 0
return C(S, m - 1, n, p) + C(S, m, n - S[n - 1], not p)donne une solution qui ne tient pas compte de l'ordre mais qui ne compte que les solutions ayant un nombre pair de sommets. La même relation peut être modifiée pour tenir compte de l'ordre et compter le nombre pair de sommets :
def C(S, n, p):
if n < 0:
return 0
if n == 0 and not p:
return 1
if n == 0 and p:
return 0
return sum([C(S, n - coin, not p) for coin in S])Cependant, que se passe-t-il si nous avons plus d'une personne entre lesquelles nous voulons partager les pièces ? Disons que je veux partager n entre 2 personnes, à condition que chaque personne reçoive le même nombre de pièces, quelle que soit la somme totale que chacune reçoit. Sur les 14 solutions, seules 7 comprennent un nombre pair de pièces, de sorte que je puisse les répartir équitablement. Mais je veux exclure les attributions redondantes de pièces à chaque personne. Par exemple, 1 + 2 + 2 + 1 y 1 + 2 + 1 + 2 sont des solutions différentes lorsque l'ordre est important, MAIS elles représentent la même répartition des pièces entre deux personnes, à savoir la personne B obtiendrait 1 + 2 = 2 + 1 . J'ai du mal à trouver une récursion pour compter les splits de manière non redondante.
