Algorithmus für ein Planungstool

Question

Ich schreibe eine kleine Software-Anwendung, die als einfaches Planungstool für eine lokale Schule dienen muss. Das ‚Problem‘ es braucht zu lösen, ist recht einfach. Das heißt, müssen die Lehrer mit den Eltern aller Kinder sprechen. Allerdings haben einige Kinder, natürlich, Brüder und Schwestern in verschiedenen Gruppen, so dass diese Gespräche müssen nebeneinander eingeplant werden, die Situationen waren Eltern zu vermeiden, haben einen Vortrag auf 18.00 Uhr und eine weitere um 10 Uhr. So kurz gesagt, eine Sammlung von gegeben n Kinder, wo einige Kinder haben 1 oder mehr Geschwister, erzeugen einen Zeitplan, wo alle Gespräche dieser Kinder geplant sind nebeneinander.

Nun, vielleicht kann das Problem sehr einfach gelöst werden, aber auf der anderen Seite habe ich ein Gefühl, das ein ziemlich kompliziertes Problem sein kann, die benötigt und kann mit irgendeiner Art von Algorithmus gelöst werden. Elegant. Aber bin ich recht? Gibt es? Ich habe auf der ungarischen alorithm aber nicht ganz auf dieses spezielle Problem anzuwenden.

Edit:. Ich vergaß zu erwähnen, dass alle Gespräche die gleiche Menge an Zeit in Anspruch nehmen

Danke!

Answer 1

Ich denke, es ist ganz einfach.

Erste Gruppen der Kinder, die zusammengehören, weil sie Eltern teilen. Planen Sie die Kinder in einer Gruppe aufeinander folgend, plant den Rest als zufällig.

Eine weitere Möglichkeit, zu abstrahieren und das Problem leichter machen, ist aus der übergeordneten Perspektive zu betrachten, sehen Brüder und Schwester als „Kind“ und ihnen mehr Zeit zu geben. Dann können Sie einfach die Eltern zufällig planen, aber einige brauchen mehr Zeit (weil sie mehrere childeren haben).

Answer 2

Ein Ansatz woul DBE das Problem in einer deklarativen Einschränkung Sprache zu definieren und dann lassen Sie es das Problem für Sie lösen. Das letzte Mal, als ich das tat, habe ich ECLIPSE , die eine nette kleine Sprache ist, wo Sie Ihr Problem Raum, der durch Einschränkungen definieren und lassen sie es dann zulässige Werte finden, die diese Bedingungen erfüllen.

Zum Beispiel, ich glaube, Sie haben zwei Klassen von Einschränkungen:

1. Ein Lehrer kann nur einen haben Konferenz zu einem Zeitpunkt
2. Alle Schüler in der gleichen Familie Muss haben aufeinanderfolgende Schlitze

Sobald Sie diese in ECLIPSE definieren, wird es Werte für jeden Schüler berechnen, die die Anforderungen erfüllen. Wenn Sie diesen Weg gehen, können Sie auch leicht Einschränkungen hinzufügen, wie Sie benötigen. Zum Beispiel ist es einfach zu sagen, dass ein Teach für Slot Y nicht verfügbar ist, oder Lehrer müssen abwechselnd tun administrative Arbeit nehmen, etc.

Answer 3

Diese Art fühlt sich wie eine „Rucksack-Algorithmus“ Art des Problems. Sie müssen die Familienmitglieder zusammen dann füllen Schlitze in geeigneter Weise zu gruppieren.

Wenn Sie „Rucksack-Algorithmus“ google, werden Sie genug Zuschreibung sehen den Kopf drehen zu machen und auch einige gute codierte Lösungen.

Answer 4

Ich denke, wenn jedes Gespräch auf „Aktivitäten“ reduziert werden könnte, wo jede Aktivität eine Startzeit und eine Endzeit hat man die Aktivität-Auswahlalgorithmus in Informatik studiert nutzen könnten. Es basiert auf einem gierigen Ansatz und könnte in O (n) gelöst werden (wobei n die Anzahl der Aktivitäten ist). Sie könnten mehr Informationen hier finden. Ich bin sicher, Sie müssen hier eine Vorbearbeitung tun müssen, um die Lage sein, die Bruder / Schwester Ausgabe als Aktivitäten des gleichen Typs zu reduzieren.