A BACKTRACKING AND BRANCH & BOUND ALGORITHM USING KNAPSACK PROBLEM

IT Skills Show & International Conference on Advancements in Computing Resources, (SSICACR-2017) 15 and 16 February 2017, Alagappa University, Karaikudi, Tamil Nadu, India. International Journal of Computer Science (IJCS) Published by SK Research Group of Companies (SKRGC)

Abstract

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).

References

[1] T.H.Cormen, C.E.Leiserson and R.L.Rivest, Introduction to algorithms, I ITPress, Cambridge MA,1996.

[2] Levitin, Anany. The Design and Analysis of Algorithms. New Jersey: Pearson Education Inc., 2003.

[3] Different Approaches to Solve the 0/1 Knapsack Problem. Maya Hristakeva, DiptiShrestha; Simpson Colleges

[4] S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani.Algorithms [5]https://en.wikipedia.org/wiki/Hamiltonian_path_problem

[6]https://en.wikipedia.org/wiki/Maze_solving_alg orithm

Keywords

Backtracking, branch & bound, maze, Hamiltonian, optimization