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)

Format: Volume 5, Issue 1, No 21, 2017

Copyright: All Rights Reserved ©2017

Year of Publication: 2017

Author: Dr.V.Selvi,G.Sadhana

Reference:IJCS-257

View PDF Format

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_algorithm

Keywords

Backtracking, branch&bound, maze, Hamiltonian, optimization.

This work is licensed under a Creative Commons Attribution 3.0 Unported License.   

TOP
Facebook IconYouTube IconTwitter IconVisit Our Blog