Difference between live node and e node and dead node in branch and bound
Answers
Answered by
10
Branch and bound is a systematic method for solving optimization problems
B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.
B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.
Answered by
4
Answer:E-node(Expanded node) represents that node which has been expanded in state space tree.
Live node represent that node which is been currently expanding.
Dead node represent the node which cannot be expanded further.
Explanation:
Similar questions