How to 'EASILY' and 'EFFECTIVELY' determine in backtracking/dfs, if we had repeat the same pattern/configuration. Do we have to check it only at certain depth?? and how to store the repeated pattern??? and how can we make sure if we encounter this same pattern, e.g at level depth N, it would not prevent a better solution at level depth N+1,N+2.... ???
i'm quite confused, especially the data representation to store the repeating/similar configuration. Several types of this problem such as Game Show Math, or Jugs (with DFS/backtracking).
Please help!!
Bright Answer Required!! Please Help....
Moderator: Board moderators
you're messing two different things, backtracking isn't equal to depth first search. however that's not the point..
you refered to game show math and jugs, well, I solved game show math using backtracking, trying each operation in each depth point, basically what you have to do is recurse avoiding unnecessary or repeated recursions and you'll get to an answer in an average good time. for jugs, although i didn't solve it, you have to try every state in each depth point of the recursion, avoiding, of course, unnecessary recursions.
you should memorize whenever you can, it improves running time a lot, and often saves you from TLE.
The way you store you're data.. well, it depends usually, an array is enough..
you refered to game show math and jugs, well, I solved game show math using backtracking, trying each operation in each depth point, basically what you have to do is recurse avoiding unnecessary or repeated recursions and you'll get to an answer in an average good time. for jugs, although i didn't solve it, you have to try every state in each depth point of the recursion, avoiding, of course, unnecessary recursions.
you should memorize whenever you can, it improves running time a lot, and often saves you from TLE.
The way you store you're data.. well, it depends usually, an array is enough..
be cool...
i know this 1 is a stupid question, but enlight me =P
"how to memorize the recursion result at level N into array and effectively prune when encountering repeated recursion"
somehow i'm still not sure bout the data representation for storing the result....
and effectively checking it if it's a 'repeated' recursion.
i know the concept, but i need more detailed explanation about it.
thanks playerX. anybody else want 2 give some inputs...?
"how to memorize the recursion result at level N into array and effectively prune when encountering repeated recursion"
somehow i'm still not sure bout the data representation for storing the result....
and effectively checking it if it's a 'repeated' recursion.i know the concept, but i need more detailed explanation about it.
thanks playerX. anybody else want 2 give some inputs...?
well... basically you have the backtrack prototype..
void backtrack (int depth)
whenever you initialize a new recursion step you do backtrack(depth+1)
for example, on game show math, what I do is avoiding recursion if the next value in the depth has already been calculated, imagine I am at depth 3 with the value 20, some steps later I am again at depth 3 with the same value twenty, this is unnecessary, so what I did was creating an array r[MAXDEPTH][MAXVALUE] and whenever I was at depth d with value k and in the next step of recursion I had the value k+n (for example), I cheked the flag array for r[depth+1][k+n], if it existed, it was unnecessary to recurse again to the same value. this prunning is enough to get accepted in game show math
void backtrack (int depth)
whenever you initialize a new recursion step you do backtrack(depth+1)
for example, on game show math, what I do is avoiding recursion if the next value in the depth has already been calculated, imagine I am at depth 3 with the value 20, some steps later I am again at depth 3 with the same value twenty, this is unnecessary, so what I did was creating an array r[MAXDEPTH][MAXVALUE] and whenever I was at depth d with value k and in the next step of recursion I had the value k+n (for example), I cheked the flag array for r[depth+1][k+n], if it existed, it was unnecessary to recurse again to the same value. this prunning is enough to get accepted in game show math
be cool...