Introduction of algorithm

Reference: www.cnblogs.com/steven_oyj/…

Greedy algorithm (greedy algorithm) refers to the algorithm that takes the best or optimal (i.e., the most favorable) choice in each step of the problem solving process, so as to lead to the best or optimal result.

Greedy algorithms often get results that are not optimal (sometimes optimal), but are relatively approximate (close to) the optimal solution.

  • Greedy algorithm has no fixed algorithm solution frame, the key of the algorithm is the choice of greedy strategy, according to different problems to choose different strategies.

  • It must be noted that the choice of strategy must have no aftereffect, that is, the choice of a state will not affect the previous state, only related to the current state, so the greedy strategy must be carefully analyzed to meet the no aftereffect.

For example, the shortest path problems (breadth-first, Dikstra) introduced above all belong to greedy algorithms, but in the choice of their problem strategy, just can get the optimal solution.

The basic idea

The basic solution idea is as follows:

1. Build a mathematical model to describe the problem

2. Divide the problem into subproblems

3. Solve each subproblem to obtain the local optimal solution of the subproblem

4. Synthesize the local optimal solution corresponding to the sub-problem into an approximate optimal solution of the original whole problem

case

The example here is from the book “Diagrams of Algorithms”

Case a

Interval scheduling problem:

Suppose you have the following classes and want as many of them as possible in one classroom:

course The start time The end of time
The fine arts 9AM 10AM
English 9:30AM 10:30AM
mathematics 10AM 11AM
The computer 10:30AM 11:30AM
music 11AM 12PM

This seems like a lot to think about, but the algorithm is actually very simple:

2. Next, choose the class that starts after the first class and finish the earliest class, which will be the second class in the classroom.

If you do this again and again, you’ll find the answer, and the selection strategy here is to sort the class that ends the earliest and doesn’t conflict with the last class, because you always choose the class that ends the earliest, so there’s more time left, so you can schedule more classes.

The choice of each lesson is the local optimal solution within the strategy (with the most time left), so the final result is also the approximate optimal solution (in this case, the optimal solution). (The code implementation of this case is a simple time traversal comparison process)

Case 2

Backpack problem: There is a backpack with a capacity of 35 pounds and the following items are available

items The weight of the The price
The guitar 15 1500
The stereo 30 3000
Laptop computer 20 2000
display 29 2999
pen 1 200

The goal to achieve is to load the maximum total value of the backpack, and the weight does not exceed.

It’s easy to count so there are only three items, but it could be tens of thousands.

As above, greedy algorithm is used, because the total value is the largest, the most expensive is loaded each time, and then the next most expensive is loaded, the selection result is as follows:

Option: Stereo + pen, total value 3000 + 200 = 3200

Not optimal: Guitar + laptop, total value 1500 + 2000 = 3500

Of course, the selection strategy is sometimes not very fixed, and may be as follows:

(1) Select the one with the maximum value each time, and the final weight does not exceed:

Option: Stereo + pen, total value 3000 + 200 = 3200

(2) Select the maximum weight each time, and the final weight does not exceed (it may be preferred if the maximum weight is required) :

Option: Stereo + pen, total value 3000 + 200 = 3200

(3) Choose the largest unit value (price/weight) each time, and the final weight does not exceed:

Option: Pen + monitor, total value 200 + 2999 = 3199

The final result above is not the optimal solution. In this case, the greedy algorithm cannot get the optimal solution, but can only get the approximate optimal solution, which is also one of the limitations of the algorithm. If the optimal solution is needed in this kind of problem, the dynamic programming algorithm can be adopted (for subsequent updates, you can also follow my official account for the first time to obtain updated information).

Case 3

Set coverage problem:

Assume that there are paid radio stations in the table below, and the areas that radio stations can cover. How to select the least number of stations so that all areas can receive the signal.

Radio station Coverage area
K1 ID,NV,UT
K2 WA,ID,MT
K3 OR,NV,CA
K4 NV,UT
K5 CA,AZ
. .

How to find the set of radio stations covering all regions, sounds easy, but implementation is complicated, use the exhaustive method to implement:

(1) List the set of every possible radio station, which is called the power set. Assuming there are n radio stations in all, there are 2n radio stations in all

(2) Of these sets, the smallest set covering the entire region is selected, assuming that n is absent, but when n is very large, assuming that 10 subsets can be computed per second

Number of radio stations n The number of subsets is 2n Time required
5 32 3.2 seconds
10 1024 102.4 seconds
32 4294967296 13.6 years
100 1.26 * 100 after DHS 4 x10 squared after years

At present, there is no algorithm that can quickly calculate the prepared value, while greedy algorithm can get a very close solution with high efficiency:

Select strategically because the minimum set needs to cover all regions:

(1) Select a station that covers the most uncovered areas, even if it includes some covered areas. (2) Repeat the first step until you have covered all areas

This is a approximation algorithm. When it takes too long to obtain the exact optimal solution, an approximation algorithm can be used. The merits and demerits of the approximation algorithm can be judged by the following criteria:

  • How fast
  • How close the approximate solution is to the optimal solution

In this example, greedy algorithm is a good choice, not only fast, the running time of this example O(n²), the worst case, suppose n radio stations, each radio station covers 1 region,n regions, the total need to query n*n=O(n²), implementation can see the Java code implementation

Number of radio stations n The number of subsets is 2n Exhaustion takes time Greedy algorithm
5 32 3.2 seconds 2.5 seconds
10 32 102.4 seconds 10 seconds
32 32 13.6 years 102.4 seconds
100 32 4 x10 squared after years 1000 seconds

At this point, the algorithm selects K1, K2, K3, and K5, which covers all regions, and may not be K2, K3,K4, and K5 as expected (it may be cheaper, easier to implement, etc.).

NP complete problem

Case 4:

Travel agent problem

Suppose a travel agent needs to start from one of the following three cities, how to plan the route to get the shortest route of the trip.

There are 3! (factorial)=6 possible scenarios:

A->B->C
A->C->B
B->A->C
B->C->A
C->A->B
C->B->A
Copy the code

The biggest difference between this and the previous shortest path algorithms (breadth search, Dikstra, Behrman-Ford) is that there is no fixed source point (starting point), every node may be the source point, and need to pass through every node, so if the exhaustive rule has to find out every possibility and compare.

When the number of cities is n, the probability is n! , assuming one route is judged per second

The number n The total number of n! Exhaustion takes time
5 120 120 seconds
10 32 42 days

By using the greedy algorithm, starting from A city randomly, such as A, starting from the nearest city that has not been to, the approximate optimal solution can be obtained.

Compare n-1 cities for the first time and n-2 cities for the second time… N-1 comparison 1 city has no comparison for the NTH time

0 + 1 + 2 + 3 +… Material + (n – 1) O (n squared / 2)

The number n The total number of n! Exhaustion takes time Greed takes time
5 120 120 seconds 12.5 seconds
10 32 42 days 50 seconds

Similar to the set coverage problem and travel salesman problem mentioned above, all belong to NP-complete problems, and there is no solution to get the optimal solution quickly in the field of mathematics. Greedy algorithm is the most suitable for dealing with such problems.

How to judge is NP-complete problem:

1. When there are fewer elements, the speed is generally very fast, but as the number of elements increases, the speed will become very slow 2. The case involving the need to calculate the comparison of “all combinations” is usually NP-complete problem 3. You can’t break it down into small problems. You have to consider all possible scenarios. This may be NP-complete problem 4. If the problem involves sequences (such as city sequences in the travel salesman problem) and is difficult to solve, it may be NP-complete problem 5. If the problem involves sets (such as a radio station set) and is difficult to solve, it may be NP-complete problem 6. If the problem can be converted to a set covering problem or a traveling salesman problem, it must be NP-complete

summary

1. Greedy algorithms can search for local optimal solutions and try to obtain global optimal solutions in this way

2. The obtained solution may be approximately optimal, but it may also be optimal (interval scheduling problem, shortest path problem (breadth-first, Dikstra))

3. For complete NP problems, there is no quick solution to get the optimal solution

4. Faced with NP-complete problems, the best approach is to use approximate algorithms

5. Greedy algorithms (approximate algorithms) are easy to implement and efficient in most cases

Java implementation

Greedy algorithm needs to select corresponding strategies according to specific problems to achieve, so here we only take the set coverage problem as an example:

Public class Greedy {public static void main(String[] args){@author Administrator ** / public class Greedy {public static void main(String[] args){ // Initialize station information HashMap<String,HashSet<String>> broadcasts = new HashMap<String,HashSet<String>>(); broadcasts.put("K1", new HashSet(Arrays.asList(new String[] {"ID"."NV"."UT"})));
		broadcasts.put("K2", new HashSet(Arrays.asList(new String[] {"WA"."ID"."MT"})));
		broadcasts.put("K3", new HashSet(Arrays.asList(new String[] {"OR"."NV"."CA"})));
		broadcasts.put("K4", new HashSet(Arrays.asList(new String[] {"NV"."UT"})));
		broadcasts.put("K5", new HashSet(Arrays.asList(new String[] {"CA"."AZ"}))); AllAreas = new HashSet(arrays.asList (new String[] {"ID"."NV"."UT"."WA"."MT"."OR"."CA"."AZ"})); List<String> selects = new ArrayList<String>(); HashSet<String> tempSet = new HashSet<String>(); String maxKey = null;while(allAreas.size()! =0) { maxKey = null;for(String key : broadcasts.keySet()) { tempSet.clear(); HashSet<String> areas = broadcasts.get(key); tempSet.addAll(areas); RetainAll (allAreas); // Find the intersection of 2 sets, tempSet is assigned to the contents of the intersection, so use the temporary variable tempset.retainall (allAreas); // If the collection contains more regions than the original collectionif(tempSet.size()>0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) { maxKey = key; }}if(maxKey ! = null) { selects.add(maxKey); allAreas.removeAll(broadcasts.get(maxKey)); } } System.out.print("selects:"+ selects); }}Copy the code
The following information is displayed after the main method is executed: SELECTS :[K1, K2, K3, K5]Copy the code

The public,

If you are interested, you can follow the wechat public number and make progress together