Le problème de la cruche d'eau dans Die Hard 3 en un graphique.

Question

Je ne suis pas trop sûr de savoir comment mettre cela en place...

Je dois créer un graphe dirigé pondéré basé sur le problème de la cruche d'eau du film Die Hard 3 ( http://www.wikihow.com/Solve-the-Water-Jug-Riddle-from-Die-Hard-3 ).

Je dois créer des nœuds pour tous les mouvements possibles (remplir, vider, verser). Ensuite, je dois trouver le chemin le plus court vers la solution. Mais j'ai des difficultés à créer ce graphe. J'utilise ma propre liste de liens/noeuds.

Toute aide concernant l'algorithme permettant de créer ce graphique serait la bienvenue. Merci.

ex) donné 3 gallons, 5 gallons. Obtenir 4 gallons dans la cruche de 5 gallons. Je dois créer un graphe de tous les mouvements possibles pour arriver à 4 gallons. Chaque gallon différent représente un nœud différent.

Joyeux Thanksgiving =)

Answer 1

On peut supposer que chaque nœud contient deux nombres entiers positifs : le nombre de gallons dans la cruche de 3 gallons, le nombre de gallons dans la cruche de 5 gallons. Les arcs, ou arêtes (dirigées), sont les "mouvements" (et sont étiquetés avec l'action que l'arc représente) -- apparemment, vous avez aussi un robinet sans nom à portée de main, puisque vous pouvez toujours remplir l'une ou l'autre des cruches ; vous pouvez aussi toujours vider une cruche (vous avez donc aussi un évier) ; et ainsi de suite (les autres mouvements impliquent tous de déplacer l'eau d'un gallon à l'autre, jusqu'à ce que le premier soit vide, ou le second plein). Il est sans doute préférable d'éviter de générer des arcs ("mouvements") légaux mais inutiles, comme "remplir" une cruche qui est déjà pleine, ou annuler un mouvement que vous venez de faire (comme vider une cruche que vous venez de remplir au robinet), bien que l'ajout de tels arcs ne signifie qu'un peu plus de travail, et non une solution incorrecte.

Commencez donc par (0, 0) - les deux cruches sont pleines, comme au début. De toute évidence, les deux arcs qui partent d'ici vous mènent respectivement à (3, 0) et (0, 5) (en remplissant l'un ou l'autre à partir du robinet), et ainsi de suite. J'espère que cela vous aidera !

Answer 2

À chaque étape, vous avez 6 options différentes

1.A=complet
2.B=complet
3.A->B
4.B->A
5.A=0
6.B=0

Et voilà. Mettez les états dans la table de consultation et vérifiez qu'aucune des solutions ne se répète. C'est aussi une condition d'arrêt.

la taille de la table de consultation est A * B, et le calcul du hachage est juste A*vol(B)+B

Dans le tableau [A*vol(B)+B], sauvegardez à partir de la position d'où vous venez. Initialiser les éléments du tableau à -1 (je suppose que le premier index est 0 dans votre langage).