Is Greed the best choice?

Question

Argue whether or not you would apply Greedy technique to the following problems:

a. Chess

b. Sorting

c. Shortest path computation

d. knapsack

Explain the reasoning behind each.

Answer 1

I think the first question we should ponder is if these problems have the greedy choice property.  For example, Chess does not (no such function known at the moment) that you can maximize.  Knapsack could, especially if fractional values allowed.

Answer 2

a) Chess - No, because there are no currently known moves that can be maximized.
b) Sorting - Yes, Greeding is a popular choice in sorting algorithms. We can give an example of selection sort where we find the smallest element in every step.
c) Shortest path computational - Yes and No, because the problems with positive cost when traveling through the edge(positive edge weight) like Dijkstra's algorithm can benefit from a greedy algorithm while the problems with negative cost when traveling from an edge( negative edge) weight can have a non-optimal solution when used greedy.
d)knapsack - Yes, it would work because our greed would be to choose the item with the highest weight-to-value ratio. the method would be specifically helpful if fractional values are allowed

Answer 3

a. Chess would not apply greedy technique. Chess involves a large state space, and making greedy choices at each move without considering future consequences is unlikely to lead to a winning strategy.

b. Sorting would apply greedy technique. In each sort step, we will use greedy technique to ensure each step is better.

c. Sometimes it apply and sometimes it will not apply. It is applicable in scenarios where a locally optimal choice at each step leads to a globally optimal solution. However, in more general cases like weighted graphs, more sophisticated algorithms like Dijkstra's is more preferred.

d. It is applied. knapsack problem is a very classic optimization problem. Greedy algorithm allow us to choose the higher ratio of weight/value subjects.

Answer 4

a.) Chess - The current best step may or may not lead to the global best solution. Because there are many possibilities where opponent can tackle our best step. We need to check all the possibilities. So, greedy may not be optimal/ applicable.

b.) Sorting - Yes, Greedy is applicable here but not necessarily encouraged. For ex- Selection Sort. Where the local solution leads to the global solution. But the time complexity is high(O(n²)). Using other approaches may give optimal ways to sort.

c.) Shortest path computation - Some problems like MST, Dijkstra's algorithm which are quite similar to Shortest path computation applies Greedy approach.

d.) Knapsack - Incase of fractional Knapsack we consider Max {Value/Weight} at each step which gives an optimal solution but for 0/1 Knapsack, dynamic programming gives optimal solution. So, for Fractional Knapsack, Greedy method is applicable.