do you know this water jug problem
A one-player minmax search with no heuristic and without iterative deepening is just depth-first search, which isn't really appropriate here.
Given practical alternatives for this class of problem:
Genetic Search
Mini-Max Search
Dijkstra Search
A few other alternatives:
Monte-Carlo Search
Beam Search
Annealing Search
Note that they are all algorithms suited to searching a state space, and they are all more or less just as easily implimented.
They each carry some garantees with them.. Not all of them can guarantee a 'best' solution in finite time. Some guarantee better "worst case" runtime than others.
Some have an implied (but not garanteed) 'early convergence' rate and will likely produce a 'good' but not necessarily 'best' solution while examining only a very small fraction of the search space. The best early convergers are (unfortunately) more oft than not the search strategies with the greatest (sometimes infinite) 'worst case's'
The 'practical meaning' of the garantees and implications are all mediated by the size of the search space.
In this specific case the search space is extremely small and I conclude that the Best(tm) algorithm here would be something of the breadth-first brute-force variety although all the methods here will produce the best solution in only a few steps.
None of these search algorithms require a great deal of effort to impliment although many 'optimisations' can significantly effect code complexity. For instance, adding a transposition table to the minimax algorithm significantly reduces the size of search space. Some of the stochastic search algorithms have parameters which can be tweaked to significantly effect the rate of early and late convergence.
Another big area of A.I. which isnt really applicable here is the Machine Learning methods, such as back propogation neural nets and actor/critic models. You would only apply these algorithms if it is impossible or impractical to trivialy assign a value to a state transition (ie, you want the algorithm to learn the value of each state transition on its way to a step-wise solution)
Genetic Search
Mini-Max Search
Dijkstra Search
A few other alternatives:
Monte-Carlo Search
Beam Search
Annealing Search
Note that they are all algorithms suited to searching a state space, and they are all more or less just as easily implimented.
They each carry some garantees with them.. Not all of them can guarantee a 'best' solution in finite time. Some guarantee better "worst case" runtime than others.
Some have an implied (but not garanteed) 'early convergence' rate and will likely produce a 'good' but not necessarily 'best' solution while examining only a very small fraction of the search space. The best early convergers are (unfortunately) more oft than not the search strategies with the greatest (sometimes infinite) 'worst case's'
The 'practical meaning' of the garantees and implications are all mediated by the size of the search space.
In this specific case the search space is extremely small and I conclude that the Best(tm) algorithm here would be something of the breadth-first brute-force variety although all the methods here will produce the best solution in only a few steps.
None of these search algorithms require a great deal of effort to impliment although many 'optimisations' can significantly effect code complexity. For instance, adding a transposition table to the minimax algorithm significantly reduces the size of search space. Some of the stochastic search algorithms have parameters which can be tweaked to significantly effect the rate of early and late convergence.
Another big area of A.I. which isnt really applicable here is the Machine Learning methods, such as back propogation neural nets and actor/critic models. You would only apply these algorithms if it is impossible or impractical to trivialy assign a value to a state transition (ie, you want the algorithm to learn the value of each state transition on its way to a step-wise solution)
Quote:Original post by Sneftel
You're right, GAs aren't appropriate for this. So I guess NNs must be the way to go. [grin]
No Sneftel... definitely not the right way to go... what this problem needs is a 5 man-year budget. Lots of researchers to ponder the problem... lots of programmers to implement the solution... and plenty of cash for beer and pizza! ;)
Quote:Original post by TimkinQuote:Original post by Sneftel
You're right, GAs aren't appropriate for this. So I guess NNs must be the way to go. [grin]
No Sneftel... definitely not the right way to go... what this problem needs is a 5 man-year budget. Lots of researchers to ponder the problem... lots of programmers to implement the solution... and plenty of cash for beer and pizza! ;)
Are you saying we need a Jugs Comitee? Im in!
Uh I had this problem in an exam at college.
Breadth first search does it. Dijkstra is definitely overkill since there is no associated weight in the transitions (unless you wanted to spend the least amount of water or something) and the problem is not linear so minmax is out. Genetic algorithm? for a (roughly) 12-state FSM? git out! Neural networks? Okay, maybe in a few years of random training you'll happen to walk into the solution by chance.
Doing the graph will give you ALL possible solutions, just find all possible paths to the states where the 4-gallon jug has 2 gallons in it.
PS: two jugs... heh heh
Breadth first search does it. Dijkstra is definitely overkill since there is no associated weight in the transitions (unless you wanted to spend the least amount of water or something) and the problem is not linear so minmax is out. Genetic algorithm? for a (roughly) 12-state FSM? git out! Neural networks? Okay, maybe in a few years of random training you'll happen to walk into the solution by chance.
Doing the graph will give you ALL possible solutions, just find all possible paths to the states where the 4-gallon jug has 2 gallons in it.
PS: two jugs... heh heh
Quote:
I'd just eyeball it... who cares if you get 2.0 or 2.1 gallons?
ha ha ha that's the old "Die Hard" problem. they have like 2 minutes to solve it b4 a bomb goes off. if it's even an ounce over... bomb goes off too so it has to be exact.
after insulting each other with white boy and nigga jokes for 1:40, they all of a sudden solve it in like 20 seconds.
for something like this though trial-and-error (fill this one, empty this one, pour from one to the other) works best, lest ur coding an actual algorithm.
Quote:Original post by gorogoro
Just put it in Prolog and it would find the solution...
Yes, but that's just because Prolog uses breadth-first search anyway (unless you flip the order of the parentheses, and then you're doing depth-first search, and you might end up not finding the solution. Which goes to show that you ought to know what you're doing in Prolog).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement