Comment implémenter un arbre d'espaces d'états?

Question

J'essaie de résoudre un problème de type sac à dos de MIT OCW. Son ensemble de problème 5.

J'ai besoin d'utiliser l'algorithme de branche et lié pour trouver les états optimaux. J'ai donc besoin de mettre en place un arbre d'état-espace. Je comprends l'idée de cet algorithme, mais je trouve que ce n'est pas si facile à implémenter.

Si je trouve un nœud où le budget ne suffit pas, je devrais arrêter ici. Dois-je ajouter un attribut à chaque nœud d'arbre? Lorsque j'ajoute un nœud, je devrais partir d'un nœud dont la borne supérieure est la plus grande. Comment puis-je trouver un tel noeud? Dois-je traverser tous les nœuds avant d'ajouter chaque nœud? Ou pourrais-je sauvegarder du var pour l'aider?

Avez-vous une idée? Pourriez-vous l'implémenter en python?

Answer 1

J'espère bien compris le problème, sinon s'il vous plaît me diriger :)
(désolé pour la confusion découlant des deux significations différentes de « l'état »)

Vous pouvez bien sûr ajouter l'attribut dans la node (ça fait partie de l'état!), car c'est une toute petite quantité de données. Notez qu'il n'est pas obligatoire de le sauvegarder, car il est implicitement présent dans le reste de l'état (compte tenu des états que vous avez déjà choisis, vous pouvez le calculer). Personnellement, j'ajouterais l'attribut, car il ne sert à rien de le calculer plusieurs fois. Sur la deuxième question: IIRC, lorsque vous ajoutez des nœuds, vous n'avez pas besoin de traverser TOUT l'arbre, mais seulement la frange (c'est-à-dire l'ensemble des nœuds qui n'ont pas de descendants - à ne pas confondre avec le niveau le plus profond de l'arbre). Puisque vous êtes à la recherche d'une limite supérieure, (et puisque vous utilisez seulement les coûts positifs), il y a trois cas où vous recherchez le nœud avec la valeur la plus élevée:

• sur la dernière étape ajouté au noeud qui avait la valeur la plus élevée, donc le noeud que vous venez d'ajouter a maintenant la valeur la plus élevée
• sur la dernière étape en ajoutant le vous avez dépassé le budget, donc vous avez dû exclure l'option. essayez d'ajouter un autre état
• Il n'y a plus d'états à essayer d'ajouter pour créer un nouveau noeud. Cette branche ne peut pas aller plus loin. Regardez la frange pour la plus grande valeur dans les autres noeuds