Explain the Greedy Structure algorithm. Give an example in which the Greedy technique fails to deliver an optimal solution.
A greedy structure algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage[1] with the hope of finding the global optimum.
For example, applying the greedy strategy to the traveling salesman problem yields the following algorithm: "At each stage visit the unvisited city nearest to the current city". In general, greedy algorithms are used for optimization problems.
In general, greedy algorithms have five pillars:
A candidate set, from which a solution is created
A selection function, which chooses the best candidate to be added to the solution
A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
An objective function, which assigns a value to a solution, or a partial solution, and
A solution function,
______ ______ ___ __________ ______ _______ _____.
_______ _________ _____ ___ _____ ___ __________.
_______ _________ ____ _________ _____ ________ ___ _________ ____.
__________ ___ _____ ________ ____ ______ __________ ____.
______ _____ ____ ______ _____ ___ _________ _______ _________.
_______ ________ ___ ______ ______ ________ _______ ________ ______ ________ _____.
__________ ____ ______ __________ ________ ______ ______.
____ ________ _____ _________ __________ ____.
____ _________ _______ __________ _____.
_______ __________ _________ _________ _______.
__________ _________ ____ ________ _________ __________ __________ ___ ___.
______ ______ __________ _________ _________ __________ ____ ____ _________ ________ ________ ________.
________ ____ ___ _____ ___ _______ ___ _________ _______ _____ ________.
______ __________ _________ _______ ____ ________.
_____ ___ ______ ________ ______ ________ _______ ________ _______.
_____ ___ __________ _______ _________.
______ ______ _____ ________ __________ ________ ____.
_____ ________ ______ ____ _________ ____ __________ ______ ______ ________ ______.
__________ _____ __________ ___ __________ ____ ____ ______ __________ ______.
_______ _________ ___ ___ __________ ________ _________ _________ ___.
______ ___ _________ ____ ______ ___ _____.
___ _____ ___ _______ ___ _______ __________.
_________ ____ ________ _________ ___ ______ ____.
________ _____ ____ _________ ______ __________ ________ _______.
______ ______ __________ ____ ________.
__________ _________ _________ _______ _____ ____ _________ ____ ______ ________ _________.
______ ___ _____ __________ ______ _______ _______ ____ ____ ___.
______ __________ __________ ________ _____ ________ ________.
_________ __________ _______ ___ _________ _____ _____.
________ _________ _______ _______ ______ _______.
________ __________ __________ _____ _____ ______ ______ __________.
_____ _______ __________ ___ ____.
____ _____ _____ ______ _____ __________ _______ __________ _____ __________ ____.
___ ___ _____ _______ _______.
_______ _____ ______ __________ _____ ____ ________ ______ ____ _______.
________ ______ ___ ________ ________ _______ ______ ___.
_____ _______ _________ ________ ____ ___ ________ ___.
________ ____ ___ _______ ________ ________.
__________.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required