Greedy Algorithm Question, Image that there is a new computer game called DownRi
ID: 3729629 • Letter: G
Question
Greedy Algorithm Question, Image that there is a new computer game called DownRightMOnsterous.
Problem 15. (10 points) Imagine that there is a new computer game called DowNRIGIITMONSTEROUS. The playing area is shaped like an NxN checkerboard and some of the squares contain monsters (that you need to kill). You begin in the top left corner and take steps either down or to the right until you reach the bottom right corner. If you step onto a square with a monster, you kill the monster. If you reach the bottom right square and all monsters have been killed then you win. If you reach the bottom right square and there are monsters still alive you are moved back to the top left corner and need to kill the remaining monsters. Your goal is to kill all of the monsters in the minimum number of transits of the board. For example, this 5x5 board will require 2 transits of the board. But this 5x5 board only requires 1 transit of the board. Describe a greedy algorithm to minimize the number of transits necessary to kil all the monsters. Prove that your algorithnm is optimal.Explanation / Answer
A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage.with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
Greedy algorithms are simple and straightforward.Popular for obtaining optimal solution
A greedy algorithm is similar to a dynamic programming algorithm, but the difference is that solutions to the sub problems do not have to be known at each stage,
instead a "greedy" choice can be made of what looks best for the moment.
greedy At each step choice made should be,
• feasible – satisfy problem constraints
• locally optimal – among all feasible sol. The best choice
• particular choice is made then shouldn’t change.
greedy algorithm consist of four function:-
GREEDY ALGORITHM:-
Algorithm Greedy (a,n)
//D is domain that contains the n inputs.
{
solution:=0; //initially assume.
for I =1 to n do
{
S:=Select(a);
if Feasible( solution, s) then
solution:=Union(solution,s);
}
return solution;
}
Characteristics of greedy algorithm:-
greedy algorithm work by making the decisiob that seems most promising at any moment. it never reconsiders this decision.
greedy algorithm and the probleam that can be solved by greedy algo are characterized by most or all of the following feachers.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.