problème Jug eau dans Die Hard 3 dans un graphique

Question

je ne suis pas trop sûr de savoir comment mettre en œuvre cette ...

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

J'ai besoin de créer des nœuds pour tous les déplacements possibles (remplir, vider, verser). Après j'ai besoin de trouver le chemin le plus court vers la solution. Mais j'ai du mal à créer ce graphique. J'utilise ma propre liste/noeud lié.

Toute aide avec l'algorithme pour créer ce graphique serait géniale. Merci. Ex) donné 3 gallons, 5 gallons. Obtenez 4 gallons dans la cruche de 5 gallons. J'ai besoin de créer un graphique de tous les mouvements possibles pour obtenir 4 gallons. Chaque gallon différent représente un noeud différent.

Happy Thanksgiving =)

Answer 1

On peut supposer que chaque noeud détient deux entiers positifs - nombre de gallons dans le pot 3-gal, le nombre de gallons dans le bol 5-gal. Arcs, aka bords (dirigés), sont les «coups» (et étiquetés avec l'action que l'arc représente) - apparemment, vous avez également un robinet sans nom à portée de main, puisque vous pouvez toujours remplir l'un ou l'autre des cruches; vous pouvez également toujours vider un pichet (de sorte que vous avez également un évier); et ainsi de suite (d'autres mouvements impliquent tous le mouvement de l'eau d'un gallon à l'autre, jusqu'à ce que le premier est vide, ou le second est plein). Il vaut sans doute mieux éviter de générer des arcs légaux mais inutiles ("bouger"), comme "remplir" un pichet déjà plein, ou défaire un mouvement que vous venez de faire (comme vider un pichet que vous venez de remplir du robinet), l'ajout de tels arcs signifiera seulement un peu plus de travail, pas une solution incorrecte. Commencez par (0, 0) - les deux pichets pleins, comme vous l'avez fait au début. Il est clair que les deux arcs d'ici vous amènent à (3, 0) et (0, 5) respectivement (remplissant l'un ou l'autre du robinet), et ainsi de suite. J'espère que cela t'aides!

Answer 2

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

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

Et c'est parti. Placez les états dans la table de recherche et vérifiez qu'aucune solution ne sera répétée. Ceci est également condition d'arrêt.

taille

de table de recherche est A * B, et hachage de calcul est juste un vol * (B) + B

Dans le tableau [A vol * (B) + B] sauver de la position de sorcière vous êtes venu. Faire l'initialisation des éléments de table sur -1 (je suppose que le premier index est 0 dans votre langue)