Comment peut on commencer à résoudre les problèmes de programmation dynamique?

Je suis confronté à des difficultés à résoudre les probs de DP, quelqu'un peut me dire comment faire pour frapper ces problèmes et où commencer de.

C’est suivre jusqu'à : Quels sont les moyens systématiques pour se préparer à une programmation dynamique?

Réponse

Permettez-moi tout d’abord, mis en avant mon propre processus de pensée pour résoudre les problèmes de DP (depuis son court-métrage) et puis vous consulter d’autres sources.

Remarque : Toutes les personnes déplacées peuvent être (ré) formulées comme la récursivité. L’effort supplémentaire que vous mettez découvrant ce qu’est que la récursivité sous-jacent ira un long chemin en aidant vous à l’avenir les problèmes de DP.

Etape 1: Imaginez que vous êtes Dieu. Ou en tant que tel, vous êtes un surveillant de la troisième personne du problème.
Etape 2: Comme Dieu, vous devez décider quel choix faire. Poser une question de décision.
Etape 3: Afin de faire un choix éclairé, vous devez demander « quelles variables m’aiderait à faire mon choix éclairé? ». Il s’agit d’une étape importante et vous devrez peut-être demander « mais ce n’est pas assez d’informations, afin que plus faire j’ai besoin de » plusieurs fois.
Etape 4: Faire le choix qui vous donne votre meilleur résultat.

Dans ce qui précède, les variables fait allusion à l’Etape 3 sont ce qui est généralement appellent le « état » de votre DP. La décision dans l’Etape 2 est considérée comme « de mon état actuel, ce que tous les États il dépend? »

Confiance en moi : J’ai résolu beaucoup de problèmes de Transports Canada sur DP juste en utilisant la méthode décrite ci-dessus. Il m’a fallu environ max 2 mois à boire cette méthodologie, alors contrairement à tous les conseils de « Continuer à pratiquer » (qui je voudrais compare à brownien), je suggère le ci-dessus 'intuition'.

BTW, si vous pouvez m’identifier par mes conseils, bon pour vous. Le point d’aller anonyme est principalement pour que les gens n’aveuglément upvote quand ils voient « X a ajouté une réponse aux algorithmes:... "

Maintenant pour quelques exemples :

Q. étant donné un tableau, trouver la plus grande somme le long d’un segment contigu de celui-ci.
Assez simple et vous savez la réponse, mais permet de voir ce que les 4 étapes s’élèvent à.
Etape 1: Je suis un surveillant (juste une étape psychologique)
Etape 2: J’ai passer par le tableau et demandez, « la plus grande somme commence à ce point? »
Etape 3: J’ai besoin de savoir quelle est la plus grande somme qui commence au point suivant, afin de décider si elle peut être prolongée ou non.
Etape 4: Je le prolonger soit au point suivant, ou j’ai couper ici: f (i) = max (arr [i], arr [i] + f(i+1)).

L’exemple donné ci-dessus a été démontrée pour moi par un ami et avant sa démonstration (DP la facilité fait), j’étais complètement dérouté par DPs moi-même.

Q. j’ai un ensemble d’emplois de N et deux machines A et B. Job, je prend un [i] sur la machine A et B [i] le temps sur l’ordinateur B. Ce qui est le minimum de temps que je dois finir toutes les tâches?
Etape 1: je suis le surveillant (ce problème se prête plus naturellement à être "Dieu").
Etape 2: J’ai traverser des emplois de 1 à N et de décider sur quel ordinateur pour planifier l’emploi j’ai.
Etape 3: si je planifie le travail sur l’ordinateur A, j’ai alors une charge d’un [i] + la meilleure façon de planifier les travaux restants. Si ses sur B, alors j’ai une charge de B [i] + la meilleure façon de planifier les travaux restants.
Mais attendez ! « meilleure façon de planifier les travaux restants » ne tient pas compte du fait que le travail de l’IE n’interfèrera potentiellement. Ainsi, j’ai besoin d’infact également passer sur les « charges totales » sur chaque machine afin de faire mon choix éclairé.
Donc, j’ai besoin de modifier ma question: "étant donné que l’intensité du courant sur le A est unet sur B est b, et je dois planifier jobs j’à N, ce qui est le meilleur moyen de le faire?"
Etape 4: f (a, b, i) = {max (a, b): J’ai == N + 1, min d’autre (f (a + A [i], b, i + 1), f (a, b + B [i], i + 1): J’ai<= n}.="" final="" answer="" is="" in="" f(0,="" 0,="">

Maintenant, assez d’exemples (réponse devient trop long). Si vous avez des questions DP, vous voudriez que je travaille ma magie sur, affichez-le comme un commentaire:)

S’il vous plaît jeter un oeil sur les réponses de Mimino sur DP: Quels sont les moyens systématiques pour se préparer à une programmation dynamique?


Tags: Programmation informatique, Programmation dynamique (DP), Algorithmes, Programmation concurrentielle, Résolution de problèmes