[HaBo]

**CDW** · 12.04.11, 15:55

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:

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)       |
 |                                                                  |
 |                                                                  |
 +------------------------------------------------------------------+

mauralix · 13.04.11, 22:52

Die Lösung der Aufgabe sieht mir auf den ersten Blick nach einem klassischen Backtracking aus.

Anzeige

- Anzeige -

**CDW** · 14.04.11, 12:24

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

**Tarantoga** · 14.04.11, 12:45

Zitat:

Zitat von cdw

[*]eingeschränkt, da ich bezweifele, dass hier jemand anständige Speicher/Rechenimplantate besitzt

Du bewilligst uns ja keine Upgrades...

Eydeet · 08.06.11, 10:22

Ohne Zusatz sollte eine Lösung so aussehen, oder?

Lösung

**CDW** · 08.06.11, 16:40

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

(anfangs war "Zusatz" die Hauptaufgabe - wurde allerdings gekürzt, da ich mir dachte, dass man damit leichter "rumtüfteln" kann

)

Eydeet · 09.06.11, 23:45

Okay, dann ist das Problem ja gar nicht so schwer. Um nicht zu viel vorweg zu nehmen sind meine Überlegungen gespoilert.

**CDW** · 10.06.11, 11:44

Eydeet

Anzeige

- Anzeige -

12.04.11, 15:55	#1 (permalink)
CDW Moderator Registriert seit: 20.07.05 Likes: 202	[leicht/mittel]WLAN-Kanal Zuteilung Anzeige 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: 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) \| \| \| \| \| +------------------------------------------------------------------+ bitmuncher and overflow like this. __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

13.04.11, 22:52	#2 (permalink)
mauralix Registriert seit: 17.04.06 Likes: 3	Die Lösung der Aufgabe sieht mir auf den ersten Blick nach einem klassischen Backtracking aus. __________________ http://chm0815.blogspot.com

14.04.11, 12:24	#3 (permalink)
CDW Moderator Themenstarter Registriert seit: 20.07.05 Likes: 202	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 __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

08.06.11, 10:22	#5 (permalink)
Eydeet Registriert seit: 14.04.06 Likes: 4	Ohne Zusatz sollte eine Lösung so aussehen, oder? Lösung Abwechselnd: Code: 1 2 3 3 1 1 2 3 3 1 Code: 2 3 1 1 2 2 3 1 1 2

08.06.11, 16:40	#6 (permalink)
CDW Moderator Themenstarter Registriert seit: 20.07.05 Likes: 202	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 (anfangs war "Zusatz" die Hauptaufgabe - wurde allerdings gekürzt, da ich mir dachte, dass man damit leichter "rumtüfteln" kann ) __________________ Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf! Selig, wer nichts zu sagen hat und trotzdem schweigt.

09.06.11, 23:45	#7 (permalink)
Eydeet Registriert seit: 14.04.06 Likes: 4	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?

Themen-Optionen
Druckbare Version zeigen Jemanden per E-Mail auf dieses Thema hinweisen
Ansicht
Linear-Darstellung Zur Hybrid-Darstellung wechseln Zur Baum-Darstellung wechseln

[HaBo]

[leicht/mittel]WLAN-Kanal Zuteilung