next up previous
Nächste Seite: Suchprobleme (2) Aufwärts: Berechenbarkeit, Komplexität (24. 10. Vorherige Seite: Hanoi (2)

Suchprobleme

$ $Id: expo.tex,v 1.2 2003/10/24 13:16:42 joe Exp $ $

Viele Aufgaben lassen sich als Such-Probleme formulieren.

Beispiel 1 (COL): gegeben sind ein Netzplan (ein Graph, bestehend aus Knoten und Kanten) sowie eine Zahl $c$ von Farben. gesucht ist eine Färbung der Knoten, so daß keine Kante zwischen gleichfarbigen Knoten verläuft.

(nicht in Vorlesung), Beispiel 2 (Lunar Lockout, siehe www.binaryarts.com): gegeben ist eine Anordnung von Robotern. Gesucht ist eine Folge von (erlaubten) Bewegungen, nach der schließlich der rote Roboter in der Mitte steht.



Johannes Waldmann 2004-01-30