| dbo:abstract
|
- En teoria de grafs, l'algorisme de Christofides és un algorisme que serveix per resoldre el problema del viatjant de comerç, en el cas en què les distàncies formen un espai mètric (són simètriques i compleixen la desigualtat triangular). Es tracta d'un algorisme d'aproximació que garanteix que les seves solucions es trobaran en un factor màxim de 3/2 respecte a la distància total de la solució òptima. i rep el nom de Nicos Christofides, que el va publicar el 1976. A data de 2015, és el millor ratio d'aproximació que s'ha demostrat pel problema del viatjant de comerç en espais mètrics generals, tot i que es coneixen millors aproximacions per a alguns casos particulars. (ca)
- Ο αλγόριθμος Χριστοφίδη είναι ένας αλγόριθμος για την εύρεση λύσεων κατά προσέγγιση στο πρόβλημα πλανόδιου πωλητή, στις περιπτώσεις όπου οι αποστάσεις σχηματίζουν ένα μετρικό χώρο (είναι συμμετρικές και ακολουθούν την τριγωνική ανισότητα).Είναι ένας αλγόριθμος προσέγγισης που εγγυάται ότι οι λύσεις θα είναι εντός συντελεστή 3/2 του μήκου βέλτιστης λύσης, και είναι ονομάστηκε από τον Νίκο Χριστοφίδη, που τον δημοσίευσε το 1976. Από το 2017, αυτός είναι ο καλύτερος ρυθμός προσέγγισης που έχει αποδειχθεί για το πρόβλημα του περιπλανώμενου πωλητή, σε γενικούς μετρικούς χώρους, αν και καλύτερες προσεγγίσεις είναι γνωστές για κάποιες ειδικές περιπτώσεις. (el)
- 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: 1.
* Erzeuge einen minimalen aufspannenden Baum für den zugrunde liegenden Graphen mit Kantengewichten. 2.
* Suche ein (bezüglich Kantengewicht) minimales perfektes Matching im Graphen zwischen den Knoten, die ungeraden Grad in dem gerade erzeugten Baum besitzen. 3.
* Füge diese Kanten zu hinzu. Dabei können Multikanten auftreten. Der entstehende Graph ist dann eulersch. 4.
* Konstruiere eine Eulertour in . 5.
* Konstruiere einen Hamiltonkreis in . 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. (de)
- The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and , who discovered it independently in 1976. This algorithm still stands as the best polynomial time approximation algorithm that has been thoroughly peer-reviewed by the relevant scientific community for the traveling salesman problem on general metric spaces. In July 2020 however, Karlin, Klein, and Gharan released a preprint in which they introduced a novel approximation algorithm and claimed that its approximation ratio is 1.5 − 10−36. Their method follows similar principles to Christofides' algorithm, but uses a randomly chosen tree from a carefully chosen random distribution in place of the minimum spanning tree. The paper was published at STOC'21 where it received a best paper award. (en)
- El algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por su acrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular. Fue desarrollado en 1976 por Nicos Christofides, profesor del Imperial College London. Supongamos que representa una instancia del TSP, en donde es un grafo completo definido por: un conjunto de vértices o nodos y una función que asocia un peso o valor real positivo a cada arista del grafo . (es)
- L'algorithme de Christofides est un algorithme d'approximation pour le problème du voyageur de commerce, dans le cas métrique, et que l'inégalité triangulaire est respectée. L'analyse de cet algorithme est due à and , qui l'ont découvert indépendamment en 1976. (fr)
- 크리스토피데스 알고리즘(Christofides algorithm)은 거리 공간 외판원 문제에서 근사해를 구하는 알고리즘이다. 위 근사 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장하며, Nicos Christofides에 의해 1976년 개발되었다. 2017년까지도 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다. (ko)
- Algorytm Christofidesa – algorytm aproksymacyjny znajdujący rozwiązanie problemu komiwojażera w grafach w których wagi krawędzi są nieujemne i spełniają warunek nierówności trójkąta. Algorytm jest 1,5-optymalny, to znaczy, że znalezione rozwiązanie będzie nie gorsze niż 1,5 rozwiązania optymalnego. (pl)
- クリストフィードのアルゴリズム（英: Christofides algorithm）は三角不等式を満たす距離を持つグラフにおいて、巡回セールスマン問題の近似解を見つける近似アルゴリズムである。この近似アルゴリズムの出力は、最適解の重みの3/2以下になることが保証されている。1976年に発案者され、発案者であるNicos Christofidesにちなんで命名された。2015年現在、距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が存在する事も知られている）。 (ja)
- O algoritmo de Christofides é um algoritmo para encontrar soluções aproximadas para o problema do caixeiro-viajante, nos casos em que as distâncias formam um espaço métrico (são simétricas e obedecem a desigualdade triangular).É um algoritmo de aproximação que garante que suas soluções estão a um fator máximo de 3/2 do tamanho da solução ótima. Seu nome vem do autor Nicos Christofides, que publicou o algoritmo em 1976. Até 2017 esta é a melhor razão de proximação já comprovada para o problema do caixeiro viajante em espaços métricos, embora aproximações melhores sejam conhecidas para alguns casos especiais. (pt)
- Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближённых решений задачи коммивояжёра для случаев, когда расстояния образуют метрическое пространство (симметричны и удовлетворяют неравенству треугольника).Алгоритм является аппроксимационным алгоритмом, который гарантирует, что решения находятся в пределах 3/2 от длины оптимального решения. Алгоритм назван именем Никоса Кристофидеса и Анатолия Ивановича Сердюкова, которые независимо друг от друга нашли его в 1976, и он обладает лучшим аппроксимационным коэффициентом, который был доказан для задачи коммивояжёра на метрических пространствах общего вида, хотя известны лучшие приближения для некоторых специальных случаев. (ru)
- 克里斯托菲德斯算法 (Christofides algorithm) 是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯 (Nicos Christofides) 于1976年首次发表了这个算法，故以他的名字命名之。 截至2017年，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9734 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En teoria de grafs, l'algorisme de Christofides és un algorisme que serveix per resoldre el problema del viatjant de comerç, en el cas en què les distàncies formen un espai mètric (són simètriques i compleixen la desigualtat triangular). Es tracta d'un algorisme d'aproximació que garanteix que les seves solucions es trobaran en un factor màxim de 3/2 respecte a la distància total de la solució òptima. i rep el nom de Nicos Christofides, que el va publicar el 1976. A data de 2015, és el millor ratio d'aproximació que s'ha demostrat pel problema del viatjant de comerç en espais mètrics generals, tot i que es coneixen millors aproximacions per a alguns casos particulars. (ca)
- Ο αλγόριθμος Χριστοφίδη είναι ένας αλγόριθμος για την εύρεση λύσεων κατά προσέγγιση στο πρόβλημα πλανόδιου πωλητή, στις περιπτώσεις όπου οι αποστάσεις σχηματίζουν ένα μετρικό χώρο (είναι συμμετρικές και ακολουθούν την τριγωνική ανισότητα).Είναι ένας αλγόριθμος προσέγγισης που εγγυάται ότι οι λύσεις θα είναι εντός συντελεστή 3/2 του μήκου βέλτιστης λύσης, και είναι ονομάστηκε από τον Νίκο Χριστοφίδη, που τον δημοσίευσε το 1976. Από το 2017, αυτός είναι ο καλύτερος ρυθμός προσέγγισης που έχει αποδειχθεί για το πρόβλημα του περιπλανώμενου πωλητή, σε γενικούς μετρικούς χώρους, αν και καλύτερες προσεγγίσεις είναι γνωστές για κάποιες ειδικές περιπτώσεις. (el)
- El algoritmo de Christofides es un algoritmo aproximado que permite resolver instancias del problema del viajante de comercio (designado convencionalmente por su acrónimo en inglés, TSP) en donde los pesos de las aristas del grafo satisfacen la desigualdad triangular. Fue desarrollado en 1976 por Nicos Christofides, profesor del Imperial College London. Supongamos que representa una instancia del TSP, en donde es un grafo completo definido por: un conjunto de vértices o nodos y una función que asocia un peso o valor real positivo a cada arista del grafo . (es)
- L'algorithme de Christofides est un algorithme d'approximation pour le problème du voyageur de commerce, dans le cas métrique, et que l'inégalité triangulaire est respectée. L'analyse de cet algorithme est due à and , qui l'ont découvert indépendamment en 1976. (fr)
- 크리스토피데스 알고리즘(Christofides algorithm)은 거리 공간 외판원 문제에서 근사해를 구하는 알고리즘이다. 위 근사 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장하며, Nicos Christofides에 의해 1976년 개발되었다. 2017년까지도 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다. (ko)
- Algorytm Christofidesa – algorytm aproksymacyjny znajdujący rozwiązanie problemu komiwojażera w grafach w których wagi krawędzi są nieujemne i spełniają warunek nierówności trójkąta. Algorytm jest 1,5-optymalny, to znaczy, że znalezione rozwiązanie będzie nie gorsze niż 1,5 rozwiązania optymalnego. (pl)
- クリストフィードのアルゴリズム（英: Christofides algorithm）は三角不等式を満たす距離を持つグラフにおいて、巡回セールスマン問題の近似解を見つける近似アルゴリズムである。この近似アルゴリズムの出力は、最適解の重みの3/2以下になることが保証されている。1976年に発案者され、発案者であるNicos Christofidesにちなんで命名された。2015年現在、距離空間における巡回セールスマン問題に対する多項式時間アルゴリズムの中では、近似度が最良であるアルゴリズムである（一部の特殊な場合では、より良い近似度が存在する事も知られている）。 (ja)
- O algoritmo de Christofides é um algoritmo para encontrar soluções aproximadas para o problema do caixeiro-viajante, nos casos em que as distâncias formam um espaço métrico (são simétricas e obedecem a desigualdade triangular).É um algoritmo de aproximação que garante que suas soluções estão a um fator máximo de 3/2 do tamanho da solução ótima. Seu nome vem do autor Nicos Christofides, que publicou o algoritmo em 1976. Até 2017 esta é a melhor razão de proximação já comprovada para o problema do caixeiro viajante em espaços métricos, embora aproximações melhores sejam conhecidas para alguns casos especiais. (pt)
- Алгоритм Кристофидеса или алгоритм Кристофидеса-Сердюкова — это алгоритм поиска приближённых решений задачи коммивояжёра для случаев, когда расстояния образуют метрическое пространство (симметричны и удовлетворяют неравенству треугольника).Алгоритм является аппроксимационным алгоритмом, который гарантирует, что решения находятся в пределах 3/2 от длины оптимального решения. Алгоритм назван именем Никоса Кристофидеса и Анатолия Ивановича Сердюкова, которые независимо друг от друга нашли его в 1976, и он обладает лучшим аппроксимационным коэффициентом, который был доказан для задачи коммивояжёра на метрических пространствах общего вида, хотя известны лучшие приближения для некоторых специальных случаев. (ru)
- 克里斯托菲德斯算法 (Christofides algorithm) 是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。 该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。尼科斯·克里斯托菲德斯 (Nicos Christofides) 于1976年首次发表了这个算法，故以他的名字命名之。 截至2017年，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。 (zh)
- The Christofides algorithm or Christofides–Serdyukov algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality).It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length, and is named after Nicos Christofides and , who discovered it independently in 1976. (en)
- 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: (de)
|
| rdfs:label
|
- Algorisme de Christofides (ca)
- Algorithmus von Christofides (de)
- Αλγόριθμος Χριστοφίδη (el)
- Algoritmo de Christofides (es)
- Christofides algorithm (en)
- Algorithme de Christofides (fr)
- 크리스토피데스 알고리즘 (ko)
- クリストフィードのアルゴリズム (ja)
- Algorytm Christofidesa (pl)
- Algoritmo de Christofides (pt)
- Алгоритм Кристофидеса (ru)
- 克里斯托菲德斯算法 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
