Aufgabe 4: Rekursion (Exhaustive Search)

Ein bekanntes, schweres Problem in der Informatik ist ”set cover“. Wir wollen dieses Problem hier mit rekursivem ”Exhaustive Search“ lösen (soweit man weiß, geht es im allgemeinen Fall auch nicht wesentlich besser, wenn man eine exakte Lösung sucht: Siehe hierzu https://en.wikipedia.org/wiki/Set_cover_problem). Nehmen wir ein konkretes Anwendungsszenario an: An der JGU gibt es Lehrkräfte, von denen jede Lehrkraft mehrere Fächer abdecken kann: Die Aufgabe ist nun, eine minimale Teilmenge der Lehrkräfte zu finden, die zusammen alle Fächer unterrichten können. Hierbei ist das Vorgehen ähnlich zum ”n-Damen-Problem“, das in der Vorlesung vorgestellt wurde.

	Fach 1	Fach 2	Fach 3	Fach 4	Fach 5	Fach 6
Lehrkraft 1	X	X		X	X
Lehrkraft 2		X		X		X
Lehrkraft 3	X		X			X
Lehrkraft 4		X		X	X
Lehrkraft 5	X		X
Lehrkraft 6			X	X	X

Schreiben Sie ein Unterprogramm ex_search(a), welchem die (rechteckige, nicht zwangsläufig quadratische) Tabelle in Form einer verschachtelten Liste a übergeben wird, welches eine Lösung in Form einer Liste zurück gibt (zum Beispiel [1,2,5] für Lehrkraft 1,2 und 5) und damit dieses Optimierungsproblem rekursiv löst. Hierbei können wie in der Vorlesung angedeutet neben der Rekursion noch Schleifen benutzt werden, aber der rekursive Aufruf ist ein wesentlicher Aspekt des Programms. Geben Sie die Lösung zu der obigen Tabelle auf der Konsole aus, indem Sie Ihrem Unterprogramm die entsprechende Liste übergeben:

a = [[True, True, False, True, True, False],
[False, True, False, True, False, True],
[True, False, True, False, False, True],
[False, True, False, True, True, False],
[True, True, True, False, False, False],
[False, False, True, True, True, True]]

Scaffold Head: a = [[True, True, False, True, True, False], [False, True, False, True, False, True], [True, False, True, False, False, True], [False, True, False, True, True, False], [True, True, True, False, False, False], [False, False, True, True, True, True]] # just in case someone overrides a _a = a[:] # if someone includes print statements _print = print print = lambda msg, *args, **kwargs: _print('#'+str(msg), *args, **kwargs)
Scaffold Foot: print = _print import numpy as np res = ex_search(a) sol = np.array([False]*6) for i in res: sol += np.array(_a[i-1]) if all(sol): print(len(res)) else: print(res, ' is not a valid solution') print(sol)

Start time:: Fr 08 Dez 2017 15:15:07
End time:: Do 14 Dez 2017 14:00:13

General test timeout:: 10.0 seconds

Tests

Comment prefix	`#`
Given input
Expected output	2

Aufgabe 4: Rekursion (Exhaustive Search) Assignment

Tests