A BACKTRACKING AND BRANCH & BOUND ALGORITHM USING KNAPSACK PROBLEM
Alagappa Institute of Skill Development & Computer Centre,Alagappa University, Karaikudi, India.15 -16 February 2017. IT Skills Show & International Conference on Advancements In Computing Resources (SSICACR-2017)
This paper describes what is termed as backtracking using maze problem and what is termed as branch & bound using Hamiltonian cycle. A backtracking algorithm is a recursive method of building up feasible solutions to a combinatorial optimization problem one step at a time. A backtracking algorithm is an exhaustive search, that is, all feasible solutions are considered and it will thus always find the optimal solution. It is a generalized of the ordinary maze problem to find a path from start from finish. One or more sequences of choices may lead to a solution. Many of the maze problem can be solved with backtracking. Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration. The algorithm explores branches of this tree, which represent subsets of the solution set. Using a Hamiltonian cycle a path which passes once and exactly once through every vertex of G (G can be digraph).
 T.H.Cormen, C.E.Leiserson and R.L.Rivest, Introduction to algorithms, I ITPress, Cambridge MA,1996.  Levitin, Anany. The Design and Analysis of Algorithms. New Jersey: Pearson Education Inc., 2003.  Different Approaches to Solve the 0/1 Knapsack Problem. Maya Hristakeva, DiptiShrestha; Simpson Colleges  S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani.Algorithms https://en.wikipedia.org/wiki/Hamiltonian_path_problem https://en.wikipedia.org/wiki/Maze_solving_algorithm