nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

8. Räumliche Analyse durch kombinatorische Optimierung

verfasst von : Jan-Henrik Haunert, Alexander Wolff

Erschienen in: Geoinformatik

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Zusammenfassung

In diesem Beitrag geht es uns darum, an einigen wenigen Beispielen aus der räumlichen Analyse grundlegende Entwurfstechniken für Algorithmen und Werkzeuge der kombinatorischen Optimierung zu illustrieren. Außerdem wollen wir ein Minimum an theoretischem Unterbau vermitteln. Damit hoffen wir, dass es dem Leser, der Leserin gelingt, räumliche Probleme mit Methoden der Informatik bewusst und damit erfolgreich zu lösen. Wir halten es für besonders wichtig, dass man neue Probleme sorgfältig mathematisch modelliert und mittels exakter Algorithmen das eigene Modell wenigstens auf kleinen Instanzen überprüft, bevor man sich schnellen Heuristiken zuwendet, um große Instanzen zu lösen.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Computer-gestützte Bewegungsanalyse

Nächstes Kapitel Räumliches Data-Mining und Big Geospatial Data

Alt, H., Efrat, A., Rote, G., Wenk, C.: Matching planar maps. J. Algorithms 49(2), 262–283 (2003). https://doi.org/10.1016/S0196-6774(03)00085-3 CrossRef

Breu, H., Kirkpatrick, D.G.: Unit disk graph recognition is NP-hard. Comput. Geom. Theory Appl. 9(1–2), 3–24 (1998). https://doi.org/10.1016/S0925-7721(97)00014-X CrossRef

Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Techn. Ber. 388, Graduate School of Industrial Administration, Carnegie Mellon University (1976)

Clark, B.N., Colbourn C.J., Johnson D.S.: Unit disk graphs. Discret. Math. 86(1–3), 165–177 (1990). https://doi.org/10.1016/0012-365X(90)90358-O CrossRef

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Algorithmen – Eine Einführung, 4. Aufl. Oldenbourg, München (2013)

Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)CrossRef

Das, G.K., De, M., Kolay, S., Nandy, S.C., Sur-Kolay, S.: Approximation algorithms for maximum independent set of a unit disk graph. Inform. Process. Lett. 115(3), 439–446 (2015). https://doi.org/10.1016/j.ipl.2014.11.002 CrossRef

de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3. Aufl. Springer, Berlin (2008). https://doi.org/10.1007/978-3-540-77974-2 CrossRef

Fowler, R.J., Paterson, M.S., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inform. Process. Lett. 12(3), 133–137 (1981). https://doi.org/10.1016/0020-0190(81)90111-3 CrossRef

10.

Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., San Francisco (1990)

11.

Gomory, R.E.: Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958). https://doi.org/10.1007/978-3-540-68279-0_4 CrossRef

12.

Haunert, J.H., Wolff, A.: Optimal simplification of building ground plans. In: Proceedings of 21st Congress International Society Photogrammetry Remote Sensing (ISPRS’08), Technical Commision II/3. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, Bd. XXXVII, Part B2, S. 373–378, Beijing (2008). http://www.isprs.org/proceedings/XXXVII/congress/2_pdf/3_WG-II-3/01.pdf

13.

Haunert, J.H., Wolff, A.: Area aggregation in map generalisation by mixed-integer programming. Int. J. Geogr. Inform. Sci. 24(12), 1871–1897 (2010). https://doi.org/10.1080/13658810903401008 CrossRef

14.

Hsiao, J.Y., Tang, C.Y., Chang, R.S.: An efficient algorithm for finding a maximum weight 2-independent set on interval graphs. Inform. Process. Lett. 43(5), 229–235 (1992). https://doi.org/10.1016/0020-0190(92)90216-I CrossRef

15.

Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–395 (1984). https://doi.org/10.1007/BF02579150 CrossRef

16.

Kirkpatrick, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983). https://doi.org/10.2307/1690046 CrossRef

17.

Krumke, S.O., Noltemeier, H.: Graphentheoretische Konzepte und Algorithmen, 3. Aufl. Vieweg+Teubner (2012). https://doi.org/10.1007/978-3-8348-2264-2

18.

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982). https://doi.org/10.1137/0211025 CrossRef

19.

Michiels, W., Aarts, E., Korst, J.: Theoretical Aspects of Local Search. Springer, Berlin/New York (2007). https://doi.org/10.1007/978-3-540-35854-1

20.

Niemeier, W.: Ausgleichungsrechnung, 2. Aufl. De Gruyter, Berlin (2008)CrossRef

21.

Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola (1998)

22.

Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001). https://doi.org/10.1007/978-3-662-04565-7

23.

Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge/New York (2011)CrossRef

24.

Wolff, A.: Graph drawing and cartography. In: Tamassia, R. (Hrsg.) Handbook of Graph Drawing and Visualization, Kap. 23, S. 697–736. CRC Press, Boca Raton (2013)

Titel: Räumliche Analyse durch kombinatorische Optimierung
verfasst von: Jan-Henrik Haunert
Alexander Wolff
Verlag: Springer Berlin Heidelberg
Buch: Geoinformatik
Print ISBN: 978-3-662-47095-4

Electronic ISBN: 978-3-662-47096-1

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-662-47096-1_69

Springer Professional

Zusammenfassung

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"