Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Daten – Interessen – Ontologien – oder wie Geschäftsmodelle die Wissenschaft verbiegen Kapitel lesen Erstes Kapitel lesen

2020 | OriginalPaper | Buchkapitel

Sind Heuristiken die besseren Algorithmen? Ein Antwortversuch am Beispiel des Traveling Salesman Problem (TSP)

verfasst von : Christian Wadephul

Erschienen in: Datafizierung und Big Data

Verlag: Springer Fachmedien Wiesbaden

Einloggen

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

search-config
loading …

Zusammenfassung

Algorithmen sind so vielfältig wie die Anwendungen, die sie ermöglichen: Vom autonom fahrenden Auto, über Sprachverarbeitung und Textgenerierung bis hin zu DNA-Entschlüsselungen sowie Analysen von Aktienmärkten finden sich tausende von Algorithmen, die digitale Prozesse (Programme) steuern. Wann immer Software auf eine Eingabe (Input) reagiert, ist die Reaktion (Output) durch Algorithmen berechnet worden. ‚Algos‘, wie sie in Fachkreisen fast liebevoll genannt werden, bringen als digital-formalisierbare Handlungsanweisungen Computer zum Laufen. Das methodische Repertoire der Informatik ist in den letzten Jahren erheblich an Umfang und Komplexität gewachsen. Zu den elementaren und exakten algorithmischen Methoden sind heuristische Strategien hinzugekommen, die zwar nicht immer optimale, aber dafür effizientere und bei komplexen Problemen oft erstmalig überhaupt Lösungen liefern. Der Beitrag möchte – v. a. mit Bezug auf das Traveling Salesman Problem (TSP) – zeigen, inwieweit Heuristiken sogar als bessere Algorithmen betrachtet werden müssen.

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 A New Kind of Science: Big Data und Algorithmen verändern die Wissenschaft
Nächstes Kapitel Big Data und die Frage nach der Anerkennung
Fußnoten
1
„Ein Programm ist ein Algorithmus, der in einer Sprache formuliert ist, welche die Abarbeitung durch einen Computer ermöglicht. Im Sinne dieser Definition ist also jedes Programm ein Algorithmus. […] Und das, was in der Welt der Tablet Computer oder Smartphones heute gern als ‚App‘ bezeichnet wird, ist auch nichts anderes als ein Programm. […] Ein Prozessor ist eine Maschine, die in der Lage ist, in einer bestimmten, der Maschine ‚verständlichen‘ Syntax formulierte Algorithmen auszuführen. Moderne Computer sind Universal-Prozessoren.“ (Ziegenbalg et al. 2016, S. 28) Als erstes Computerprogramm gilt der Algorithmus von Ada Lovelace zur Berechnung von Bernoulli-Zahlen, konzipiert im Jahr 1842 für die Analytical Engine von Charles Babbage.
 
2
Vgl. zum Problem biomorpher Metaphorik in technischem Kontext Gutmann/Knifka 2015.
 
3
Vgl. zu Objektivierungen durch das Agens-Actio-Schema Wadephul 2012, S. 35–37.
 
4
Black 2001 deckte etwa detailliert die Geschäftsbeziehungen von IBM mit den Nazis während der 1930er Jahre und im Zweiten Weltkrieg auf. Eine zentrale These ist, dass die Hollerith-Lochkartenechnik Holocaust und Massenmord überhaupt erst möglich machte.
 
5
al-Hwarizmi 1997.
 
6
Vgl. Ziegenbalg et al. 2016, S. 44, 45.
 
7
Vgl. Igarashi et al. 2014, S. 59–61.
 
8
Vgl. Schröder 2014, S. 76; Ziegenbalg et al. 2016, S. 50.
 
9
Vgl. Ziegenbalg et al. 2016, S. 56. Ähnlich funktioniert die Intervallschachtelung, deren Prinzip jedoch auf ‚Ausprobieren‘ beruht und in der Praxis schwer auszuführen ist.
 
10
Das schriftliche Wurzelziehen jedoch (ein Algorithmus ähnlich dem Verfahren der schriftlichen Division) kann mithilfe der binomischen Formel auch exakte Ergebnisse liefern.
 
11
Dafür gibt es Sortieralgorithmen, die dasselbe logarithmische Prinzip ausnutzen.
 
12
„Mathematisch ausgedrückt ist die Anzahl der Verzweigungen vom Stamm bis zu einem Blatt der Logarithmus der Anzahl der Blätter. Genauer der Logarithmus zur Basis zwei – Basis zwei, weil sich jeder Ast in zwei dünnere Äste teilt.“ (Stiller 2015, S. 53).
 
13
Auch hier ist List dreifach konstitutiv: „Auf der Ebene 1) der Programmiersprache, 2) der generischen Programmiertechniken, und schließlich 3) auf derjenigen der spezifischen Listen zur Implementierung numerischer Algorithmen. […] [D]a der für den Computer direkt ausführbare Maschinencode für einen Menschen kaum verständlich ist [,…] zeigt sich also schon eine erste List der Implementierung: Indem die Architektur eines Computers ein gewisses Mittel zum Zwecke seiner Programmierung vorgibt (nämlich den Maschinencode als vom Computer umsetzbare Befehle), schieben wir ein weiteres Mittel, nämlich eine höhere Programmiersprache dazwischen, die es uns erleichtert, den Zweck zu erreichen.“ (Kaminski et al. 2016, S. 110) In den meisten Programmiersprachen liegt die Binäre Suche in den Bibliotheken vor.
 
14
1857 erfand er das Spiel „The Icosian Game“, das er später verbesserte und „Traveller's Dodecahedron or A Voyage Round The World“ nannte. Ziel ist es, eine Reiseroute entlang der Kanten des hölzernen Dodekaeders zu finden, die jede der 20 Städte (Knoten) genau einmal besucht bevor sie zum Ausgangspunkt zurückkehrt. Vgl. hierzu: Cook 2012, S. 30–33, incl. Abbildungen der Spiele.
 
15
Vgl. Cook 2012, S. 33–35.
 
16
Vgl. Cook 2012, S. 49–60.
 
17
Vgl. Cook 2012, S. 22–23.
 
18
Vgl. Cook 2012, S. 171–174.
 
19
Das Hamiltonkreisproblem gehört zu den 21 NP-vollständigen Problemen in der Liste von Karp 1972, womit dessen schwere praktische Lösbarkeit begründet war. Seitdem sind hunderte weitere derartige Probleme aufgezeigt worden. Vgl. Cook 2012, S. 174–177.
 
20
Der Name geht auf Dantzigs Freund Theodore Motzkin zurück, der meinte, dass der Simplex genannte Ansatz in der Geometrie am besten geeignet wäre, um das Verfahren zu beschreiben. Vgl. Cook 2012, S. 105; Hochstättler 2017, S. 138.
 
21
Dantzig 1982; vgl. Cook 2012, S. 99–105.
 
22
Vgl. Rothlauf 2011, S. 52–58.
 
23
Vgl. Hochstättler 2017, S. 95–176; Cook 2012, S. 94–99.
 
24
Cook 2012, S. 127–145.
 
25
Padberg/Rinaldi 1987. Branch-and-Cut ist eine kombinatorische Optimierungsmethode (Schnittebenen- mit Branch-and-Boundverfahren) zur Lösung von ganzzahligen linearen Programmen (integer linear programs, ILP). Vgl. Cook 2012, S. 146–151.
 
27
Helsgaun 2000; vgl. Cook 2012, S. 83, 84.
 
28
Die aufgewendeten 136 Jahre Rechenzeit machen eine Überprüfung der Lösung nahezu unmöglich. Entsprechend haben Applegate et al. 2009 einen Computercode und einen Datensatz veröffentlicht, die zusammen die Optimalität der 85.900-Stadtrundfahrt ‚beweisen’ sollen. Die Daten bestehen aus den Schnittebenen und dualen LP-Lösungen für jedes Teilproblem in der Branch-and-cut-Suche: „Vielleicht nicht so sauber wie der Beweis für den Satz des Pythagoras, aber er enthält genug Informationen, damit zukünftige TSP-Forscher die Ergebnisse der riesigen Berechnung durchforsten können“, meint Cook 2012, S. 162, 163, Übersetzung C. W.
 
29
Vgl. auch die Führung in der VLSI Test Collection, http://​www.​tsp.​gatech.​edu/​vlsi/​index.​html.
 
32
Sogar ein simpler Organismus wie die Amöbe kann, auf einen Computerchip gepresst, ein 8-Städte-TSP lösen! Dies zeigt, was in Zukunft biologische Rechner leisten könnten.
 
33
Vgl. Cook 2012, S. 65 und Fig. 4.3 der Nearest-Neighbor-Heuristik zur Lösung des 42-Städte-USA-Problems auf S. 66.
 
34
Bei der von beiden Methoden am meisten verwendeten Tiefensuche werden sowohl alle Knoten als auch Kanten eines Baumes durchlaufen, wohingegen bei der Breitensuche allein die Knoten des Baumes durchlaufen werden. Vgl. Ziegenbalg 2016, S. 124–137.
 
35
Vgl. Cook 2012, S. 67–70; und Abb. 4.5 mit einer gierigen Tour, S. 67.
 
36
Vgl. Sörensen et al. 2018, S. 797; Stützle/Ruiz 2018.
 
37
Seit 1995 tagt die MIC (Metaheuristics International Conference) und wird das Journal of Heuristics (http://​link.​springer.​com/​journal/​10732/​1/​1/​page/​1) herausgegeben.
 
38
Vgl. Sörensen et al. 2018, S. 804, für eine lange Liste natürlicher Prozesse, die solche metaheuristischen Verfahren inspiriert haben.
 
39
Vgl. Cook 2012, S. 86; vgl. Rimscha 2017, S. 50–56; Domschke/Scholl 2006, S. 8.
 
40
Vgl. Laguna 2018.
 
41
Sörensen et al. 2018, S. 800, machen darauf aufmerksam, dass derselbe Artikel, nämlich Glover 1986, der die Tabu-Suche einführte, auch das Wort ‚Meta-Heuristik‘ prägte.
 
42
Auch Ameisenalgorithmen haben sich als nicht konkurrenzfähig – etwa zu LK/LKH-basierten Methoden – erwiesen. In den letzten Jahren wurde das Paradigma jedoch effektiv auf Probleme in anderen Bereichen angewendet, z. B. bei der Zeitplanung. Vgl. Cook 2012, S. 90; Domschke/Scholl 2006, S. 11; López-Ibáñez et al. 2018.
 
43
Ziegenbalg et al. 2016, S. 310–320, erläutern EA (und ihre Selektions-, Rekombinations- und Mutationsprozesse) am Beispiel des TSP und beschreiben auch eine konkrete Implementierung in der Programmiersprache Mathematica. Vgl. García-Martínez et al. 2018; Gonçalves/Resende 2018; Corne/Lones 2018; zu GA und EA als stochastische Heuristiken vgl. Rimscha 2017, S. 57–65.
 
44
Vgl. zu Künstlichen Neuronalen Netzen (KNN) Ziegenbalg (2016, S. 320–337) und zur Mustererkennung mit rückgekoppelten Netzen (ebd., S. 341–343) sowie für eine Beschreibung eines konkreten (zweiphasigen) Algorithmus (ebd., S. 343–346).
 
45
Vgl. Ziegenbalg 2016, S. 351–355 für eine TSP-Lösung mit einem KNN bzw. „selbstorganisierenden Netz“. Nagata 2006 hat dies in einem der bisher erfolgreichsten Verfahren getan und konnte 2009 so die 100.000 Städte umfassende Mona-Lisa-Tour finden – „leaving a gap of […] only 0.0026 %“ (Cook 2012, S. 164) – sowie Rekordlösungen für die zwei größten Beispiele in der National TSP Collection.“ (Cook 2012, S. 87–90; 93). Vgl. http://​www.​aco-metaheuristic.​org und http://​www.​tsp.​gatech.​edu/​world/​countries.​html.
 
46
„If we are able to formulate a bound, a heuristic ‚becomes‘ an approximation algorithm.“ (Rothlauf 2011, S. 84).
 
47
Christofides 1976; vgl. Cook 2012, S. 72–75.
 
49
Vgl. für Überblick über Workshops seit 2006: http://​astarte.​csr.​unibo.​it/​Matheuristics/​.
 
50
Vgl. Fischetti/Fischetti 2018.
 
52
Selbst-adaptive Metaheuristiken passen ihre Parameter tatsächlich automatisch an (vgl. Cotta et al. 2008). Im Allgemeinen handelt es sich bei diesen Methoden um selbstadaptive Varianten bestehender Metaheuristiken wie TS oder EA (vgl. Kramer 2008).
 
53
Vgl. zu „heuristischen Algorithmen“ Rimscha 2017, S. 42–49.
 
54
Vgl. zu probabilistischen Algorithmen Rimscha 2017, 65–70. Auch Big Data-Analysen sind probabilistische Mustererkennungen von Datenkorrelationen.
 
55
Vgl. Grandori (2015) für nicht-algorithmische Heuristiken bei ökonomischen Problemen.
 
56
Vgl. Lohr 1969.
 
57
Vgl. Magnani 2015.
 
Literatur
al-Hwārizmī, Muhammad Ibn-Mūsā. (1997). Die älteste lateinische Schrift über das indische Rechnen nach al-Hwārizmī. In v. Menso Folkerts, Paul Kunitzsch (Hrsg.). München: Verlag der Bayrischen Akademie der Wissenschaften.
Anders, G. (1956). Die Antiquiertheit des Menschen (Bd. 1). München: Beck.
Applegate, D., et al. (2009). Certification of an optimal TSP tour through 85,900 cities. Operation Research Letters, 37(1), 11–15.CrossRef
Bächle, T. (2015). Mythos Algorithmus. Die Fabrikation des computerisierbaren Menschen. Wiesbaden: Springer VS.
Black, E. (2001). IBM and the Holocaust: The strategic alliance between Nazi Germany and America’s most powerful corporation. New York: Three Rivers Press.
Blischke, W. (2014). Bugs, Big Data und die UnverNETZbaren. Ein Gespräch mit Peter Bittner, Stefan Hügel und Julia Stoll vom FIfF. testcard, 24, 62–72.
Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388. Graduate School of Industrial Administration, Carnegie Mellon University.
Cotta, C., Sevaux, M., & Sörensen, K. (Hrsg.). (2008). Adaptive and Multilevel Metaheuristics. Berlin: Springer.
Commis-Voyageur. (1832). Der Handlungsreisende – Wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein. Ilmenau: Voigt.
Cook, W. J. (2012). In pursuit of the traveling salesman Mathematics at the limits of computation. New Jersey: Princeton University Press.
Corne, D., Lones, M. A. (2018). Evolutionary Algorithms. In Martí et al., S. 409–430.
Dantzig, George B. (1982). Reminiscences about the origins of linear programming. Operations Research Letters, 1, 43–48.CrossRef
Domschke, W., & Scholl, A. (2006). Heuristische Verfahren. Jena: Wirtschaftswissenschaftliche Fakultät, Friedrich-Schiller-Universität Jena.
Euler, L. (1741). Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, 8, 128–40.
Fischetti, M., Fischetti, M. (2018). Matheuristics. In Martí et al., S. 121–154.
Fowler, D., & Robson, E. (1998). Square root approximations in old babylonian mathematics. Historica Mathematica, 25, 366–378.CrossRef
García-Martínez, C., Rodriguez, F. J., Lozano, M. (2018). Genetic Algorithms. In Martí et al., S. 431–464.
Gigerenzer, G. (2007). Bauchentscheidungen. Die Intelligenz des Unbewussten und die Macht der Intuition. München: Bertelsmann.
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computing. Operations Research, 13(5), 533–549.
Goldberg, D. E. (1989). Genetic Algorithms in Search Optimization and Machine Learning. Alabama: Addison Wesley.
Gonçalves, J. F., Resende, M. G. C. (2018). Random-Key Genetic Algorithms. In Martí et al., S. 703–716.
Grandori, A. (2015). Heuristics as Methods. Validity, Reliability and Velocity. In Ippoliti, E. (Hrsg.), Heuristic reasoning. (S. 147–161). Cham: Springer.
Gutmann, M., & Knifka, J. (2015). Biomorphic and technomorphic metaphors – Some arguments why robots don’t evolve, why computing is not organic and why adaptive technologies are not intelligent. In M. Decker, M. Gutmann, & J. Knifka (Hrsg.), Evolutionary Robotics, Organic Computing and Adaptive Ambience. Epistemological and Ethical Implications of Technomorphic Descriptions of Technologies (S. 53–80). Zürich: LIT.
Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126, 103–130.CrossRef
Hofstetter, Y. (2014). Sie wissen alles: Wie intelligente Maschinen in unser Leben eindringen und warum wir für unsere Freiheit kämpfen müssen. München: Bertelsmann.
Igarashi, Y., Altman, T., Funada, M., Kamiyama, B. (2014). Computing. A historical and technical perspective. New York: CRC Press.
Ippoliti, E. (Hrsg.). (2015). Heuristic reasoning. Cham: Springer.
Kaminski A., Schembera B., Resch M., Küster U. (2016). Simulation als List. In G. von Gerhard, G. Petra, H. Christoph, K. Andreas und N. Alfred (Hrsg.), Jahrbuch Technikphilosophie List und Tod (S. 93–122). Zürich: Diaphines.
Karp, R. M. (1972): Reducibility among Combinatorial Problems. In: Miller R.E., Thatcher J.W., Bohlinger J.D. (Hrsg.), Complexity of computer computations. The IBM research symposia series. Boston: Springer.CrossRef
Kirchner, F., & Michaëlis, C. (1907). Wörterbuch der Philosophischen Grundbegriffe. Leipzig: Verlag der Dürr’schen Buchhandlung.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598), 671–680.CrossRef
Kramer, O. (2008). Self-Adaptive Heuristics for Evolutionary Computation. Berlin: Springer.
Laguna, M. (2018). Tabu Search. In Martí et al., S. 741–758.
Lohr, E. (1969). Systematische Heuristik – Ein Beitrag zur Rationalisierung der technisch-wissenschaftlichen Forschung. Deutsche Zeitschrift für Philosophie, 17(3), 355–363.CrossRef
López-Ibáñez, M., Stützle, T., Dorigo, M. (2018). Ant colony optimization: A Component-Wise overview. In Martí et al., S. 371–408.
Lorenz, K. (1995). Algorithmus. In Jürgen Mittelstraß (Hrsg.), Enzyklopädie Philosophie und Wissenschaftstheorie (Bd. 1, S. 85), Stuttgart: Metzler.
MacGregor, J. N., & Ormerod, T. (1996). Human performance on the traveling salesman problem. Perception and Psychophysics, 58, 527–539.CrossRef
Magnani, L. (2015). Are Heuristics Knowledge–Enhancing? Abduction, Models, and Fictions in science. Ippoliti, S. 29–56.
Martí, R., Pardalos, P. M., Resende, M. G. C. (2018). (Hrsg.). Handbook of Heuristics. Cham: Springer.
Metropolis, N., et al. (1953). Equation of state calculations by fast computing machines. Journal of Chemical Physics, 21(6), 1087–1092.CrossRef
Nagata, Y. (2006). Fast EAX algorithm considering population diversity for traveling salesman problems. In European Conference on Evolutionary Computation in Combinatorial Optimization (S. 171–182). Berlin: Springer.CrossRef
Nerurkar, M., Wadephul, C., & Wiegerling, Klaus. (2019). Metaphorik in der Technikethik. Ein Kommentar anlässlich der Big-Data-Stellungnahme des Deutschen Ethikrats. Jahrbuch Technikphilosophie, 5, 271–274.
Newell, A. (1983). The Heuristic of George Polya and its relation to artificial intelligence. In von Groner, R., Groner, M., Bischof, Walter F., (Hrsg.), Methods of Heuristics, (S. 195–244). New Jersey.
O’Neil, C. (2016). Weapons of math destruction. How big data increases inequality and threatens democracy. New York: Crown Books.
O’Neil, C. (2017). Angriff der Algorithmen. Wie sie Wahlen manipulieren, Berufschancen zerstören und unsere Gesundheit gefährden. München: Hanser.
Padberg, M., & Rinaldi, G. (1987). Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters, 6, 1–7.CrossRef
Pietsch, W., & Wernecke, J. (2017). Einführung: Zehn Thesen zu Big Data und Berechenbarkeit. In W. Pietsch, J. Wernecke, & M. Ott (Hrsg.), Berechenbarkeit der Welt? Philosophie und Wissenschaft im Zeitalter von Big Data (S. 13–36). Wiesbaden: Springer VS.
Pólya, G. (1945). How to solve it. Princeton: Princeton University Press.CrossRef
Pólya, G. (1965). Mathematical Discovery Volume II: On understanding, learning, and teaching problem solving. New York: John Wiley and Sons Inc.
Rardin, R. L., & Uzsoy, R. (2001). Experimental evaluation of heuristic optimization algorithms: A tutorial. Journal of Heuristics, 7, 261–304.CrossRef
Kurz, C., & Rieger, F. (2011). Die Datenfresser: Wie Internetfirmen und Staat sich unsere persönlichen Daten einverleiben und wie wir die Kontrolle darüber zurückerlangen. Frankfurt a. M.: Fischer.
Rimscha, M. (2017). Algorithmen kompakt und verständlich. Lösungsstrategien am Computer. Wiesbaden: Springer Vieweg.CrossRef
Robinson, J. (1949). On the Hamiltonian game (a traveling salesman problem). Research Memorandum RM-303. RAND Corporation: Santa Monica.
Rothlauf, F. (2011). Design of Modern Heuristics. Principles and Application. Berlin: Springer.CrossRef
Schröder, M. (2014). Eine Maschine für alle Maschinen. Kleine Genealogie des Computers mit Implikationen für seine Anwendung in Philosophie und Musik. testcard, 24, 74–83.
Schwertgen, D. (2014). Der Autor im Zeitalter seiner technischen Reproduzierbarkeit. testcard, 24, 132–137.
Sebö, A., & Vygen, J. P. (2014). Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34, 597–629.CrossRef
Seidl, T., Enderle, J. (2008). Binäre Suche. In Berthold Vöcking u. a. (Hrsg.), Taschenbuch der Algorithmen (S. 7–13). Berlin: Springer.
Sörensen, K., Sevaux, M., Glover, F. (2018). A History of Metaheuristics. In Martí et al., S. 791–808.
Sörensen, K. (2015). Metaheuristics – The metaphor exposed. International Transactions in Operational Research, 22(1), 3–18.CrossRef
Stiller, S. (2015). Planet der Algorithmen. Ein Reiseführer. München: Knaus.
Stützle, T., Ruiz, R. (2018). Iterated Greedy. In Martí et al., S. 547–578.
Vickers, D., Butavicius, M., Lee, M., & Medvedev, A. (2001). Human performance on visually presented Traveling Salesman problems. Psychological Research, 65, 34–45.CrossRef
Vickers, D., Lee, M. D., Dry, M., & Hughes, P. (2003). The roles of the convex hull and the number of potential intersections in performance on visually presented traveling salesman problems. Memory & Cognition, 31(7), 1094–1104.CrossRef
Vickers, D., Lee, M. D., Dry, M., Hughes, P., & McMahon, J. A. (2006). The aesthetic appeal of minimal structures: Judging the attractiveness of solutions to traveling salesperson problems. Perception and Psychophysics, 68(1), 32–42.CrossRef
Tian, W. (2016). On Polynomial Time Absolute Approximation-bounded Solution of TSP and NP Complete Problems. School of Information and Software Engineering, University of Electronic Science and Technology of China (UESTC). https://​arxiv.​org/​pdf/​1605.​06183.​pdf.
Wadephul, C. (2012). Vom philosophischen zum grammatischen Medienbegriff Und wieder zurück. In Peter F., Andreas L, & Ulrike Ramming (Hrsg.), Die Reflexion des Möglichen Zur Dialektik von Handeln, Erkennen und Werten (S. 31–49). Münster: LIT.
Ziegenbalg, J. Ziegenbalg, O., Ziegenbalg, B. (2016). Algorithmen von Hammurapi bis Gödel Mit Beispielen aus den Computeralgebrasystemen Mathematica und Maxima, (4., überarbeitete und erweiterte Aufl.,), Springer Spektrum: Wiesbaden.CrossRef
Metadaten
Titel
Sind Heuristiken die besseren Algorithmen? Ein Antwortversuch am Beispiel des Traveling Salesman Problem (TSP)
verfasst von
Christian Wadephul
Copyright-Jahr
2020
Buch
Datafizierung und Big Data

Print ISBN: 978-3-658-27148-0

Electronic ISBN: 978-3-658-27149-7

Copyright-Jahr: 2020

DOI
https://doi.org/10.1007/978-3-658-27149-7_3

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Zur Marktübersicht
    Bildnachweise