Question

Hamiltonian circuit can be most perfectly related with:

A. Greedy approach

B. Dynamic programming

C. Backtracking

D. Branch and bound

Answer 1

Ans C)Backtracking

Comments

little bit understood..:-/

not getting hw r u explaining backtracking here

---

Actually I made it in Paint. The figure. If u know d basic idea of backtracking,we backtrack our steps to root in case d solution is not obtained. Similarly in d above graph {0,1,2,4,3,0) is d Hamiltonian path. It's representation I've shown using backtracking. We go back to d root node i.e. d zero th node.And then from there move towards dat path which generates d solution. Now is it K?

---

Hamiltonian path is not wat I've mentioned. But it cud be a different one as well {0,3,4,2,1,0}. You can generate d backtracking solution for this one as well. :)

Answer 2

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage^[1] with the hope of finding a global optimum.  reference -https://en.wikipedia.org/wiki/Greedy_algorithm

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions

Backtracking Algorithm
Create an empty path array and add vertex 0 to it. Add other vertices, starting from the vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If we find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return false

Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems

So Hamiltonian related with Backtracking