Contenu du cours
Greedy Algorithms using Python
Greedy Algorithms using Python
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.
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
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.
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessousMerci pour vos commentaires !
Passez à un bureau pour une pratique réelleContinuez d'où vous êtes en utilisant l'une des options ci-dessous