Denksport: Radialer Bestplatz-Algorithmus

Hi zusammen,

Vorweg, dieser Post ist wahrscheinlich eher mathematisch als technisch ein Problem und sicher nicht sonderlich simpel zu lösen. Ich hab mir schon länger mit Kollegen mein Hirn zermattert, wir kommen aber zu keiner eleganten Lösung.

Aufgabenstellung:
Es gibt einen Sitzplan (in Form eines 2-dimensionalen Arrays). Davon sind gewisse Plätze verfügbar (auf der Beispielskizze grün), andere sind nicht buchbar (auf der Beispielskizze rot).

Der Kunde gibt dem System nur bekannt, welche Anzahl an Tickets er haben möchte, und das System soll ihm nach Möglichkeit zusammenhängede Plätze zurückliefern.

Dabei müssen folgende Regeln beachtet werden:

1. Der beste Platz ist links und oben (Skizze: Platz 1/1). Von dort soll die Berechnung beginnen.

2. Die zurückgelieferten Plätze müssen nach folgender Priorisierung zusammenhängend sein (wobei n die vom User gewünschte Platzanzahl repräsentiert):

a) Versuche n nebeneinanderliegende Plätze zu finden. Ist die Suche erfolglos,...

b) versuche n hintereinanderliegende Plätze oder eine Kombination aus nebeneinanderliegenden Plätzen und hinterinanderliegenden Plätzen zu finden. Ist auch diese Suche erfolglos...

c) versuche n diagonal verbundene Plätze zu finden. Ist auch das erfolglos

d) liefere n Plätze mit den geringsten Zwischenabständen zurück, die am besten positioniert sind.

Lösungsansatz & Beispiele:
Klingt recht kompliziert, ist es nach menschlichem "Hausverstand" aber eigentlich nicht.
Hier ein paar Beispiele, passend zu angefügter Skizze:
WICHTIG: Rot makierte Plätze auf der Skizze sind nicht verfügbar!

Beispiel 1: Der Kunde möchte 2 Plätze
Das System muss ihm Platz 1/1 und Platz 1/2 zurückliefern

Beispiel 2: Der Kunde möchte 3 Plätze
Das System muss ihm Platz 3/2, 3/3 und 3/4 zurückliefern. (da nebeneinander liegende Plätze höher priorisiert sind als diagonal oder vertikal verbundene).

Beispiel 3: Der Kunde möchte 4 Plätze
Das System muss ihm Platz 3/2, 3/3, 3/4 und 2/4 liefern (kombination aus horizontal und vertikal)

Beispiel 4: Der Kunde möchte 5 Plätze
Das System muss ihm Platz 2/4, 2/5, 3/2, 3/3 und 3/4 zurückliefern.

Beispiel 4: Der Kunde möchte 15 Plätze
Das System muss ihm FALSE zurückliefern (da nicht mehr 15 Plätze verfügbar sind).

Wie Ihr seht, ist es mit Hausverstand eigentlich eine recht simple sache, dass ganze aber in eine Array-Berechnung umzulegen, ist nicht einfach...

Vielleicht habt Ihr ein paar Ideen oder Denkanstöße, wäre toll.

Danke & LG
Mike

Einen Denkanstoß zur Lösung kann ich dir jetzt nicht liefern, da das nun auf die Schnelle etwas zu komplex ist (wobei ich sagen muss, dass ich sowas auch mal aus Spaß an der Freud machen wollte, es dafür in meinem Bereich aber keine Anwendung gibt (und "nur so" war es dann doch zu viel Arbeit)).

Aber einen Verbesserungsvorschlag für deine Denkweise hätte ich: Bei Beispiel 4 (also das erste Beispiel 4) würde ich 3/3, 3/4 und 2/4, 2/5 vergeben wollen. Einzelpersonen von Gruppen abspalten finde ich nicht so toll. Also ab 4 Personen bitte minimum 2er-Gruppen bilden wenn möglich.

Da hast Du recht... Aber genau das ist das Problem. Es soll die Software selbständig ermitteln können.

Ich denke schon darüber nach, für alle Kombinationsmöglichkeiten Prioritäten zu vergeben.
z.B.:
- nebeneinander liegende Plätze = 10 Punkte
- hintereinander liegende Plätze = 8 Punkte
etc.

Und nachdem alle Möglichkeiten durchgespielt sind, wird jene mit der höchsten Summe ausgegeben.

Das macht die Geschichte aber nicht gerade einfacher.
Vor allem soll die Berechnung keinesfalls länger als 2-3 Sekunden dauern.

Ich weiß, komplizierte Sache, aber das muss doch lösbar sein...

Danke & Ciao,
Mike

Alle Möglichkeiten durchspielen, halte ich nicht für sinnvoll.
Du könntest Dir überlegen, die "Distanz" zwischen den freien Plätzen zu ermitteln.
Z.B. könntest Du nebeneinanderliegende freie Plätze mit einer Kante verbinden, die Du mit 1 bewertest. Hintereinander liegende Plätze erhalten 1.3, Diagonal verbundene 1.6. Nun suchst Du Dir von jedem freien Platz zu jedem anderen freien Platz die kürzeste "Entfernung", wobei Du keine "Wege" berücksichtigen mußt, die über freie Plätze führen.
Die gängigen Verfahren (TSP-Verfahren, Dykstra, etc.) aus der Routen- und Tourenplanung lassen sich dann ggf. auf Dein Problem anpassen.

Gruß hpvw

Ich würds mal mit einem Floodfill-Algorithmus probieren, der zuerst nach rechts und danach erst nach oben und unten füllt (zuletzt diagonal) und bei der eingebenen Anzahl gefundener Felder abbricht. Dürfte in etwa das zurückgeben, was Du Dir vorstellst.

Der Ansatz mag kompletter Blödsinn sein, war aber das was mir spontan zuerst einfiel. ^^

Gruß
.

Hm.. mich würden diese Algorithmen zur Routenplanung interessieren.. Im Prinzip ist es ja nichts anderes, als die Verbindung von n-Orten (Plätzen) auf einem Plan (Sitzplan) mit der kürzestmöglichen Distanz...

Habt Ihr eine ahnung, wo man näheres über diese Algorithmen erfährt?

Danke & LG
Mike

Datic hat gesagt.:

Ich würds mal mit einem Floodfill-Algorithmus probieren, der zuerst nach rechts und danach erst nach oben und unten füllt (zuletzt diagonal) und bei der eingebenen Anzahl gefundener Felder abbricht. Dürfte in etwa das zurückgeben, was Du Dir vorstellst.

Der Ansatz mag kompletter Blödsinn sein, war aber das was mir spontan zuerst einfiel. ^^

Gruß
.

Zum Vergrößern anklicken....

Die Idee ist gar nicht schlecht und ließe sich evtl. mit einer Bewertung der ermittelten Platzgruppen erweitern, um unter den gefundenen die beste zu finden.

Gruß hpvw

Die Idee von Datic klingt wesentlich unkomplizierter als die TSP-Geschichte....
Gibt es zu diesen Floodfill Algorithmen irgendwelche Tuts (Vor allem um die Performance hochzuhalten?)

LG
Mike

Mik3e hat gesagt.:

Hm.. mich würden diese Algorithmen zur Routenplanung interessieren.. Im Prinzip ist es ja nichts anderes, als die Verbindung von n-Orten (Plätzen) auf einem Plan (Sitzplan) mit der kürzestmöglichen Distanz...

Habt Ihr eine ahnung, wo man näheres über diese Algorithmen erfährt?

Danke & LG
Mike

Zum Vergrößern anklicken....

Ausgangspunkt könnte die Übersichtsseite zur Graphentheorie bei Wikipedia sein.

Außerdem könntest Du Dich durch die Uniseiten kämpfen, am ehesten bei den Lehrstühlen für Informatik, Wirtschaftsinformatik oder auch Logistik.

Gruß hpvw

Naja warum kommt es erst zu solchen Probs?
Wenn du systematisch die Plätze verzeilst, wird die Aufteilung nie so, wie im Beispiel sein.

D.h die ersten setzt du vorne hin, die nächsten dahinter etc.
Dann brauchst du nur immer abfragen, wo dir 1. n Plätze nebeneinander sind.

Also wenn ich das richtig sehe ...
Und wenn keine n Plätze mehr nebeneinander sind, dann eben so aufteilen, dass möglichst keiner alleine sitzt von denen, die du neu zuteilst.

Wenn's dir aber echt nur um das Problem geht, einfach so aus spaß, dann ist ok.
Aber so schwer ist das gar nicht, du kannst im Array ja ausrechnen, welche indizes nebeneinander sind.

Und das mit dem diagonal verteilen ... Das ergibt sowieso keinen sinn, oder?
entweder nebeneinander oder hintereinander, aber diagonal?