Metraipolis › archive › dc_d2c167aceb18

Algorithmus von Christofides — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Algorithmus_von_Christofides
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-17T03:15:19.059Z
SHA-256 of the archived text
eff4dd9336c5ed37c22fd3b430bdb06d658985597599bb2873fed1d0a71c7989
Stable URL of this page
https://metraipolis.com/documento/dc_d2c167aceb18

How to cite

Algorithmus von Christofides — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Algorithmus_von_Christofides (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d2c167aceb18 (Metraipolis archive dc_d2c167aceb18, sha256 eff4dd9336c5ed37c22fd3b430bdb06d658985597599bb2873fed1d0a71c7989)
BibTeX
@misc{dcd2c167aceb18,
  title = {Algorithmus von Christofides — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Algorithmus_von_Christofides},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d2c167aceb18; sha256 eff4dd9336c5ed37c22fd3b430bdb06d658985597599bb2873fed1d0a71c7989},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/Algorithmus_von_Christofides. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Der Algorithmus von Christofides oder der Algorithmus von Christofides und Serdyukov ist ein Algorithmus, der zur Approximation des metrischen Problem des Handlungsreisenden dient. Er wurde 1976 unabhängig von Nicos Christofides und Anatoliy I. Serdyukov entdeckt und war lange Zeit die beste Approximation des Problems für euklidische Graphen. 1996 stellten Arora und Mitchell für diese jedoch einen besseren Approximationsalgorithmus vor. Formal geht man ähnlich wie bei der Minimum-Spanning-Tree-Heuristik vor: Erzeuge einen minimalen aufspannenden Baum T {\displaystyle T} für den zugrunde liegenden Graphen G = ( V , E ) {\displaystyle G=\left(V,E\right)} mit Kantengewichten. Suche ein (bezüglich Kantengewicht) minimales perfektes Matching M {\displaystyle M} im Graphen zwischen den Knoten, die ungeraden Grad in dem gerade erzeugten Baum T {\displaystyle T} besitzen. Füge diese Kanten zu T {\displaystyle T} hinzu. Dabei können Multikanten auftreten. Der entstehende Graph T ∪ M {\displaystyle T\cup M} ist dann eulersch. Konstruiere eine Eulertour in T ∪ M {\displaystyle T\cup M} . Konstruiere einen Hamiltonkreis in T ∪ M {\displaystyle T\cup M} . Wähle dazu einen beliebigen Startknoten und gehe die Eulertour ab. Ersetze dabei die bereits besuchten Knoten durch direkte Verbindungen (bzw. Abkürzungen) zum nächsten noch nicht besuchten Knoten.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Algorithmus von Christofides» — https://de.wikipedia.org/wiki/Algorithmus_von_Christofides
Wikidata Q498144: «algorithm that approximates solutions to the travellng salesman problem on a metric space, guaranteeing that its solutions will be within 1½ of the optimal solution length; discovered by Nicos Christofides in 1976» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q498144
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Algorithmus_von_Christofides?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 257822894, consultata il 2026-10-17T03:07:39.119Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2550eb9c6bac802d5a986efa3f2a58f9bd1a098b973aecf664b7b9269c7a3f1f