Now, if you wish to note this as some form of pseudo algorithm you could write it like this: BacktrackingProcedure( someVector, dimension)īacktrackingProcedure(temporatyVector, increaseDimenzsionOfVector) įor the above general algorithm, we would need one condition.
BACKTRACK C8 FULL
When you have partial solution, it will be represented with v0, v1,…,vi, from this partial sub solution you could go back if you find out that it will not lead you toward the vector that will full fill all conditions, that candidate solution would be replaced with v0,v1,…vi-1, but you should know that vi-1 would also be next choice of that same level, or if you see the possibility to reach a final solution you would create vector that has one more element added, in other words it would be v0,v1,…vi,vi+1. This vector is sometimes of certain dimension, for example if you are solving problems of queen placement, but it could be of dimensions that are smaller or different.įor example, if you try to get convex hull or something similar, where dimension is smaller than whole set of points that we are trying to contain in one convex hull, but you would not be able to figure out how many dots would be in that convex hull, or dimensions could be different if you trying to find paths from one node of the graph to another. To create more methodical discussion, we will say that the final vector v0, v1,…,vn is a solution, if it meets all conditions that are set in the beginning of the problem we are solving. If you need to find one solution you could stop, and if you wish to find all possible solutions you could store them and present it after you have checked all possible.įrom this, you would recognize that it is very recursive and it is one of techniques that would be adequate for recursive implementations. In a way, it works similar to permutations of a set but as soon as you see that there is no solution in that partial permutation you backtrack and do more tests with new candidates, in most cases there are nodes of a graph, and you dismiss all sub candidates that could be derived from an unpromising path. In other case, if you find promising candidate it will become part of partial solution that would be used as a part of final solution.
If you end up at the root, you could say that the solution is not available, and that it is not possible to solve problem with the given conditions. If that level does not contain the adequate solution you backtrack one more level. This way you could find one or all possible solutions for problem you are solving.Īt each step you look for a next candidate, and if you notice that this path is not giving you solution, you backtrack one level back, and start with new candidate. You start with possible solution of the problem, and you build on this basis toward the one of solutions that will satisfy all conditions that you are required to meet. So, if you have placed four queens on the chess board, and you have figure out that there is no way to place the fifth one, then you don’t need to place the sixth, or seventh, or eight queen. Because there is no way that you could find a good solution after you have figure out that this partial solution is not promising. If you look for all possible ways to place eight queens on a chess board, you would soon realize that if some configurations are not promising, then you should not check all of its derived solutions.
We could apply backtracking to both programmatic and real life practical problems. One of possible technique to solve a combination problem is to use backtracking. You should reduce the poll of possible candidates as much as you can, and find a better solution that will use less processor time. If you try to solve some combination problem in programming using simple combination approach where you check all possible variations with repetition or permutations of some kind, you would realize that you would have way too many tries that are not necessary.
0 kommentar(er)
