Shulou(Shulou.com)06/02 Report--

This article Xiaobian introduces in detail for you "how to use Python greedy algorithm to solve the set coverage problem", the content is detailed, the steps are clear, and the details are handled properly. I hope this article "how to use Python greedy algorithm to solve the set coverage problem" can help you solve your doubts.

There is an interesting little case in "algorithm Diagram". The background is a radio program that can be heard by listeners for 50 weeks across the United States, but each radio station may cover multiple states, and there is a fee for each broadcast on one radio station. so, from the point of view of cost, how to broadcast in all states as much as possible is a typical problem of collective coverage. And it's typical in our lives.

For example, if we narrow it down and specify five states, then 50 states have the same algorithm.

States_need = set (["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # pass in an array that is converted to a collection

Some students may have no idea about these states. This abbreviation is just like Beijing for Beijing, Lu for Shandong, and Gansu for Gansu. If you take a closer look, you can see that they are all states in the west.

How to use the greedy algorithm is to choose to cover as many state radio stations as possible, and then gradually narrow the scope. Then the radio stations corresponding to the states with wide coverage will be selected first, and so on.

The implementation of the program specifies a set states_need, which contains all the states, and the corresponding states of each station are implemented through initialized array elements, named according to the order of one, two, three, four, five. Of course, in fact, the arrangement of these elements is not in the order of array names, but in this scenario is kfive,ktwo,kthree,kone,kfour.

And then gradually narrow the scope to converge, the more special point is the operation of the set, using &, you get the intersection, if the union is |, the difference is-

The program code is as follows:

#! / usr/bin/env python# coding:utf-8states_need = set (["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # pass in an array It is converted into a collection # list of available broadcasters stations = {} stations ["kone"] = set (["id", "nv", "ut"]) stations ["ktwo"] = set (["wa", "id", "mt"]) stations ["kthree"] = set (["or", "nv", "ca"]) stations ["kfour"] = set (["nv") "ut"]) stations ["kfive"] = set (["ca", "az"]) print (stations) # the final selected broadcasting station set final_stations = set () while states_need:best_station = Nonestates_covered = set () for station, states_for_station in stations.items (): covered = states_need & states_for_station # to find the intersection print ("states_need:", states_need, "states_for_station:", states_for_station, "covered:" Covered) if len (covered) > len (states_covered): best_station = stationstates_covered = coveredstates_need-= states_coveredfinal_stations.add (best_station) print ("states_needed:", states_need, "best_station:", best_station, "final_stations:", final_stations) print ("- -") print ("Final_stations:", final_stations)

In order to facilitate debugging and get the results of an iteration, I added several output logs for reference.

{'kfive': set ([' ca', 'az']),' ktwo': set (['mt',' id', 'wa']),' kthree': set (['ca',' or', 'nv']),' kone': set (['ut',' id', 'nv']),' kfour': set ([ut', 'nv'])} (' states_need:', set (['wa',' ut']) 'ca',' id', 'mt',' az', 'or',' nv']), 'states_for_station:', set ([' ca', 'az']),' covered:', set (['ca',' az'])) ('states_needed:', set ([' wa', 'ut',' id', 'mt',' or', 'nv']),' best_station:', 'kfive' 'final_stations:', set ([' kfive']))-('states_need:', set ([' wa', 'ut',' id', 'mt',' or', 'nv']),' states_for_station:', set (['mt',' id', 'wa']),' covered:', set (['mt',' id', 'wa']) (' states_needed:', set (['ut']) 'or',' nv']), 'best_station:',' ktwo', 'final_stations:', set ([ktwo',' kfive']))-('states_need:', set ([' ut', 'or',' nv']), 'states_for_station:', set ([' ca', 'or',' nv']), 'covered:', set ([' or']) 'nv']) (' states_needed:', set (['ut',' or', 'nv']),' best_station:', 'ktwo',' final_stations:', set (['ktwo',' kfive']))-('states_need:', set ([' ut', 'or',' nv']), 'states_for_station:', set ([' ut', 'id',' nv']) 'covered:', set ([' ut', 'nv']) (' states_needed:', set (['ut',' or', 'nv']),' best_station:', 'ktwo',' final_stations:', set (['ktwo',' kfive']))-('states_need:', set ([' ut', 'or',' nv']), 'states_for_station:', set ([' ut']) 'nv']),' covered:', set (['ut',' nv']) ('states_needed:', set ([' ut', 'or',' nv']), 'best_station:',' ktwo', 'final_stations:', set ([' ktwo', 'kfive']))-(' states_need:', set (['ut',' or', 'nv']),' states_for_station:'] Set (['ca',' az']), 'covered:', set ([]) (' states_needed:', set (['ut',' or', 'nv']),' best_station:', None, 'final_stations:', set ([' ktwo', None, 'kfive']))-(' states_need:', set (['ut',' or', 'nv']),' states_for_station:'] Set (['mt',' id', 'wa']),' covered:', set ([]) ('states_needed:', set ([' ut', 'or',' nv']), 'best_station:', None,' final_stations:', set (['ktwo', None,' kfive']))-('states_need:', set ([' ut', 'or',' nv']), 'states_for_station:'] Set (['ca',' or', 'nv']),' covered:', set (['or',' nv'])) ('states_needed:', set ([' ut']), 'best_station:',' kthree', 'final_stations:', set ([' ktwo', 'kthree', None,' kfive']))-('states_need:', set ([' ut']), 'states_for_station:'] Set (['ut',' id', 'nv']),' covered:', set (['ut'])) (' states_needed:', set (['ut']),' best_station:', 'kthree',' final_stations:', set (['ktwo',' kthree', None, 'kfive']))-(' states_need:', set (['ut']),' states_for_station:', set (['ut']) 'nv']),' covered:', set (['ut'])) (' states_needed:', set (['ut']),' best_station:', 'kthree',' final_stations:', set (['ktwo',' kthree', None, 'kfive'])-(' states_need:', set (['ut']),' states_for_station:', set (['ca',' az']), 'covered:' Set ([]) ('states_needed:', set ([' ut']), 'best_station:', None,' final_stations:', set (['ktwo',' kthree', None, 'kfive']))-(' states_need:', set (['ut']),' states_for_station:', set (['mt',' id', 'wa']),' covered:', set ([]) ('states_needed:') Set (['ut']),' best_station:', None, 'final_stations:', set ([' ktwo', 'kthree', None,' kfive']))-('states_need:', set ([' ut']), 'states_for_station:', set ([' ca', 'or',' nv']), 'covered:', set ([])) (' states_needed:', set (['ut'])) 'best_station:', None,' final_stations:', set (['ktwo',' kthree', None, 'kfive']))-(' states_need:', set (['ut']),' states_for_station:', set (['ut',' id', 'nv']),' covered:', set (['ut'])) (' states_needed:', set ([]), 'best_station:',' kone' 'final_stations:', set ([' ktwo', 'kthree', None,' kfive', 'kone']))-(' states_need:', set ([]), 'states_for_station:', set ([' ut', 'nv']),' covered:', set ([])) ('states_needed:', set ([]),' best_station:', 'kone',' final_stations:', set (['ktwo']) 'kthree', None,' kfive', 'kone']))-(' Final_stations:', set (['ktwo',' kthree', None, 'kfive',' kone']))

The end result is: the four radio stations ktwo,kthree,kfive,kone.

Read here, this article "how to use the Python greedy algorithm to solve the set coverage problem" article has been introduced, want to master the knowledge of this article also need to practice and use in order to understand, if you want to know more related articles, welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.