Embed Size (px)
DESCRIPTION
Meine Facharbeit im Fach Mathematik.
Citation preview
Planare Standortprobleme am Beispiel von Sendemasten
Facharbeit von Malte Schledjewski ( 12M2 )
Hohenstaufen-Gymnasium Kaiserslautern
11.05.2010
Planare Standortprobleme am Beispiel von Sendemasten
1 Einleitung ____________________________________________________________1
2 Problemstellung _______________________________________________________2
3 Lösungsstrategien _____________________________________________________2
3.1 Bisherige Ansätze __________________________________________________2
3.1.1 Der kontinuierliche Fall ___________________________________________2
3.1.2 Der diskrete Fall ________________________________________________4
3.2 Algorithmen_______________________________________________________6
3.2.1 Der Wegstreich-Algorithmus _______________________________________6
3.2.2 Der Kanten-Algorithmus __________________________________________8
3.2.3 Der Greedy-Algorithmus __________________________________________9
3.3 Analyse der Algorithmen_____________________________________________9
3.3.1 Der Wegstreich-Algorithmus ______________________________________14
3.3.2 Der Kanten-Algorithmus _________________________________________15
3.3.3 Der Greedy-Algorithmus _________________________________________15
3.4 Analyse des Problems _____________________________________________17
3.5 Bewertung_______________________________________________________18
4 Ausblick ____________________________________________________________19
5 Literaturverzeichnis ___________________________________________________20
6 Anhang ____________________________________________________________20
1
1 Einleitung Das heutige Zeitalter wird oft auch als Informationszeitalter bezeichnet. Das heißt,
der Zugang zu Informationen ist bedeutend für die Gesellschaft. Gleichzeitig lässt
sich ein Trend zur Mobilisierung erkennen. Computer wurden zu Laptops, wurden
zu Netbooks und wurden zu Smartphones wie zum Beispiel dem iPhone. Die
Nachfrage nach mobilem Internet steigt stetig. Wir entwickeln uns zu einer
Gesellschaft, in der wir immer Zugriff auf riesige Mengen an Daten und
Informationen haben und brauchen. Doch dafür braucht man die nötigen
Mobilfunk-Netze. In manchen Ländern geht es um den Aufbau, wohingegen es in
Deutschland primär um den Ausbau, beziehungsweise um die Aufrüstung der
bestehenden Netz-Infrastruktur geht. Nach UMTS steht nun der LTE-Standard für
ein Mobilfunknetz der vierten Generation, welches teilweise sogar schneller ist als
aktuelle DSL-Anschlüsse. Gleichzeitig subventioniert die Bundesregierung den
Breitbandausbau in den bisher vernachlässigten, ländlichen Regionen. Für die
Provider verursacht jeder Sendemast zusätzliche Kosten, gleichzeitig will man
jedoch eine optimale Abdeckung des Gebietes erreichen. Die Frage ist also wie
man die Sendemasten optimal verteilt, um alles abzudecken und trotzdem
möglichst wenige Masten zu benötigen.
In dieser Facharbeit sollen einige Möglichkeiten diskutiert werden, wie man die
Problemstellung mathematisch modellieren kann. Außerdem werden mögliche
Algorithmen vorgestellt, in MATLAB implementiert und untersucht.
2
2 Problemstellung Das Problem wird in einer vereinfachten Version betrachtet: Es gibt eine
zusammenhängende Fläche. Diese Fläche muss komplett durch Sendemasten
abgedeckt werden. Das heißt, für jeden Punkt in der Fläche muss es einen
Sendemast geben, sodass der Abstand zwischen dem Punkt und dem Sendemast
maximal der Reichweite eines Sendemasts entspricht. Sendemasten werden als
Kreise modelliert, wobei der Radius die maximale Sendereichweite ist. Störungen
werden also vernachlässigt. Der Abstand zu einem Sendemast ist als der Abstand
zu dessen Mittelpunkt definiert und die Position eines Sendemasts ist auch durch
dessen Mittelpunkt definiert. Alle Sendemasten haben die gleiche
Sendereichweite, die dem Algorithmus zu Beginn übergeben wird. Die
Sendemasten können ausschließlich auf der Fläche, dort aber ohne
Einschränkung, platziert werden.
Ziel ist es, ein Verfahren zu finden, das eine Verteilung der Sendemasten liefert,
die mit möglichst wenigen Sendemasten auskommt. Im optimalen Fall liefert es die
minimale Anzahl.
3 Lösungsstrategien
3.1 Bisherige Ansätze
3.1.1 Der kontinuierliche Fall Am Anfang soll hier vom kontinuierlichen Fall ausgegangen werden. Das bedeutet,
dass die Positionierung der Sendemasten auf der Fläche frei möglich ist, sie also
unendlich genau gesetzt werden können.
Das Problem fällt in das mathematische Feld der Optimierungsprobleme. Als
erstes wird dabei die analytische Lösung untersucht. Wäre es nur ein Sendemast,
den man optimal aufstellen müsste, könnte man eine Funktion aufstellen, wie viel
der Sendemast abdeckt und dann diese Funktion maximieren. Der Standardfall
wird aber mit mehreren Sendemasten sein, da ein einzelner nur für relativ große
Radien die gesamte Fläche abdecken kann. Man braucht also eine Funktion, die
eine Menge von Sendemasten ihrer abgedeckten Fläche zuordnet. Das Problem
ist, dass die Anzahl der Elemente nicht gleich ist. Eine solche Funktion besitzt
keine Ableitung. Wäre die Anzahl der Elemente konstant, könnte man versuchen
die partiellen Ableitungen zu benutzen. Da die Anzahl aber nicht konstant ist, gibt
es auch keine partielle Ableitung, also macht eine analytische Lösung keinen Sinn
3
(Papageorgiou 1991). Ein weiteres Problem ist, dass man die Anzahl an
Sendemasten, die man mindestens braucht, um die Fläche abzudecken, nicht
berechnen kann. Zumindest konnte bisher keine Methode gefunden werden. Dies
liegt daran, dass sich die Bereiche der Sendemasten fast immer überschneiden
müssen und dass ein Teil der Fläche, die von den Sendemasten abgedeckt
werden kann, außerhalb der abzudeckenden Fläche liegt und somit nicht zur
Abdeckung beiträgt. Dieser Verlust an der Außenseite hängt jedoch von der Form
ab.
Abbildung 1: Beispiel zur Abhängigkeit des "Flächenverlustes" an den Rändern von der Form der Fläche
Angenommen man hat eine kreisrunde Fläche, dann kann diese Fläche von einem
Sendemast, der den gleichen Radius wie die Fläche hat, abgedeckt werden. Wenn
man nun aber ein Rechteck, das den gleichen Flächeninhalt besitzt, mit einer
extrem kleinen Seite betrachtet, fällt auf, dass man mehr als einen Sendemast
braucht, solange man den Radius nicht verändert (Abbildung 1). Der Flächeninhalt
ist also eindeutig nicht das einzige Kriterium für die Anzahl der Sendemasten.
Angenommen man fände eine Methode um die Anzahl der Sendemasten zu
berechnen, dann würde das Problem auf die Verteilung dieser Sendemasten
vereinfacht werden. Wahrscheinlich würde die Methode sogar die Verteilung der
Sendemasten gleich mitliefern, da ohne Wissen über die effiziente Verteilung von
Sendemasten es wohl eher unmöglich ist, die Anzahl zu bestimmen.
Der kontinuierliche Fall ist also bisher nicht wirklich vielversprechend, weswegen
im Folgenden der diskrete Fall behandelt wird.
4
3.1.2 Der diskrete Fall Der diskrete Fall ermöglicht nun keine absolut freie Platzierung der Sendemasten
mehr, sondern gibt nur noch eine gewisse Genauigkeit an. Dabei wird später bei
der Umsetzung am Computer eine normale Rastergrafik als abzudeckende Fläche
benutzt. Daher bietet sich die Platzierung auf Pixelebene an. Ein Sendemast wird
also auf die Position eines Pixels gesetzt. Er kann also nicht zwischen Pixel
gesetzt werden. Sinnvoll ist es auch, das Pixel als kleinste Einheit der Länge,
sowie der Fläche zu benutzen. Somit ist eigentlich die Pixel-Kantenlänge die
kleinste Längeneinheit. Es wird aus Gründen der Lesbarkeit weiterhin von Pixel als
Abstand geredet.
Die diskrete Variante eines Kreises wird wie folgt definiert:
Als Mittelpunkt wird ein Pixel festgelegt. Seine Position ist durch seine Koordinaten
(x,y) festgelegt. Der Abstand zweier Pixel wird als normaler euklidischer Abstand
definiert. Zur Kreisfläche gehören alle Pixel, deren Abstand kleiner als der Radius
ist.
Das praktische am diskreten Fall ist, dass es nun nur noch eine endliche Menge an
abzudeckenden Pixel, beziehungsweise möglichen Sendemasten gibt. Bei kleinen
Flächen, also Flächen, die aus wenigen Pixel bestehen, könnte man alle
möglichen Kombinationen durchprobieren. Somit könnte man sicher sein, die beste
Konstellation an Sendemasten zu finden. Die Anzahl der möglichen Kombinationen
steigt aber zu schnell an, um auch bei größeren Flächen genutzt zu werden. Es
muss also ein anderes Verfahren gefunden werden.
Aus der endlichen Anzahl der Pixel leitet sich eine erste Modellierungsmöglichkeit
ab: Man sieht die abzudeckende Fläche als eine Menge von Pixel. Jedem
Sendemast ordnet man die Menge der Pixel zu, die in seinem Sendebereich
liegen. Jeder Sendemast ist also eine Teilmenge der Fläche. Man versucht nun mit
der Vereinigung von möglichst wenigen Teilmengen die gesamte Menge aller Pixel
zu erhalten. Dieses Problem nennt sich „set covering“-Problem. Für dieses
Problem gibt es bisher keine wirklich guten Lösungsmöglichkeiten, außer dem
Greedy-Algorithmus (engl.: greedy – gierig) (Vazirani 2001, 13). Er hat den Vorteil,
dass er relativ schnell ist und dass sein Fehler durch die n-te Harmonische Zahl
beschränkt ist (Vazirani 2001, 12), das heißt: Sei k die Anzahl der Elemente der
größten Teilmenge, dann ist der Quotient aus gelieferter Anzahl an Teilmengen
5
über der optimalen Anzahl durch 1+ ln(k) nach oben beschränkt (Berg, et al. 2010,
135). Dieser Greedy-Algorithmus wird später noch genauer vorgestellt.
Eine weitere Modellierungsmöglichkeit sind Graphen. Graphen sind ein in der
Optimierung häufig eingesetztes Hilfsmittel. Fast jedes Navigationsgerät benutzt
zum Beispiel Graphen um das Straßennetz zu simulieren (Gritzmann und
Brandenberg 2004). Graphen bestehen aus Knoten und Kanten. Kanten können
zwischen den Knoten aufgespannt sein. Kanten und Knoten können auch
gewichtet sein, also irgendeine Art von Wert besitzen. Dieser kleine Einblick sollte
zum Verständnis dieser Facharbeit ausreichen. Für Graphen gibt es relativ viele
Algorithmen (Gritzmann und Brandenberg 2004). Ein Großteil davon, wie zum
Beispiel den kürzesten Weg zu finden, kann man jedoch hier nicht verwenden, da
sich keinerlei Anwendung finden lässt. Den kürzesten Weg kann man zum Beispiel
direkt über den euklidischen Abstand bestimmen. Eine Sorte von Algorithmen sind
jedoch Clustering-Algorithmen. Dabei geht es darum, mehrere Knoten zu größeren
Gruppen, den Clustern, zusammenzufassen. Meist benutzt man solche
Algorithmen um ähnliche Knoten zusammenzufassen (Gritzmann und
Brandenberg 2004). Hier könnte man zum Beispiel versuchen so zu clustern, dass
jeder Cluster einem Sendemast entspricht. Man könnte also jedes Pixel als Knoten
modellieren und die Kanten zwischen zwei Knoten mit dem Abstand gewichten.
Die Bedingung wäre also, dass je zwei Knoten eines Clusters immer einen
Abstand kleiner als der doppelte Radius eines Sendemasts besitzen. Das Problem
dabei ist jedoch, dass fast alle Clustering-Algorithmen, wie zum Beispiel der k-
Means-Algoritmus als Eingabe-Parameter die Anzahl der Cluster braucht
(Gritzmann und Brandenberg 2004) (Wikipedia contributors 2010). Das bedeutet,
man müsste die Anzahl der Sendemasten wissen, was jedoch bisher nicht möglich
ist. Ein Clustering-Algorithmus der nicht die Anzahl der Cluster braucht, funktioniert
analog zum Greedy-Algorithmus (Wikipedia contributors 2010). Er erstellt alle
möglichen Cluster und nimmt den Cluster mit den meisten Knoten und streicht
diese dann aus seinen weiteren Berechnungen. Diese Option ist also durch die
noch folgende, genauere Untersuchung des Greedy-Algorithmus bereits
abgedeckt.
Eine weitere Möglichkeit ist es, sich die optimale Abdeckung auf einer unendlichen
Fläche anzuschauen. Drei Sendemasten sollten also möglichst weit auseinander
6
liegen, damit sie sich so wenig wie möglich überschneiden. Es darf aber auch kein
Zwischenraum zwischen ihnen bleiben. Dies ist genau dann der Fall, wenn sie sich
in genau einem Punkt schneiden und sich symmetrisch um diesen Schnittpunk
platzieren. Man kann also dieses Muster benutzen und über die abzudeckende
Fläche legen, es vielleicht um zum Beispiel fünf Pixel hin und her schieben, damit
es möglichst gut passt. Somit findet man also schnell eine Lösung, die relativ gut
ist, wenn die Fläche im Verhältnis zum Radius relativ groß ist und eher wenige
Einkerbungen hat.
Da es bisher also noch keine Methode gibt, die klar zu favorisieren ist, werden nun
drei Algorithmen vorgestellt und genauer untersucht. Darunter ist auch der
Greedy-Algorithmus.
3.2 Algorithmen Alle drei Algorithmen benutzen ein Bild als Eingabe. Die Bilder sind alle
Rastergrafiken, bestehen also aus einer Matrix an Pixel. Schwarze Pixel
repräsentieren die abzudeckende Fläche, weiße Pixel sind zu vernachlässigen.
Außerdem wird jedem Algorithmus der Radius der Sendemasten übergeben, der
dann für den Durchlauf konstant ist.
Die Abdeckung eines Sendemasts ist die Anzahl der Pixel, die von diesem
Sendemasten abgedeckt werden.
3.2.1 Der Wegstreich-‐Algorithmus Bei diesem Algorithmus ist der Grundgedanke, dass eine optimale Menge an
Sendemasten eine Teilmenge aller möglichen Sendemasten ist.
Durch die konstante Anzahl an Pixel in der Fläche und die minimale Anzahl der
Sendemasten, ist die durchschnittliche Abdeckung an Pixel pro Sendemast also
maximal, wenn man die optimale Konstellation an Sendemasten wählt. Deswegen
wird immer der Sendemast mit der minimalen Abdeckung an Pixel aus der Menge
der möglichen Sendemasten gestrichen. Sobald es ein Pixel gibt, das nur noch von
einem Sendemasten abgedeckt wird, wird der zugehörige Sendemast in die
Lösungsmenge übernommen. Außerdem müssen dann die Pixel, die durch diesen
Sendemast abgedeckt werden im Weiteren nicht mehr berücksichtigt werden, da
sie bereits abgedeckt sind. Der Wegstreich-Algorithmus ist also ein schrumpfender
Algorithmus. Er wählt zu Beginn alle möglichen Sendemasten und verringert diese
Menge.
7
Pseudocode:
1. Bild einlesen und drei Matrizen erstellen. Für jede Position wird gespeichert:
i. In der Matrix „abzudeckend“: ob das Pixel an dieser Position noch
abgedeckt werden muss, ja=1 / nein=0
ii. In der Matrix „abdeckung“: die Anzahl der Pixel, die der Sendemast
an dieser Position abdecken würde, 0 wenn es hier keinen
Sendemast gibt
iii. In der Matrix „abdeckende“: die Anzahl der Sendemasten, die dieses
Pixel abdecken wenn es noch abgedeckt werden muss, sonst 0
2. Die beiden Sonderfälle werden abgefangen: Wenn die Fläche nur ein Pixel
groß ist oder wenn der Radius 1 ist und somit jeder Sendemast gesetzt
werden muss. Dies geschieht, da im nächsten Schritt einer der
Sendemasten gestrichen wird und somit das zugehörige Pixel nicht
abgedeckt werde würde.
3. Suche ein Pixel, das von der minimalen Anzahl an Sendemasten abgedeckt
wird, also das Minimum größer Null in „abdeckende“. Wenn es nur noch
Nullen gibt, sind alle Pixel abgedeckt und es wird abgebrochen.
i. Wenn „abdeckende“ für dieses Pixel eins ist:
a. Den Sendemast suchen, der dieses Pixel abdeckt
b. Diesen Sendemast in die Lösungsmenge verschieben
c. Sein Gebiet in „abzudeckend“ und „abdeckende“ auf Null
setzen
d. Die Anzahl an abgedeckten Pixel für die Sendemasten, die
Teile dieses Gebietes abgedeckt haben, in „abdeckung“ neu
berechnen.
ii. Wenn n=„abdeckende“ für dieses Pixel, größer als eins ist, ist sicher,
dass jedes Pixel mindestens n mal abgedeckt ist. Man kann also n-1
Sendemasten streichen und trotzdem sind alle Pixel noch abgedeckt.
Also n-1 mal:
a. Den Sendemast mit der geringsten Abdeckung streichen, also
in „abdeckung“ auf Null setzen
b. Die Anzahl der abdeckenden Sendemasten in „abdeckende“ in
seinem Abdeckungsgebiet um 1 verringern (bis minimal 0)
4. Wiederhole 3. bis dort die Abbruchbedingung erfüllt ist.
8
3.2.2 Der Kanten-‐Algorithmus Als Kante werden die Pixel definiert, die abgedeckt werden müssen und
gleichzeitig ein nicht mehr abzudeckendes Pixel als Nachbar haben. Die Kante ist
also der Umriss der abzudeckenden Fläche. Am Anfang sind dies also alle
schwarzen Pixel, neben denen sich ein weißes befindet.
Abbildung 2: Beispiel für den Fall, dass die optimalen Sendemasten gleichzeitig die maximale Kantenabdeckung haben
Bei den Beispielen (Abbildung 2) fällt auf, dass hier die Sendemasten der
optimalen Sendemasten-Konstellation (die weißen Punkte) gleichzeitig auch
maximal viel Kante abdecken. Deswegen wurde untersucht, wie gut die Verteilung
ist, wenn man immer den Sendemast setzt, der am meisten Kante abdeckt. Dieser
Algorithmus ist ein wachsender Algorithmus, da in jedem Schleifendurchlauf ein
Sendemast gewählt wird und der Lösungsmenge hinzugefügt wird.
Pseudocode:
1. Bild einlesen und drei Matrizen erstellen. Für jede Position wird gespeichert:
i. In der Matrix „abzudeckend“: ob das Pixel an dieser Position noch
abgedeckt werden muss, ja=1 / nein=0
ii. In der Matrix „kante“: ob das Pixel an dieser Position zur Kante
gehört, ja=1 / nein=0
iii. In der Matrix „abdeckung“: die Anzahl der Kanten-Pixel, die der
Sendemast an dieser Position abdecken würde
2. Solange es einen Sendemast mit Kanten-Abdeckung größer null in
„abdeckung“ gibt:
i. Setze den Sendemast mit der höchsten Abdeckung
ii. In seinem Sendebereich setze die Werte von „abzudeckend“ auf 0
iii. Berechne die neue Kante in diesem Bereich für „kante“
iv. Berechne die neue Kanten-Abdeckung der Sendemasten in diesem
Gebiet für „abdeckung“
9
3.2.3 Der Greedy-‐Algorithmus Wie bereits erwähnt, setzt dieser Algorithmus immer den Sendemast mit der
höchsten Abdeckung. Er funktioniert analog zum Kanten-Algorithmus und ist daher
auch wachsend.
Pseudocode:
1. Bild einlesen und zwei Matrizen erstellen. Für jede Position wird
gespeichert:
i. In der Matrix „abzudeckend“: ob das Pixel an dieser Position noch
abgedeckt werden muss, ja=1 / nein=0
ii. In der Matrix „abdeckung“: die Anzahl der Pixel, die der Sendemast
an dieser Position abdecken würde, 0 wenn es hier keinen
Sendemast gibt
2. Solange es einen möglichen Sendemast gibt:
i. Setze den Sendemast mit der höchsten Abdeckung (Maximum aus
„abdeckung“)
ii. Markiere sein Gebiet als abgedeckt in „abzudeckend“
iii. Berechne die neuen Werte für Sendemasten in der Umgebung
3.3 Analyse der Algorithmen Es wurden zwei Bilder als Eingabe verwendet. Einmal eine Deutschlandkarte und
einmal ein Kreis mit Radius 50. Für den Kreis wurden die Algorithmen jeweils mit
einem Radius von 1 bis 50 laufen gelassen. Für die Deutschlandkarte von 1 bis
100. Es wurde jeweils die Anzahl an benötigten Sendemasten notiert.
Den Kreis mit Radius 50 und den Sendemastenradius von 50 kann man als Test
ansehen. Im optimalen Fall setzt der Algorithmus genau den einen, benötigten
Sendemast in die Mitte. Jeder Algorithmus der wesentlich mehr Sendemasten
braucht ist nicht vielversprechend. Alle drei Algorithmen erfüllen aber diesen Test
(Abbildung 10).
Die drei Algorithmen terminieren und sind in sofern korrekt, dass die ausgegebene
Sendemasten-Konstellation die Fläche komplett abdeckt.
Gezeigt ist hier jeweils die Verteilung der Sendemasten (als weiße Punkte
dargestellt) für einen Radius von 10 Pixel.
10
Abbildung 3: Verteilung der Sendemasten in Deutschland Wegstreich-Algorithmus
11
Abbildung 4: Verteilung der Sendemasten in Deutschland Kanten-Algorithmus
12
Abbildung 5: Verteilung der Sendemasten in Deutschland Greedy-Algorithmus
13
Abbildung 9: Anzahl der Sendemasten für Deutschland
1
10
100
1000
10000
100000
0 10 20 30 40 50 60 70 80 90 100
Anzahl der Sendem
asten
Radius
Wegstreichen Kanten-‐Algorithmus Greedy-‐Algorithmus
Abbildung 6: Verteilung der Sendemasten im Kreis, Wegstreich-Algorithmus
Abbildung 7: Verteilung der Sendemasten im Kreis, Kanten-Algorithmus
Abbildung 8: Verteilung der Sendemasten im Kreis, Greedy-Algorithmus
14
Abbildung 10: Anzahl der Sendemasten für den Kreis
3.3.1 Der Wegstreich-‐Algorithmus Der Wegstreich-Algorithmus ist der langsamste der drei. Wie man sieht, kommt es
häufiger zu kleinen Clustern (Abbildung 3). Dies liegt daran, dass die weniger
abdeckenden Sendemasten von außen schon weggestrichen wurden. Wenn jetzt
aber ein Sendemast in die Lösungsmenge übernommen werden muss, kann es zu
Bereichen kommen, die nur noch von Sendemasten abgedeckt werden, die sich
mit dem übernommenen Sendemast stark überschneiden. Eine Möglichkeit, dies
zu umgehen wäre es, die gestrichenen Sendemasten im Umfeld um den
übernommenen Sendemast wieder hinzuzufügen. Dies würde den Algorithmus
aber noch langsamer machen, da somit die Anzahl der möglichen Sendemasten
zwischendurch immer wieder steigen würde. Das würde bedeuten, dass fast alle
Sendemasten mehrmals gestrichen werden müssten. Damit würde der Aufwand
also drastisch erhöht werden. Jedoch tritt bei diesem Algorithmus das Phänomen
seltener auf, dass er für einen größeren Radius mehr Sendemasten braucht als für
einen kleineren Radius (Abbildung 9).
1
10
100
1000
10000
0 5 10 15 20 25 30 35 40 45 50
Anzahl der Sendem
asten
Radius
Wegstreichen Kante Greedy
15
Das schlechte Verhalten beim Kreis ist auch mit den Clustern zu erklären
(Abbildung 6). Die Sendemasten werden von außen her weggestrichen. Wenn
dann ein Sendemast übernommen wird, entstehen Flächen, die nur noch von
Sendemasten abgedeckt werden, die sich mit diesem Sendemast stark
überschneiden. Der Wegstreich-Algorithmus braucht also eine Art „Schwachstelle“
in der Fläche, von wo aus er sich ausbreiten kann.
3.3.2 Der Kanten-‐Algorithmus Der Kanten-Algorithmus ist in etwa so schnell wie der Greedy-Algorithmus. Er
liefert jedoch so gute oder teilweise bessere Ergebnisse wie der Wegstreich-
Algorithmus (Abbildung 4, Abbildung 7). Leider tritt hier jedoch das Phänomen,
dass für einen größeren Radius mehr Sendemasten gebraucht werden, wesentlich
häufiger auf (Abbildung 9). Man könnte also den Algorithmus jedes Mal für etwas
kleinere Radien laufen lassen, um zu überprüfen, ob man nicht vielleicht doch mit
weniger Sendemasten auskommt. Dies würde den Rechenaufwand jedoch auch
stark erhöhen, was also auch nicht praktikabel ist. Man könnte sonst vielleicht die
Kanten unterschiedlich gewichten, zum Beispiel in Abhängigkeit davon, wie oft sie
abgedeckt werden.
3.3.3 Der Greedy-‐Algorithmus Der Greedy-Algorithmus ist, wie bereits erwähnt, relativ schnell. Bei der
Deutschlandkarte braucht er mindestens 7% mehr Sendemasten als das Minimum
der andern beiden und im Durchschnitt sogar 40% mehr (Abbildung 5, Abbildung
8, Abbildung 9). Diese Ineffektivität lässt sich anhand einer Analogie gut
beschreiben: Jeder, der schon einmal Kreise aus einem Blatt Papier ausschneiden
musste, kann das nachvollziehen. Der Greedy-Algorithmus platziert sozusagen
erst die Kreise und schneidet sie aus. Es bleibt aber natürlich eine Art Gerippe
übrig. Jeder weitere „Kreis“ wird also jetzt einen Großteil an Fläche enthalten, die
zu einem anderen Kreis gehören. Der Greedy-Algorithmus liefert also
Konstellationen, die nicht sehr effektiv sind. Eine Möglichkeit, ihn zu verbessern,
wäre es aber zum Beispiel, immer wieder einzelne, bereits gesetzte Sendemasten
zu streichen. Außerdem könnte man die Kante stärker gewichten oder auch eine
Gewichtung in Abhängigkeit von der Anzahl abdeckender Sendemasten einführen.
16
Abbildung 11: Effizienz für Deutschland
Abbildung 12: Effizienz für den Kreis
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
0 10 20 30 40 50 60 70 80 90 100
Ef4izienz
Radius
Wegstreich-‐Algorithmus Kanten-‐Algorithmus Greedy-‐Algorithmus
0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
0 5 10 15 20 25 30 35 40 45 50
Ef4izienz
Radius
Wegstreich-‐Algorithmus
Kanten-‐Algorithmus
Greedy-‐Algorithmus
17
3.4 Analyse des Problems Bisher wurden also die Algorithmen untersucht, wie gut sie dafür geeignet sind
eine optimale Verteilung der Sendemasten zu finden. Nun soll es aber um das
Problem an sich gehen. Macht es also zum Beispiel mehr Sinn viele kleine
Sendemasten oder eher wenige große Sendemasten aufzustellen. Dazu werden
jeweils zwei Grafiken verwendet. Einmal wird die Anzahl der benötigten
Sendemasten in Abhängigkeit vom Radius dargestellt (Abbildung 9, Abbildung 10).
Dabei ist die logarithmische Skalierung der Anzahl zu beachten. Zum andern
wurde die Effizienz als Funktion des Radius dargestellt (Abbildung 11, Abbildung
12). Als Effizienz wird der Quotient von abzudeckender Fläche über abdeckbarer
Fläche bezeichnet. Die abdeckbare Fläche ist die Fläche, die man abdecken
könnte, wenn die Sendemasten sich nicht überschneiden müssten und sie auch
am Rand keine Fläche verlieren würden. Man kann die Fläche berechnen durch
Fläche pro Sendemast mal Anzahl der Sendemasten.
Wenn man die Effizienz betrachtet, fällt auf, dass sie 1 wird für den Radius 1 und
beim Kreis auch für den Radius 50. Dieser Fall, also dass Kreise die Fläche perfekt
beschreiben können, ist so selten, dass eine weitere Betrachtung hier nicht
durchgeführt wird. Sonst fällt auf, dass die Effizienz schon für einen Radius von 10
auf circa 0,6 gefallen ist. Danach nimmt sie langsamer ab. Man kann dabei immer
eine Art Zackenmuster erkennen. Dies kommt zustande indem die Anzahl der
Sendemasten für ein paar Radien konstant ist und erst dann wieder niedriger wird.
Solange die Anzahl der Sendemasten konstant ist, fällt die Effizienz aufgrund der
größeren abdeckbaren Fläche. Wenn die Anzahl der Sendemasten dann aber fällt,
wird die abdeckbare Fläche wieder kleiner, wodurch die Effizienz steigt.
Wenn man sich die Anzahl der Sendemasten anschaut, fällt auf, dass sie am
Anfang für kleine Radien extrem fällt. Von 1 auf 2 sinkt die Anzahl auf ein Achtel
des Startwertes. Dieser Abfall geht dann weiter, auch wenn er langsamer ist, bis er
irgendwann bei 1 ankommt. Für die Deutschlandkarte müsste dies bei einem
Radius von circa 190 passieren.
Um Aussagen treffen zu können welche Konstellation am günstigsten ist, wären
einige Informationen wichtig. Wie hoch sind die Errichtungskosten und laufenden
Kosten pro Sendemast? Gibt es Kosten, die sich wie die möglich abdeckbare
Fläche verhalten? Da solche Informationen fehlen, kann keine genaue Aussage
getroffen werden. Es sollen aber ein paar Szenarien besprochen werden.
18
Angenommen es gibt Kosten, die sich nach der möglich abdeckbaren Fläche
richten und angenommen diese Kosten sind ausschlaggebend. Dann sind
eindeutig kleine Radien zu bevorzugen, da sie eine wesentlich bessere Effizienz
besitzen. Bei einem Radius von 10 ist die Anzahl auch schon sehr stark
geschrumpft, wodurch die Anzahl auf ein verträgliches Niveau gesunken ist,
welches sich auch managen lässt. Wenn hingegen die laufenden Kosten, die
proportional zur Anzahl an Sendemasten sind, die ausschlaggebenden Kosten
sind, sollt man natürlich eher größere Radien benutzen. Gleiches gilt auch, wenn
man den Radius nicht ganz genau weiß, denn für die größeren Radien macht der
einzuplanende Puffer dann keine so große Änderung der benötigten Anzahl aus.
3.5 Bewertung Gesucht war eine Methode um eine gute Verteilung der Sendemasten zu finden.
Die vorgestellten Algorithmen bieten alle schon gewisse Ansätze, haben aber
jeweils ihre Probleme. Im Moment bevorzuge ich den Kanten-Algorithmus, da er
relativ schnell ist und in vielen Fällen das beste Ergebnis geliefert hat. Ein Problem
ist bisher jedoch, dass die Struktur der Lösung beziehungsweise des Problems
noch nicht ganz klar ist. Was ich damit meine: Das ganze nochmals am Beispiel
der Navigation verdeutlicht: Wenn man nur alle Straßen, ihre Länge und die
jeweilige Höchstgeschwindigkeit kennt, ist es schwer einen schnellen und guten
Algorithmus zu entwickeln. Wenn man jedoch die Struktur des Straßennetzes
kennt und weiß, dass es hierarchisch aufgebaut ist, kann man dies nutzen.
Gleiches gilt, wenn man weiß, dass die meisten Städte meist nur über ein paar
Straßen verlassen werden können. Durch dieses Wissen über die Struktur können
wesentlich schnellere und bessere Algorithmen entworfen werden.
Eine solche Struktur, wie man die Sendemasten am effektivsten verteilt, konnte ich
bisher nicht erkennen. Eine Möglichkeit wäre es also zum Beispiel nun für mehrere
Flächen jeweils für einen gegebenen Radius durch Ausprobieren aller
Möglichkeiten alle optimalen Kombinationen an Sendemasten zu finden. Wenn
man genügend unterschiedliche Flächen benutzt, kann man jeweils die Verteilung
untersuchen und vielleicht gewisse Muster erkennen. Dass sich solche
Informationen lohnen, sieht man meiner Meinung nach am Vergleich von Greedy-
Algorithmus und Kanten-Algorithmus. Der Greedy-Algorithmus ist für das
allgemeine set covering Problem die Standardlösung. Der Kanten-Algorithmus ist
aber effektiver, obwohl er fast gleich funktioniert. Der einzige Unterschied ist, dass
19
er die Kante benutzt. Er kennt also besondere Elemente der Teilmengen. Die
Nutzung dieser Besonderheit der Kanten-Pixel macht den Kanten-Algorithmus also
effektiver. Er setzt also Informationen über die Struktur ein, um effektiver zu sein.
4 Ausblick In dieser Facharbeit wollte ich untersuchen, wie man das Problem der
Sendemasten-Verteilung mathematisch modellieren kann. Meiner Einschätzung
nach sind die beiden Optionen, also eine Menge von Punkten beziehungsweise ein
Graph, die sinnvollsten Ansätze. Dies liegt daran, dass die Fläche aus kleinsten
Einheiten besteht, welche jeweils abgedeckt sind oder eben nicht. Somit macht es
für mich Sinn, dieses Problem durch diese kleinsten Flächen zu modellieren, egal
ob als Element einer Menge oder als ein Knoten in einem Graphen. Bei den
Algorithmen bin ich mir nicht sicher. Der Kanten-Algorithmus ist zwar schon recht
gut jedoch gibt es noch eine weitere Herangehensweise, die hier nicht näher
besprochen wurde. Diese Möglichkeit sind sogenannte evolutionäre Algorithmen.
Hier versucht man das recht erfolgreiche Prinzip der biologischen Evolution zu
übertragen. Man könnte hier also mit einem Pool an „Individuen“, in diesem Fall
mögliche Sendemasten-Konstellationen, beginnen und dann durch Mutation, also
leichter Veränderung, und durch Rekombination der Konstellationen immer wieder
neue Kombinationen finden. Durch Selektion würden dann die schlechten wieder
gestrichen werden, bis zum Schluss nur noch eine Konstellation übrig bleibt.
Solche evolutionäre Algorithmen werden für solche Probleme, bei denen keine
anderen guten Algorithmen existieren, häufig eingesetzt (Weicker 2007, 42).
Außerdem könnte man diese Algorithmen kombinieren. So kann man den Kanten-
Algorithmus zum Beispiel nutzen, um am Anfang „Individuen“ zu erschaffen. Somit
wüsste man, dass man einer optimalen Konstellation schon recht nah ist.
Interessante Fragen wären für mich nun, wie sich ein verbesserter
Kanten-Algorithmus im Vergleich zu einem guten evolutionären Algorithmus
verhält. Auch wäre eine genauere Untersuchung der optimalen Lösungen
interessant, um zum Beispiel zu sehen, ob es gewisse Hot-Spots gibt, also
Bereiche, in denen in jeder optimalen Lösung ein Sendemast steht.
20
5 Literaturverzeichnis Berg, Mark, Otfried Cheong, Marc Kreveld, und Mark Overmars. Computational Geometry: Algorithms and Applications. Berlin: Springer Verlag, 2010.
Gritzmann, Peter, und René Brandenberg. Das Geheimnis des kürzesten Weges: Ein mathematisches Abenteuer. Berlin: Springer Verlag, 2004.
Papageorgiou, Markos. Optimierung. Statische, dynamische, stochastische Verfahren für die Anwendung. München: R. Oldenbourg Verlag, 1991.
Vazirani, Vijay V. Approximation Algorithms. Berlin: Springer Verlag, 2001.
Weicker, Karsten. Evolutionärer Algorithmus. Wiesbaden: Teubner Verlag, 2007.
Wikipedia contributors. Cluster analysis. Wikipedia, The Free Encyclopedia. 21. 04 2010. http://en.wikipedia.org/w/index.php?title=Cluster_analysis&oldid=357486081 (Zugriff am 25. 04 2010).
6 Anhang - Wegstreich-Algorithmus in MATLAB implementiert
- Kanten-Algorithmus in MATLAB implementiert
- Greedy-Algorithmus in MATLAB implementiert
- selbstgeschriebene Hilfsfunktionen in MATLAB implementiert
- CD mit:
o Wegstreich-Algorithmus in MATLAB implementiert
o Kanten-Algorithmus in MATLAB implementiert
o Greedy-Algorithmus in MATLAB implementiert
o selbstgeschriebene Hilfsfunktionen in MATLAB implementiert
o die Deutschlandkarte und der Kreis als Eingabe-Bild
o die ausgegebenen Verteilungen für den Radius 10 (als Bilder)
o die Auswertungstabelle, auf der die Diagramme basieren
12.05.10 17:09 /Users/malte/Dropbox/.../wegstreich_algorithmus.m 1 of 2
function numberOfTowers= wegstreich_algorithmus(file,radius)% This algorithm expects a RGB picrue in the png format.% Also it needs the radius of a tower.% It returns the number of towers and also writes a png file in which the% towers are marked as red pixel%%read in the image and get its dimensionspicture = imread(file,’png’);[sizeX,sizeY,~]=size(picture);mapOfTowers=zeros(sizeX,sizeY);mapToCover=zeros(sizeX,sizeY);mapCovering=zeros(sizeX,sizeY);%initialize the matrixesfor x = 1:sizeX for y = 1:sizeY if picture(x,y,1)==0 && picture(x,y,2)==0 && picture(x,y,3)==0 mapOfTowers(x,y)=1; mapToCover(x,y)=1; mapCovering(x,y)=1; end endendmapOfTowers = coverageInArea(sizeX,sizeY,mapToCover,mapOfTowers,1,sizeX,1,sizeY,radius);mapCovering = initializeCoverage(sizeX,sizeY,radius,mapCovering,mapOfTowers);%find the tower with the least coverage[x,y,minimum]=findMinimum(mapOfTowers,sizeX,sizeY);%check for special cases radius =1 or area = 1 pixelwhile minimum==1 mapOfTowers(x,y)=0; mapToCover(x,y)=0; mapCovering(x,y)=0; picture(x,y,1)=255; picture(x,y,2)=0; picture(x,y,3)=0; [x, y, minimum] = findMinimum(mapOfTowers,sizeX,sizeY);end%find the tower with the least coverage[xa,ya,minimumCovering]= findMinimum(mapCovering,sizeX,sizeY);while minimumCovering ~=0 if minimumCovering ==1 %find the tower to be set and set it [x,y]=findTower(mapOfTowers,xa,ya,radius,sizeX,sizeY); picture(x,y,1)=255; picture(x,y,2)=0; picture(x,y,3)=0; mapOfTowers(x,y)=0; %mark its pixel as covered and calculate the new values mapToCover = markAsCovered(mapToCover,radius,x,y,sizeX,sizeY); mapCovering= markAsCovered(mapCovering,radius,x,y,sizeX,sizeY); mapOfTowers = coverageInArea(sizeX,sizeY,mapToCover,mapOfTowers,x 2*radius,x+2*radius,y 2*radius,y+2*radius,radius); else %erase minimumCovering 1 towers and calculate the new values for i = 2:minimumCovering [x, y,~] = findMinimum(mapOfTowers,sizeX,sizeY); mapOfTowers(x,y)=0; mapCovering=decreaseCovering(mapCovering,radius,x,y,sizeX,sizeY); end end
12.05.10 17:09 /Users/malte/Dropbox/.../wegstreich_algorithmus.m 2 of 2
%find the tower with the least coverage [xa,ya,minimumCovering]= findMinimum(mapCovering,sizeX,sizeY);end%count all towersnumberOfTowers =countTowers(picture,sizeX,sizeY);disp([’radius: ’,num2str(radius),’ amount of towers: ’,num2str(numberOfTowers)]);imwrite(picture,[file,’_wegstreichen_’,num2str(radius),’.png’],’png’);image(picture);axis equal;
12.05.10 17:08 /Users/malte/Dropbox/Fach.../kanten_algorithmus.m 1 of 1
function numberOfTowers= kanten_algorithmus(file,radius)% This algorithm expects a RGB picrue in the png format.% Also it needs the radius of a tower.% It returns the number of towers and also writes a png file in which the% towers are marked as red pixel%%read in the image and get its dimensionspicture = imread(file,’png’);[sizeX,sizeY,~] = size(picture);mapOfTowers=zeros(sizeX,sizeY);mapToCover =zeros(sizeX,sizeY);mapOfEdges =zeros(sizeX,sizeY);%initialize the matrixesfor x = 1:sizeX for y = 1:sizeY if picture(x,y,1)==0 && picture(x,y,2)==0 && picture(x,y,3)==0 mapOfTowers(x,y)=1; mapToCover(x,y)=1; end endendmapOfEdges=calculateEdges(mapOfEdges,mapToCover,1,sizeX,1,sizeY,sizeX,sizeY);mapOfTowers = edgeCoverageInArea(sizeX,sizeY,mapOfTowers,mapToCover,mapOfEdges,1,sizeX,1,sizeY,radius);%get the best tower[x, y, minimum] = findMaximum(mapOfTowers,sizeX,sizeY);while minimum ~=0 %mark this pixel as a tower picture(x,y,1)=255; picture(x,y,2)=0; picture(x,y,3)=0; %mark its pixel as covered and calculate the new values mapToCover=markAsCovered(mapToCover,radius,x,y,sizeX,sizeY); mapOfEdges=calculateEdges(mapOfEdges,mapToCover,x radius,x+radius,yradius,y+radius,sizeX,sizeY); mapOfTowers = edgeCoverageInArea(sizeX,sizeY,mapOfTowers,mapToCover,mapOfEdges,x 2*radius,x+2*radius,y 2*radius,y+2*radius,radius); %find the new maximum [x, y, minimum] = findMaximum(mapOfTowers,sizeX,sizeY);end%count all towersnumberOfTowers =countTowers(picture,sizeX,sizeY);disp([’radius: ’,num2str(radius),’ amount of towers: ’,num2str(numberOfTowers)]);imwrite(picture,[file,’_kanten_’,num2str(radius),’.png’],’png’);image(picture);axis equal;
12.05.10 17:09 /Users/malte/Dropbox/Fach.../greedy_algorithmus.m 1 of 1
function numberOfTowers = greedy_algorithmus(file,radius)% This algorithm expects a RGB picrue in the png format.% Also it needs the radius of a tower.% It returns the number of towers and also writes a png file in which the% towers are marked as red pixel%%read in the image and get its dimensionspicture = imread(file,’png’);[sizeX,sizeY,~]=size(picture);mapOfTowers=zeros(sizeX,sizeY);mapToCover=zeros(sizeX,sizeY);%initialize the matrixesfor x = 1:sizeX for y = 1:sizeY if picture(x,y,1)==0 && picture(x,y,2)==0 && picture(x,y,3)==0 mapOfTowers(x,y)=1; mapToCover(x,y)=1; end endendmapOfTowers = coverageInArea(sizeX,sizeY,mapToCover,mapOfTowers,1,sizeX,1,sizeY,radius);%get the best tower[x, y, maximum] = findMaximum(mapOfTowers,sizeX,sizeY);while maximum ~=0 %mark this pixel as a tower mapOfTowers(x,y)=0; picture(x,y,1)=255; picture(x,y,2)=0; picture(x,y,3)=0; %mark its pixel as covered and calculate the new values mapToCover=markAsCovered(mapToCover,radius,x,y,sizeX,sizeY); mapOfTowers = coverageInArea(sizeX,sizeY,mapToCover,mapOfTowers,x2*radius,x+2*radius,y 2*radius,y+2*radius,radius); %find the new maximum [x, y, maximum] = findMaximum(mapOfTowers,sizeX,sizeY);end%count all towersnumberOfTowers =countTowers(picture,sizeX,sizeY);disp([’radius: ’,num2str(radius),’ amount of towers: ’,num2str(numberOfTowers)]);imwrite(picture,[file,’_greedy_’,num2str(radius),’.png’],’png’);image(picture);axis equal;
12.05.10 17:09 /Users/malte/Dropbox/Facharbe.../calculateEdges.m 1 of 1
function mapOfEdges = calculateEdges(mapOfEdges,mapToCover,xmin,xmax,ymin,ymax,sizeX,sizeY)% for the given area the edge is newly computed %for each pixel in the areafor x = xmin:xmax if x<1 continue end if x>sizeX break end for y = ymin:ymax if y<1 continue end if y>sizeY break end mapOfEdges(x,y)=0; %default: no edge if mapToCover(x,y)==1 %if this pixel has to be covered: check the four neighbours if y 1 >0 if mapToCover(x,y 1)==0 mapOfEdges(x,y)=1; end end if y+1<sizeY if mapToCover(x,y+1)==0 mapOfEdges(x,y)=1; end end if x 1 >0 if mapToCover(x 1,y)==0 mapOfEdges(x,y)=1; end end if x+1<sizeX if mapToCover(x+1,y)==0 mapOfEdges(x,y)=1; end end end endend
12.05.10 17:09 /Users/malte/Dropbox/Facharbeit/.../countTowers.m 1 of 1
function numberOfTowers =countTowers(picture,sizeX,sizeY)%count all red pixels (=towers)numberOfTowers =0;for x =1:sizeX for y=1:sizeY if picture(x,y,1)==255 && picture(x,y,2)==0 numberOfTowers=numberOfTowers+1; end endend
12.05.10 17:09 /Users/malte/Dropbox/Facharbeit/abg.../coverage.m 1 of 1
function sum = coverage(sizeX,sizeY,mapToCover,radius,x,y)%calculates the coverage of a given tower sum = 0;for i=x radius+1:x+radius 1 if i <1 continue end if i>sizeX break end for j=y radius+1:y+radius 1 if j<1 continue end if j>sizeY break end if (x i)*(x i)+(y j)*(y j) radius*radius <0 %based on Pythagorean theorem: the pixel is in the circle if mapToCover(i,j)==1 sum=sum+1; end end endend
12.05.10 17:10 /Users/malte/Dropbox/Facharbe.../coverageInArea.m 1 of 1
function mapOfTowers= coverageInArea(sizeX,sizeY,mapToCover,mapOfTowers,xmin,xmax,ymin,ymax,radius)%for each tower in the area the new coverage is calculatedfor x =xmin:xmax if x <1 continue end if x>sizeX break end for y=ymin:ymax if y<1 continue end if y>sizeY break end if mapOfTowers(x,y)~=0 %if there is a tower, calculate the new value mapOfTowers(x,y)=coverage(sizeX,sizeY,mapToCover,radius,x,y); else mapOfTowers(x,y)=0; end endend
12.05.10 17:10 /Users/malte/Dropbox/Fachar.../decreaseCovering.m 1 of 1
function mapCovering=decreaseCovering(mapCovering,radius,x,y,sizeX,sizeY)%decrease coverage of all pixel, which were covered by the%tower at position x,yfor i = x radius+1:x+radius 1 if i <1 continue end if i>sizeX break end for j=y radius+1:y+radius 1 if j<1 continue end if j>sizeY break end if (x i)*(x i)+(y j)*(y j) < radius*radius %based on Pythagorean theorem: in the circle if mapCovering(i,j) >0 mapCovering(i,j)=mapCovering(i,j) 1; end end endend
12.05.10 17:10 /Users/malte/Dropbox/Fach.../edgeCoverageInArea.m 1 of 1
function mapOfTowers = edgeCoverageInArea(sizeX,sizeY,mapOfTowers,mapToCover,mapOfEdges,xmin,xmax,ymin,ymax,radius)%for each pixel in the area calculate the coverage of the tower, if the%pixel itself still has to be coveredfor x =xmin:xmax if x <1 continue end if x>sizeX break end for y=ymin:ymax if y<1 continue end if y>sizeY break end if mapToCover(x,y)==1 %if this pixel has to be covered: calculate the edge coverage %of the tower at this position mapOfTowers(x,y)=coverage(sizeX,sizeY,mapOfEdges,radius,x,y); else mapOfTowers(x,y)=0; end endend
12.05.10 17:11 /Users/malte/Dropbox/Facharbeit/.../findMaximum.m 1 of 1
function [x,y,max] = findMaximum(map,sizeX,sizeY)%returns the position of, and the maximum itselfp=[1 1];max=map(1,1);for x=1:sizeX for y=1:sizeY if map(x,y)>max p=[x y]; max = map(x,y); end endendx=p(1);y=p(2);end
12.05.10 17:11 /Users/malte/Dropbox/Facharbeit/.../findMinimum.m 1 of 1
function [x,y,min]=findMinimum(map,sizeX,sizeY)%returns the position of, and the minimum itselfp=[1 1];min=map(1,1);for x=1:sizeX for y=1:sizeY if map(x,y)>0 && (map(x,y)<min || min==0) p=[x y]; min = map(x,y); end endendx=p(1);y=p(2);end
12.05.10 17:11 /Users/malte/Dropbox/Facharbeit/ab.../findTower.m 1 of 1
function [x,y]=findTower(mapOfTowers,xa,ya,radius,sizeX,sizeY)%find the tower which covers this pixelfound = 0; for i = xa radius+1:xa+radius 1 if i<1 continue end if i > sizeX || found==1 break end for j =ya radius+1:ya+radius 1 if j<1 continue end if j>sizeY break end if (xa i)*(xa i)+(ya j)*(ya j)<radius*radius %based on Pythagorean theorem: in the circle if mapOfTowers(i,j)>0 x=i; y=j; found =1; break end end endend
12.05.10 17:11 /Users/malte/Dropbox/Fach.../initializeCoverage.m 1 of 1
function mapCovering = initializeCoverage(sizeX,sizeY,radius,mapCovering,mapOfTowers) %for each pixel increment the coverage count by 1 for each covering towerfor i =1:sizeX for j=1:sizeY if mapCovering(i,j)==1 for x=i radius+1:i+radius 1 if x < 1 continue end if x >sizeX break end for y=j radius+1:j+radius 1 if y <1 continue end if y >sizeY break end if (x i)*(x i)+(y j)*(y j)<radius*radius if mapOfTowers(x,y)>=1 mapCovering(i,j)=mapCovering(i,j)+1; end end end end end endend%decrease all values by 1, because 1 was used to mark themfor i =1:sizeX for j=1:sizeY if mapCovering(i,j)>0 mapCovering(i,j)=mapCovering(i,j) 1; end endend
12.05.10 17:12 /Users/malte/Dropbox/Facharbei.../markAsCovered.m 1 of 1
function map = markAsCovered(map,radius,posx,posy,sizeX,sizeY)%in a circle around the given pixel all values are zeroed for x = posx radius+1:posx+radius 1 if x<1 continue end if x>sizeX break end for y=posy radius+1:posy+radius 1 if y<1 continue end if y>sizeY break; end if (x posx)*(x posx)+(y posy)*(y posy) radius*radius <0 %based on Pythagorean theorem: in the circle %set the value to 0 = covered map(x,y)=0; end endend
Ich erkläre hiermit, dass ich die Facharbeit „Planare Standortprobleme am Beispiel von Sendemasten“ selbstständig und nur unter Zuhilfenahme der angegebenen Quellen erarbeitet habe. (Malte Schledjewski)
