nicht angemeldet
Hallo martin,
Ferrari rot München Madonna Lehrer
BMW blau Köln Heino Meztger
Ah ok, das sind die Daten und zusätzlich sind Bedingungen gegeben wie "BMW steht neben Ferrari", "rot neben grün" etc.?
Gesucht ist nun was? Die Reihenfolge in der die Autos geparkt sind?
Für solche Probleme eignet sich meist Backtracking oder fertige Software für Constraint Programming.
http://de.wikipedia.org/wiki/Backtracking@Backtracking ist in der Wikipedia recht ausführlich beschrieben. Die Idee ist es, nicht nacheinander Kombinationen auszuprobieren, sondern diese Schrittweise auszuwählen und an einer Stelle nicht weiter zu suchen, sobald man feststellt, dass das nicht geht.
Theoretisch ist es zwar möglich, dass man bei diesem Ansatz auch alle Kombinationen ausprobieren muss. Praktisch kann man das aber meist verhindern, indem man sich überlegt, wie man schon erkennen, dass eine Kombination nicht zulässig ist, bevor man alle Elemente festgelegt hat und das evtl. noch um Heuristiken erweiter, welche Art von Kombinationen zuerst untersucht werden sollten.
Ich würde als ersten Ansatz mal so etwas machen:
Belege der Reihe nach die Parkplätze, sobald eine Regel verletzt ist, breche ab und mache mit anderen Kombinationen weiter.
Wenn das nicht schon reicht, würde ich versuchen, immer zuerst Werte zu wählen, für die ich möglichst viele Regeln habe.
Funktioniert das auch nicht, würde ich mir überlegen, ob ich mir wirklich die Arbeit machen möchte oder doch erstmal eine fertige Software drauf ansetzen ;-)
Das Problem ist relativ einfach und lässt sich mit Aussagenlogik (siehe Wikipedia ;-) modellieren.
Wenn man das gemacht hat, könnte man z.B. Limboole darauf ansetzen und eine Lösung bestimmen lassen. Mit beliebig großen Problemen kommen solche Programme natürlich auch nicht klar. Aber es reicht schon für mehr als man mal so auf die Schnelle mit Backtracking gelöst bekommt.
Grüße
Daniel
seth