Die probabilistische Methode in der Kombinatorik

Abstract

Ziel dieser Arbeit ist die Lösung kombinatorischer Probleme unter Einsatz von probabilistischen Methoden, insbesondere Simulated Annealing. Probabilistische Algorithmen verwenden einen Zufallsgenerator, um das Vorgehen zu bestimmen, und sind somit bei Problemen schneller, deren Definitionsraum zu groß für eine erschöpfende Suche ist. Es werden Analysen durchgeführt, unter welchen Bedingungen diese Methoden eine Lösung approximieren. Simulated Annealing ist am Abkühlprozess aus der Metallurgie angelehnt, bei dem ein Stoff stark erhitzt und dann langsam abgekühlt wird, um eine möglichst optimale Beschaffenheit zu erzielen. Anhand von zwei kombinatorischen Fragestellungen werden diese Methoden auch in Laufzeit und Güte der Lösung untersucht. Die Erste ist das Property B Problem. Von einer Grundmenge mit endlicher Anzahl an Objekten hat eine Familie von Teilmengen Property B, falls diese Familie mit jeder beliebigen Partition der Grundmenge nichtleeren Durchschnitt hat. Gesucht wird die kleinstmögliche Familie, sodass diese Eigenschaft nicht gilt. Das zweite Problem ist die Suche nach Covering Codes. Hierbei wird in einem Coderaum ein Code gesucht, sodass alle Codewörter des Coderaumes höchstens Abstand R von einem Codewort dieses Codes haben. Dazu wurden zwei Lösungsverfahren durch Simulated Annealing in C realisiert.

This thesis introduces probabilistic methods for solving combinatorial problems. Main method used is Simulated annealing. Probabilistic algorithms use random numbers to determine the course of action. They can be used when an exhaustive search is deemed unfeasible or extremely inefficient. Conditions for convergence will be discussed in this thesis. Simulated annealing is a procedure which mirrors a phenomenon in metallurgy. Annealing in metallurgy is the process of heating up a material and then cooling it down very slowly to reduce defect to enable the solid to reach its lowest possible state of energy. Two combinatorial problems will be presented and quality and runtime of Simulated annealing will be analyzed. The first one is the property b problem. A family of subsets of a set X has property b, if every partition of X meets with every subset. We look for the smallest family for which this property does not hold. The second problem is the search for covering codes. A covering code is a collection of codewords such that every codeword of the codespace has at most hamming-distance R from one codeword of the covering code. Two solving schemes have been implemented in C.