Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lära Why Greedy? | Greedy Algorithms: Overview and Examples
Greedy Algorithms using Python

Svep för att visa menyn

book
Why Greedy?

Why Greedy?

The aim of the Greedy approach is to reach the optimal solution as fast as possible. It may be optimal in some cases, but we can’t always guarantee that this is the best solution. The greedy search may be faster and simpler than the correct solution, that’s why it is used instead of a more complex one.

The examples are searching optimal paths on graph problems. In The Travelling Salesman Problem, the point is to find the shortest path to connect all the cities, and each city must be visited only once. This problem has no solution, and we can try to apply some greedy approach: for each new city, select the nearest unvisited city, for example. But we can’t prove or guarantee that a found solution will be optimal.

The Dijkstra algorithm from the last chapter reaches the optimal solution, but only for positive-weighted edges, and we can’t guarantee it for negative-weighted edges.

Anyway, the Greedy approach is common-used and applicable, and we’ll solve some problems with it.

Close-packing of equal spheres problem is one of the unsolved problems where the Greedy approach isn’t applicable. There are known solutions only for dimensions of size 1, 2, 3, 8, and 24.

Switch to desktopByt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedan
Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 1

Fråga AI

expand
ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

book
Why Greedy?

Why Greedy?

The aim of the Greedy approach is to reach the optimal solution as fast as possible. It may be optimal in some cases, but we can’t always guarantee that this is the best solution. The greedy search may be faster and simpler than the correct solution, that’s why it is used instead of a more complex one.

The examples are searching optimal paths on graph problems. In The Travelling Salesman Problem, the point is to find the shortest path to connect all the cities, and each city must be visited only once. This problem has no solution, and we can try to apply some greedy approach: for each new city, select the nearest unvisited city, for example. But we can’t prove or guarantee that a found solution will be optimal.

The Dijkstra algorithm from the last chapter reaches the optimal solution, but only for positive-weighted edges, and we can’t guarantee it for negative-weighted edges.

Anyway, the Greedy approach is common-used and applicable, and we’ll solve some problems with it.

Close-packing of equal spheres problem is one of the unsolved problems where the Greedy approach isn’t applicable. There are known solutions only for dimensions of size 1, 2, 3, 8, and 24.

Switch to desktopByt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedan
Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 1. Kapitel 1
Switch to desktopByt till skrivbordet för praktisk övningFortsätt där du är med ett av alternativen nedan
Vi beklagar att något gick fel. Vad hände?
some-alt