Mailinglist Archive: opensuse-programming-de (187 mails)

[Andreas Loesch <suseliste@xxxxxxxxx>]

Hi Michael, *,
Am Donnerstag, 7. Oktober 2004 23:08 schrieb Michael Wenger:
> Andreas Loesch schrieb am 07.10.2004 19:00 :
> > IMHO handelt es sich auf jeden Fall um ein Optimierungsproblem, hier
> > wären dann Stichworte wie Lineare Programmierung etc. angesagt,
> > weiterhin dürfte es sich um ein NP-vollständiges Problem handeln, so
> > dass [...] Du mit Greedy nicht weit kommst. Hier sind andere
> > Heuristiken und Approximations-Schemata interessant.
>
> Hm?
> Gerade weil dieses Problem NP-vollständig ist, ist doch "Greedy" eine
> Lösungsmöglichkeit.
>

Greedy liefert eine Lösung, die aber beliebig weit von einem Optimum entfert 
ist. Insbesondere habe ich bei NP-Problemen noch keine guten Greedys gesehen.

Aber der Witz besteht ja darin eine möglichst gute Löusung zu produzieren. 
Hier sind also Approximationsschemata (mit etsprechendem Gütebeweis :) ) oder 
eine ganz klassische Branch-and-Bound-Lösung sicherlich mit besseren 
Ergebnissen gesegnet.

Als reines Graphenproblem sehe ich das eigendlich weniger, Wenn man das 
Problem als Graphenproblem beschreiben will, könnte man ein Maximales 
Matching über je n-Knoten draus bauen (Fach - Lehrer - StundeInRaum - Klasse) 
aber maximale Matchings bei n>2 sollten auch NP-Vollständig sein :) sonst 
hätten wir ein Klasse Problem beseitigt. Zusätzlich fehlen dann die 
Nebenbedingungen, dass nur bestimmte Lehrer irgendwas unterrichten können, 
dass alle Zeiten geblockt sein müssen (minimale Lücken) etc..

Andreas