Thiemos Archiv
- Sunday, 2004-07-25 15:41
- Ich habe eine Datenbank mit einem Satz von Regeln für Öffnungszeiten, z.B. "geöffnet Montag bis Donnerstag von 8 bis 18 Uhr", "geöffnet jeden 2. Samstag im Monat von 10 bis 14 Uhr", "geschlossen vom 25. bis 26.12. (Feiertage)" usw. Gesucht ist die nächste Öffnungszeit von der jeweils aktuellen Uhrzeit aus bemessen. Wie sieht ein optimaler Algorithmus aus, der mir das mit geringstmöglichem Aufwand berechnet?
Kommentare zu diesem Beitrag können per E-Mail an den Autor gesandt werden.
naja, irgendwie muß man die Regeln ein wenig computertauglicher formulieren *überleg*
vielleicht sollte man erst einmal die Regeln innerhalb eine Woche zusammenfassen mit Hilfe von timestamps. Sonntag 0 Uhr ist t=0, naja bis Samstag 23:95 ...
nur dann hat man immer noch genügend Sonderregelungen ... *grübel*
oder man muß anhand der Regelungen die einzelnen Öffnunfszeiten erst einmal ermitteln ... so daß in der DB jeder einzelne offene Tag steht ...
irgendwie ist die Aufgabe sehr interessant!
das problem ist eher das geschickteste format in dem du die öffnungszeiten in der DB ablegst.
Für die Auswertung fülle ich eine Matrix für die z.b. nächsten 8 Wochen mit allen möglichen positiven Zeiträumen. Danach werden die negativen Zeiträume wieder herausgestrichen. Der kleinste übriggebliebene Termin ist die nächste relevante Öffnungszeit.
Das Problem dabei: Wenn es z.B. 8 Wochen Urlaub gibt, ist die Matrix nach der Anwendung der Negativ-Regeln leer. Den Algorithmus in solchen Fällen mehrmals laufen zu lassen, ist aber auch keine gute Idee.
Stellt euch vor, ein Ereignis findet nur am 29.2. statt, und das auch nur aller 8 Jahre. Außerdem liegt für den 29.2.2008 eine einmalige Negativ-Regel vor. Wie kann ein Algorithmus den nächsten Termin berechnen (29.2.2016), ohne eine megabytegroße Matrix zu benötigen? Mit Timestamps (die nebenbei noch ganz andere Probleme machen, Stichwort "Sommerzeit") komme ich da nicht weiter.
-Eingabe: Startzeit
While(NotFound)
-Berechne für alle Positivregeln die jeweils nächstliegendste Öffnungszeit, sortiere diese mit dazugehörigen Regeln in einer Liste. Regeln, die in der Vergangenheit liegen, also keinen Zeitpunkt mehr liefern, fliegen raus
-Verfahre ebenso mit den Negativregeln in einer zweiten Liste
-Wähle den ersten Eintrag der Positivliste -> ergibt geeignete nächste Öffnungszeit
-Teste nun, ob in der Negativliste Einträge stehen mit Schließzeit<aktuelle Öffnungszeit und prüfe, ob diese der aktuellen Öffnungszeit widersprechen.
-Falls kein solcher Eintrag vorhanden: Fertig
-Falls solch ein Eintrag vorhanden: Setze aktuelle Startzeit auf das Ende der Schließzeit
-Falls Listen leer: Nie geöffnet
ENDWHILE
In den meisten Fällen (wenn sich die nächstliegenden Zeiträume nicht überlappen) dürfte nach ein oder zwei Läufen schon ein Ergebnis bereitliegen.
Zur Implementierung: Es muß nur einmal komplett sortiert werden, danach genügt es, wenn die jeweils in der Vergangeheit liegende Regeln neu evaluiert werden.
Als Sortierung reicht eine Prioritätswarteschlange.
Um die Sommerzeit kommst Du so oder so nicht herum, irgendeine lineare Zeit wird schon benötigt.
Einen Haken hat das Verfahren: Es terminiert nur, wenn tatsächlich irgend wann auch mal geöffnet ist oder keine zeitlich unbegrenzt gültigen Regeln existieren.
Ein Problem haben alle Ansätze: Was passiert mit einem Regelsatz der Art "Wochentags geöffnet" + "jeden 2ten Mittwoch geschlossen" + "Im Dezember an allen Wochentagen geöffnet"?