[leicht/mittel]WLAN-Kanal Zuteilung

CDW

0
Mitarbeiter
Wie einige schon wissen, werden während der Phase II der Weltherrschaftübernahme hauptsächlich 3 Hauptquartiere (Schweiz, Alaska, Australien) gebraucht.
Die jeweiligen HQs sind vom Bauplan absolut identisch und unterscheiden sich nur in (Keller ;) )Stockwerkanzahl:
Schweiz: -2 Stockwerke
Australien: -3
Alaska: -20

Nun brauchen wir darin unbeding ein WLAN.
Die optimalen Positionen für die AccessPoints auf dem jeweiligen Stockwerk wurden schon berechnet.
Eingesetzt soll IEEE 802.11h
da man hier 19 Kanäle zur Verfügung hat.

Wir brauchen aber noch eine Kanalzuteilung pro AccessPoint-Standort. Die Kanäle der Nachbarn sollten sich nicht überschneiden ;)

Hier die Skizze eines Stockwerks (ich war so frei und habe die Koordinaten durch ganze Zahlen ersetzt, damit ihr es einfacher habt):
Code:
  +----------------------------------------------------+
 |                                                    |
 |                                                    |
 |     (0,3,0)           (1,3,0)          (2,3,0)     |
 |                                                    |
 |                                                    |
 |                                                    |
 |                                                    |
 |                                                    |
 |              (0,2,0)           (1,2,0)             |
 |                                                    |
 |                                                    |
 |                                                    |
 |                                                    |
 |                                                    |
 |     (0,1,0)           (1,1,0)          (2,1,0)     |
 |                                                    |
 |                                                    |
 |                                                    |
 |                                                    |
 |                                                    |
 |              (0,0,0)             (1,0,0)           |
 |                                                    |
 |                                                    |
 +----------------------------------------------------+
Koordinaten: (x,y,z), wobei x,y die Position auf dem jeweiligen Stockwerk darstellt und z das eigentliche Stockwerk (hier: 0)
Positionen auf anderen Stockwerken sind identisch (abgesehen von z).

Nachbarn: unmittelbare Nachbarn auf dem jeweiligen Stockwerk sowie 1 Stockwerk höher/tiefer (wegen der Bodendicke muss eigentlich nur der unmittelbar höhere/tiefere Nachbar berücksichtigt werden - z.B von (0,0,1): (0,0,0), (0,0,2))
Beispiel: Nachbarn von (0,0,1): (0,1,1), (1,1,1), (1,0,1), (0,0,0), (0,0,2)
Nachbarn von (1,1,0): (0,1,0), (0,2,0),(1,2,0),(2,1,0),(1,0,0),(0,0,0) und (1,1,1)

Es reicht schon, als Ausgabe eine Liste mit AccessPoint Koordinaten samt dem zugehörigem Kanal(1-19) zu posten.

Zusatz:
Unser aktuelles HQ in Berlin könnte auch eine Neuzuteilung vertragen.
Es sind 10 Stockwerke mit folgender Positionierung:
Code:
 +------------------------------------------------------------------+
 |                                                                  |
 |           (0,8,0)            (1,8,0)               (2,8,0)       |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |     (0,7,0)           (1,7,0)          (2,7,0)       (3,7,0)     |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |           (0,6,0)            (1,6,0)               (2,6,0)       |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |     (0,5,0)           (1,5,0)          (2,5,0)       (3,5,0)     |                                                                    
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |           (0,4,0)            (1,4,0)               (2,4,0)       |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |     (0,3,0)           (1,3,0)          (2,3,0)       (3,3,0)     |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |           (0,2,0)            (1,2,0)               (2,2,0)       |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |     (0,1,0)           (1,1,0)          (2,1,0)       (3,1,0)     |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |                                                                  |
 |         (0,0,0)               (1,0,0)              (2,0,0)       |
 |                                                                  |
 |                                                                  |
 +------------------------------------------------------------------+
 
Ich behaupte mal, dass man die Aufgabe (abgesehen vom Zusatz) auch mit euren eingeschränkten menschlichen Ressourcen* lösen kann. Ganz ohne externe Rechenkapazitäten ;)


[*]eingeschränkt, da ich bezweifele, dass hier jemand anständige Speicher/Rechenimplantate besitzt ;)
 
Ohne Zusatz sollte eine Lösung so aussehen, oder?
Abwechselnd:
Code:
1 2 3
 3 1
1 2 3
 3 1
Code:
2 3 1
 1 2
2 3 1
 1 2
 
Jep. Man kann es relativ leicht per Hand ausrechnen. Mit einem Programm/Code wäre es natürlich schöner, da man sich so auf den "Zusatz" vorbereiten kann :wink: (anfangs war "Zusatz" die Hauptaufgabe - wurde allerdings gekürzt, da ich mir dachte, dass man damit leichter "rumtüfteln" kann :) )
 
Okay, dann ist das Problem ja gar nicht so schwer. Um nicht zu viel vorweg zu nehmen sind meine Überlegungen gespoilert.
Aufgrund der Symmetrie dieses Problems ist es ausreichend, nur Lösungen für die ersten beiden Stockwerke zu finden, diese kann man dann abwechselnd wiederholen.
Gleiches gilt für die Reihen in jedem Stockwerk. Auch hier ist es wegen der speziellen Anordnung möglich, die Reihen abwechselnd zu wiederholen.
Es ist also nur nötig, für die ersten beiden Reihen des ersten und des zweiten Stockwerks eine gültige Färbung zu finden. Sobald dieses Problem gelöst ist, ist der Rest trivial.

Für das Färbungsproblem gibt es ein paar intelligente Algorithmen, für allgemeine Graphen führt afaik die zufällige Auswahl der Knoten und minimaler Färbung dieser schon zu einer recht guten Lösung. In diesem Fall ist das noch nicht einmal nötig. Bereits die triviale Lösung, für alle Punkte unterschiedliche Frequenzen zu wählen führt beim Zusatzproblem schon zu einer validen Lösung, denn die vier Reihen haben zusammen nur 14 Punkte, es gibt aber 19 Frequenzen. Eine triviale Lösung sieht demnach so aus:

Abwechselnd:
Code:
 1 2 3
4 5 6 7
 1 2 3
4 5 6 7
...
und
Code:
  8  9 10
11 12 13 14
  8  9 10
11 12 13 14
...

Es ist allerdings möglich, mit deutlich weniger Frequenzen auszukommen, bei allgemeiner Größe wie folgt:

Abwechselnd:
Code:
 3 1 2 3 1 2 ...
1 2 3 1 2 3 1 ...
...
und
Code:
 1 2 3 1 2 3 ...
2 3 1 2 3 1 2 ...
...

Das könnte man natürlich noch in Code gießen, das ist allerdings an dieser Stelle m.E. keine große Schwierigkeit mehr. Waren obige Überlegungen das Ziel dieser Übung, oder sollte das Programm unoptimiert das Färbungsproblem lösen?
 
Waren obige Überlegungen das Ziel dieser Übung, oder sollte das Programm unoptimiert das Färbungsproblem lösen?
Größtenteils ja. Auch wenn ich zugegebenermaßen eine etwas andere Strategien im Kopf hatte (mit "Teilen&Herrschen" kommt man hier auch weiter - und notfalls lässt sich jeder planare Graph sowieso mit 6 Farben in linearer Zeit färben).
Auf jeden Fall waren Vorüberlegungen notwendig - während sich Teil1 noch gut per Backtracking/Bruteforce lösen ließe, würde man damit beim Teil2 sich die (CPU)"Zähne" ausbeißen ;)

Dass man es durch simple versetzte Reihen lösen kann, war allerdings nicht geplant :(
Vielleicht hätte ich an meiner Originalidee nicht sooo viel rumbasteln sollen - allerdings wollte ich das rel. abstrakte Färbungsproblem in "RealWorld" Rahmen bringen und dabei die Schwierigkeitsstufe möglichst niedrig halten, was wohl nicht so ganz geklappt hat
 
Zurück
Oben