Confundido/a acerca del bucle for en el Problema de Cubrimiento de Conjuntos (Algoritmos Voraces)
Esta es mi primera vez aprendiendo estructuras de datos y algoritmos. Estoy atascado en el Capítulo 8 de Algoritmos Codiciosos de Grokking Algorithm, donde se presenta a los lectores un problema simple de Cobertura de Conjuntos.
¿Existe un ejemplo más simple de código fuente al que pueda referirme para comprender el concepto detrás de este ejemplo?
¿Alguien puede explicar cómo la intersección de conjuntos ayuda a obtener el resultado final de {‘k4’, ‘k5’} en inglés claro? ¿Cómo se pasa el array de estados necesarios a un hash y se convierte en un conjunto?
states_needed = set(["a", "b", "c", "d", "e", "f", "g", "h"])
stations = {}
stations["k1"] = set(["a", "b", "c"])
stations["k2"] = set(["c", "d", "e"])
stations["k3"] = set(["f", "g", "h"])
stations["k4"] = set(["a", "b", "c", "d"])
stations["k5"] = set(["e", "f", "g", "h"])
final_stations = set()
while states_needed:
best_station = None
states_not_covered = set()
for station, states_for_station in stations.items():
covered = states_needed & states_for_station
if len(covered) > len(states_not_covered):
best_station = station
states_not_covered = covered
states_needed -= states_not_covered
final_stations.add(best_station)
print(final_stations)
davy.ai
Sí, hay varios ejemplos más simples disponibles en línea a los que puedes referirte. Algunos ejemplos son:
La operación de intersección de conjuntos (&) ayuda a encontrar los estados que están cubiertos por una estación en particular. En un lenguaje sencillo, esto significa encontrar los estados comunes entre los estados necesarios y los estados cubiertos por una estación.
Por ejemplo, si los estados necesarios son [a, b, c] y una estación cubre [b, c, d], entonces la operación de intersección de conjuntos devolverá [b, c] ya que son los estados comunes.
El programa utiliza una tabla hash para almacenar las estaciones y sus estados cubiertos correspondientes. La tabla hash se representa mediante un diccionario en Python. La matriz de estados necesarios se pasa como un conjunto al programa y se utiliza para realizar operaciones de conjuntos como unión, intersección, etc.