Rasenmäherproblem
Das Rasenmäherproblem ist ein Problem in der algorithmischen Geometrie. Anschaulich wird gefragt, wie man zu einer gegebenen Fläche (einem „Rasen“) und einem gegebenen Rasenmäher eine Route bestimmt, die den ganzen Rasen mäht und dabei die kürzeste unter allen möglichen Routen ist.
Zur Formalisierung definiert man sich folgende Begriffe:[1]
- Gegeben ein Gebiet (ein Rasen) . Per Diskretisierung nehmen wir an, dass aus endlich vielen mehrfach zusammenhängenden polygonalen Komponenten besteht. Notiere mit die Anzahl der Ecken und mit den Rand von . Sei außerdem ein Rasenmäher , das heißt ein Polygon um einen Koordinatenursprung, gegeben. Bezeichne für ein mit die Platzierung von in , das heißt die Parallelverschiebung von um den Ortsvektor von .
- Manchmal ist man auch an einer Fräsetour interessiert. Damit ist eine Schneidetour gemeint, die keinen Punkt außerhalb von „mäht“, das heißt, es gilt (S) mit Gleichheit.
- Das Rasenmäherproblem fragt nach einer Schneidetour mit minimaler Länge. Das Fräsungsproblem fragt nach einer minimalen Fräsetour oder alternativ nach einem Beweis dafür, dass keine Fräsetour existiert.
Obwohl für den Rasenmäher viele Figuren denkbar wären, sind praktisch nur das Einheitsquadrat und der Einheitskreis als Rasenmäher interessant und gut untersucht.[2]
- Einfache Beobachtungen
-
(Abb. 1) Das Fräsungsproblem
-
(Abb. 2) Für kombinatorisch sehr einfache Rasenflächen (hier ) kann die kombinatorische Darstellung der kürzesten Schneidetour potentiell unbegrenzt groß sein.
-
(Abb. 3) Achsenparalleles Rasenmähen und …
-
(Abb. 4) … kantenparalleles Rasenmähen.
Wegen des Phänomens, das in Abbildung 2 illustriert wird, definiert man die Komplexität einer Eingangsgröße des Rasenmäherproblems nicht als , sondern als die Länge einer Zahlendarstellung der Koordinaten der Eckpunkte von . Mit diesem Verständnis der Eingangsgröße lassen sich Pseudopolynomielle Algorithmen finden, die das Rasenmäherproblem lösen.
Arkin, Fekete & Mitchell (2000) schlagen für das Rasenmäherproblem eine Reduktion auf das Hamiltonkreisproblem in planaren bipartiten Graphen mit Maximalgrad 3 vor. Sie zitieren dann das Argument von Johnson & Papadimitriou (1985), um zu beweisen, dass das Rasenmäherproblem schon für Polygone NP-schwer ist. Dasselbe Argument wenden sie auch auf das Fräsungsproblem an, können dort aber nur zeigen, dass es für mehrfach zusammenhängende polygonale Gebiete NP-schwer ist. Sie schlagen außerdem einen einfachen Approximationsalgorithmus für beide Probleme vor:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/35/Runde_pixel.png/220px-Runde_pixel.png)
- Bestimme einen Gittergraphen so, dass die Mittelpunkte derjenigen Pixel enthält, die mit schneiden.
- Benutze eine bekannte Approximationsmethode für das Rundreiseproblem.
Schritt 1 hat eine Laufzeit von , dabei ist die Mächtigkeit von .
Literatur
[Bearbeiten | Quelltext bearbeiten]- E.M. Arkin, S.P. Fekete, J.S.B. Mitchell: Approximation algorithms for lawn mowing and milling. In: Computational Geometry. 17. Jahrgang, Nr. 1–2, 2000, S. 25–50 (edu.au [PDF]).
- D.S. Johnson, C.H. Papadimitriou: The Traveling Salesman Problem. John-Wiley and Sons, Ltd., 1985, ISBN 0-471-90413-9, Computational complexity, S. 37–86.