////////////////////////////////////////////////////////////////////////////////////////////////////
Backtracking Algorithm!
Backtracking algorithm consider all cases which are possible,
Checking each case is whether satisfied with the condition, backtracking determines whether or not there be a solution.
And because it searches all cases that can occur, solution always exists.
Upon reaching a dead end during finding a solution, then return to the latest turning point and go to where it is not search.
Example
{ 1 }
n-Queens problem
Queen which is placed on the chessboard can attack any piece which is placed in the same column, row, diagonal.
So, we place the Queen on the place where any queens cannot attack.
-
Place the Queen in each column. In this case, put the Queen in the place where Queen does not attack each other.
-
If there is no place anymore to put is, change the place of the Queen as return to Just before line.
-
Repeat the step2, until find the solution
{ 0 }
GROUP PROJECT
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
Calculate the calories for a day
This program is calculating the minimum calories with eating 4 nutrient (carbohydrate, protein, fat, vitamin(this is assuming) )
-
Input the calories for one day. then calculate the each nutrient calories.
carbohydrate 30%, protein 40%, fat 10%, vitamin 20% -
And enter the 4 food
Suppose to each food has 4 nutrient, enter the each nutrient's calories. -
Any of the four nutrients must be eaten without missing.
Therefore, Select the most minimum calories among those that contain four nutrients. -
Then, print what nutrients do lack and what nutrients do overbalance about calories for one day and how many the calories lack or overbalance.
Other algorithms
-
Solving maze
-
Map-coloring
-
Hamoltonian cycle
-
Terminology
Map-coloring
BRANCH-and-BOUND
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////
In the case of Backtracking, need to consider the number of all cases, So, it is often inefficient. Therefore, a Branch and Bound be enhanced these concepts.
Branch and Bound, as an algorithm for choosing the "best case", defines the range, where at least this degree is likely to be the answer must(Bound), and rest is branched for searching the solution.
Assignment problem
{ 1 }
It is a program that you want to assign the work not to overlap in people with a minimum of cost.
-
Set the Lower bound.
You can get sum choosing the minimum value for each row or column. that is the Lower bound. -
Fix values in alphabetical order and get minimum sum again.
At this time, the other people are not able to use this fixed value. -
Select the smallest among the total obtained at step2, then fix the value of b.
-
the rest of c and d is in the same way. Then it is solution which has the smallest sum.
SOLUTION