Complete codeExample: U = {1,2,3,4,5} S = {S1,S2,S3} S1 = {4,1,3}, Cost(S1) = 5 S2 = {2,5}, Cost(S2) = 10 S3 = {1,4,3,2}, Cost(S3) = 3 Output: Set cover = {S2, S3} Min Cost = 13 """ def powerset(iterable): """Calculate the powerset of any iterable. For a range of integers up to the length of the given list, make all possible combinations and chain them together as one object. From https://docs.python.org/3/library/itertools.html#itertools-recipes """ "list(powerset([1,2,3])) --> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]" s=list(iterable) returnchain.from_iterable(combinations(s, r) forrinrange(len(s) +1)) def optimal_set_cover(universe, subsets, costs): """ Optimal algorithm - DONT USE ON BIG INPUTS - O(2^n) complexity! Finds the minimum cost subcollection os S that covers all elements of U Args: universe (list): Universe of elements subsets (dict): Subsets of U {S1:elements,S2:elements} costs (dict): Costs of each subset in S - {S1:cost, S2:cost...} """ pset=powerset(subsets.keys()) best_set=None best_cost=float("inf") forsubsetinpset: covered=set() cost=0 forsinsubset: covered.update(subsets[s]) cost+=costs[s] iflen(covered) ==len(universe) andcost<best_cost: best_set=subset best_cost=cost returnbest_set def greedy_set_cover(universe, subsets, costs): """Approximate greedy algorithm for set-covering. Can be used on large inputs - though not an optimal solution. Args: universe (list): Universe of elements subsets (dict): Subsets of U {S1:elements,S2:elements} costs (dict): Costs of each subset in S - {S1:cost, S2:cost...} """ elements=set(eforsinsubsets.keys() foreinsubsets[s]) # elements don't cover universe -> invalid input for set cover ifelements!=universe: returnNone # track elements of universe covered covered=set() cover_sets= [] whilecovered!=universe: min_cost_elem_ratio=float("inf") min_set=None # find set with minimum cost:elements_added ratio fors, elementsinsubsets.items(): new_elements=len(elements-covered) # set may have same elements as already covered -> new_elements = 0 # check to avoid division by 0 error ifnew_elements!=0: cost_elem_ratio=costs[s] /new_elements ifcost_elem_ratio<min_cost_elem_ratio: min_cost_elem_ratio=cost_elem_ratio min_set=s cover_sets.append(min_set) # union covered |= subsets[min_set] returncover_sets if __name__ == '__main__': universe= {1, 2, 3, 4, 5} subsets= {'S1': {4, 1, 3}, 'S2': {2, 5}, 'S3': {1, 4, 3, 2}} costs= {'S1': 5, 'S2': 10, 'S3': 3} optimal_cover=optimal_set_cover(universe, subsets, costs) optimal_cost=sum(costs[s] forsinoptimal_cover) greedy_cover=greedy_set_cover(universe, subsets, costs) greedy_cost=sum(costs[s] forsingreedy_cover) print('Optimal Set Cover:') print(optimal_cover) print('Cost = %s'%optimal_cost) print('Greedy Set Cover:') print(greedy_cover) print('Cost = %s'%greedy_cost.

The code defines two functions: optimal_set_cover and greedy_set_cover. The optimal_set_cover…

Answered: U = {1,2,3,4,5} S = {S1,S2,S3}…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

Complete code

Example:
	U = {1,2,3,4,5}
	S = {S1,S2,S3}

	S1 = {4,1,3}, Cost(S1) = 5
	S2 = {2,5}, Cost(S2) = 10
	S3 = {1,4,3,2}, Cost(S3) = 3

	Output:
	Set cover = {S2, S3}
	Min Cost = 13
	"""


	def powerset(iterable):
	"""Calculate the powerset of any iterable.

	For a range of integers up to the length of the given list,
	make all possible combinations and chain them together as one object.
	From https://docs.python.org/3/library/itertools.html#itertools-recipes
	"""
	"list(powerset([1,2,3])) --> [(), (1,), (2,), (3,), (1,2), (1,3), (2,3), (1,2,3)]"
	s=list(iterable)
	returnchain.from_iterable(combinations(s, r) forrinrange(len(s) +1))


	def optimal_set_cover(universe, subsets, costs):
	""" Optimal algorithm - DONT USE ON BIG INPUTS - O(2^n) complexity!
	Finds the minimum cost subcollection os S that covers all elements of U

	Args:
	universe (list): Universe of elements
	subsets (dict): Subsets of U {S1:elements,S2:elements}
	costs (dict): Costs of each subset in S - {S1:cost, S2:cost...}
	"""
	pset=powerset(subsets.keys())
	best_set=None
	best_cost=float("inf")
	forsubsetinpset:
	covered=set()
	cost=0
	forsinsubset:
	covered.update(subsets[s])
	cost+=costs[s]
	iflen(covered) ==len(universe) andcost<best_cost:
	best_set=subset
	best_cost=cost
	returnbest_set


	def greedy_set_cover(universe, subsets, costs):
	"""Approximate greedy algorithm for set-covering. Can be used on large
	inputs - though not an optimal solution.

	Args:
	universe (list): Universe of elements
	subsets (dict): Subsets of U {S1:elements,S2:elements}
	costs (dict): Costs of each subset in S - {S1:cost, S2:cost...}
	"""
	elements=set(eforsinsubsets.keys() foreinsubsets[s])
	# elements don't cover universe -> invalid input for set cover
	ifelements!=universe:
	returnNone

	# track elements of universe covered
	covered=set()
	cover_sets= []

	whilecovered!=universe:
	min_cost_elem_ratio=float("inf")
	min_set=None
	# find set with minimum cost:elements_added ratio
	fors, elementsinsubsets.items():
	new_elements=len(elements-covered)
	# set may have same elements as already covered -> new_elements = 0
	# check to avoid division by 0 error
	ifnew_elements!=0:
	cost_elem_ratio=costs[s] /new_elements
	ifcost_elem_ratio<min_cost_elem_ratio:
	min_cost_elem_ratio=cost_elem_ratio
	min_set=s
	cover_sets.append(min_set)
	# union
	covered \|= subsets[min_set]
	returncover_sets


	if __name__ == '__main__':
	universe= {1, 2, 3, 4, 5}
	subsets= {'S1': {4, 1, 3}, 'S2': {2, 5}, 'S3': {1, 4, 3, 2}}
	costs= {'S1': 5, 'S2': 10, 'S3': 3}

	optimal_cover=optimal_set_cover(universe, subsets, costs)
	optimal_cost=sum(costs[s] forsinoptimal_cover)

	greedy_cover=greedy_set_cover(universe, subsets, costs)
	greedy_cost=sum(costs[s] forsingreedy_cover)

	print('Optimal Set Cover:')
	print(optimal_cover)
	print('Cost = %s'%optimal_cost)

	print('Greedy Set Cover:')
	print(greedy_cover)
	print('Cost = %s'%greedy_cost.

Expert Solution

Step by step

Solved in 3 steps with 1 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.