Algoritmo de Christofides

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).[1] É 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.[2] 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.

Algoritmo

Seja G = (V,w) uma instância do problema do caixeiro viajante. Isto é, G é um grafo completo com o conjunto de vértices V, e a função w atribui um peso (valor real não-negativo) a cada aresta de G. De acordo com a desigualdade triangular, para três vértices u, v e x quaisquer, é válido dizer que w(uv) + w(vx) ≥ w(ux).

O algoritmo pode ser descrito em pseudocódigo da seguinte forma.

  1. Criar um árvore geradora mínima T de G.
  2. Seja I o conjunto de vértices de grau ímpar em T. Pelo lema do aperto de mão, I tem um número par de vértices.
  3. Encontrar um acoplamento perfeito de peso mínimo M no subgrafo induzido pelos vértices de I.
  4. Combinar as arestas de M e T para formar um multigrafo H em que cada vértice tem grau par.
  5. Formar um circuito Euleriano em H.
  6. Transformar o circuito encontrado na etapa anterior em um circuito Hamiltoniano, ignorando vértices repetidos.

Exemplo

Dado: gráfico completo cujos das arestas obedecem a desigualdade triangular
Calcular a árvore geradora mínima T
Calcular o conjunto de vértices O com grau ímpar em T
Formar a subgrafo de G usando apenas os vértices de O
Construir um acoplamento perfeito de peso mínimo no subgrafo M
Unir o emparelhamento e a árvore geradora  T ∪ M para formar um multigrafo Euleriano.
Calcular o ciclo Euleriano
Remover vértices repetidos, dando a saída do algoritmo

Referências

  1. ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), «18.1.2 The Christofides Approximation Algorithm», Algorithm Design and Applications, Wiley, pp. 513–514 .
  2. ↑ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

Read other articles:

Tina Strobos

Dutch resistance member (1920–2012) Tina StrobosStrobos in 1941BornTineke Buchter(1920-05-19)May 19, 1920Amsterdam, NetherlandsDiedFebruary 27, 2012(2012-02-27) (aged 91)Rye, New York, USAlma materUniversity of AmsterdamOccupationPsychiatristKnown forRescuing over 100 Jewish Holocaust refugees during World War IISpousesRobert Strobos (c. 1947–1964)Walter Chudson (1967–2002)Children3 children and 2 stepchildrenParent(s)Marie Schotte and Alphonse BuchterAwardsElizabet...

 

 

Phonetics

Study of the sounds of human language For the study of phonemes, or how languages organize sounds, see Phonology. For the method of teaching reading and writing, see Phonics. For other uses, see Phonetics (disambiguation). This article's lead section may be too long. Please read the length guidelines and help move details into the article's body. (December 2023) Part of a series onPhonetics Part of the Linguistics Series Subdisciplines Acoustic Articulatory Auditory Articulation Places of art...

 

 

Front militaire

Pour les articles homonymes, voir front. Cet article est une ébauche concernant le domaine militaire. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Front militairePrésentationPartie de GuerreLocalisationLocalisation Ligne de front (en)modifier - modifier le code - modifier Wikidata Un front militaire est une frontière, contestée entre deux forces combattantes. Un front peut être local et tactique ou peut ...

Liste des sénateurs des États-Unis pour l'Idaho

Cet article dresse la liste des membres du Sénat des États-Unis élus de l'État de l'Idaho depuis son admission dans l'Union le 3 juillet 1890. Mike Crapo (R), sénateur depuis 1999. Jim Risch (R), sénateur depuis 2009. Élections Les deux sénateurs sont élus au suffrage universel direct pour un mandat de six ans. Les prochaines élections auront lieu en novembre 2026 pour le siège de la classe II et en novembre 2022 pour le siège de la classe III. Liste des sénateurs Classe II Nom P...

 

 

Gendercide

Systematic killing of members of a specific gender This article appears to be slanted towards recent events. Please try to keep recent events in historical perspective and add more content related to non-recent events. (October 2018) Part of a series onHomicide Murder Note: Varies by jurisdiction Assassination Child murder Consensual homicide Contract killing Crime of passion Depraved-heart murder Felony murder rule Foeticide Honor killing Human cannibalism Child cannibalism Human sacrifice C...

 

 

Hwe (Cyrillic)

Cyrillic letter Cyrillic letter HwePhonetic usage:/ħʷ/The Cyrillic scriptSlavic lettersАА̀А̂А̄ӒБВГҐДЂЃЕЀЕ̄Е̂ЁЄЖЗЗ́ЅИІЇꙆЍИ̂ӢЙЈКЛЉМНЊОО̀О̂ŌӦПРСС́ТЋЌУУ̀У̂ӮЎӰФХЦЧЏШЩꙎЪЪ̀ЫЬѢЭЮЮ̀ЯЯ̀Non-Slavic lettersӐА̊А̃Ӓ̄ӔӘӘ́Ә̃ӚВ̌ԜГ̑Г̇Г̣Г̌Г̂Г̆Г̈ҔҒӺҒ̌ӶД́Д̌Д̈Д̣Д̆ӖЕ̃Ё̄Є̈ԐԐ̈ҖӜӁЖ̣ҘӞЗ̌З̣З̆ӠИ̃ӤҊҚӃҠҞҜК̣ԚᴫЛ́ӅԮԒЛ̈ӍᵸН́ӉҢԨӇҤО̆О̃Ӧ...

Mitsuba Corporation

MITSUBA CorporationCompany typePublic KKTraded asTYO: 7280IndustryAutomotiveFounded(March 8, 1946; 78 years ago (1946-03-08))Headquarters1-2681 Hirosawa-cho, Kiryū, Gunma 376-8555, JapanKey peopleNoboru Hino(Chairman and CEO)Yuichi Nagase(President and COO)ProductsCar electrical componentsMotorcycle componentsNursing care equipmentSolar car & EV productsRevenue US$ 2.64 billion (FY 2013) (¥ 272.54 billion) (FY 2013)Net income US$ 68.28 million (FY 2013) (¥ 7.02 billio...

 

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

 

 

Approach (album)

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Approach album – news · newspapers · books · scholar · JSTOR (February 2024) (Learn how and when to remove this message) 2006 studio album by Von Hertzen BrothersApproachStudio album by Von Hertzen BrothersReleased17 May 2006 (Finland)RecordedMD St...

Raphael Saadiq

American contemporary R&B singer This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if potentially libelous.Find sources: Raphael Saadiq – news · newspapers · books · scholar · JSTOR (March 2020) (Learn how and when to remove this ...

 

 

Doctor of Philosophy

Postgraduate academic degree awarded by most universities worldwide PhD redirects here. For other uses, see PHD (disambiguation). Doctor of PhilosophyTypePostgraduate educationDuration3 to 8 yearsPrerequisites / eligibility criteriaBachelor's degreeMaster's degree(varied by country and institution) A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: philosophiae doctor or doctor philosophiae) is a terminal degree that usually denotes the highest level of academic achievement in a given disci...

 

 

Norman Lear

American screenwriter and producer (1922–2023) Norman LearLear in 2015BornNorman Milton Lear(1922-07-27)July 27, 1922New Haven, Connecticut, U.S.DiedDecember 5, 2023(2023-12-05) (aged 101)Los Angeles, California, U.S.EducationEmerson CollegeOccupationsScreenwriterproducerYears active1946–2023Known forSitcoms: All in the FamilyThe JeffersonsSanford and SonGood TimesMaudeMary Hartman, Mary HartmanOne Day at a TimeSpouses Charlotte Rosen ​ ​(m. 1943...

Mary Eva Kelly

Irish writer This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Mary Eva Kelly – news · newspapers · books · scholar · JSTOR (February 2013) (Learn how and when to remove this message) Mary Eva KellyBorn1826Died1910 (aged 83–84)Resting placeToowong CemeteryOccupationPoetNationalityIrishGenrePoetry Ma...

 

 

مالي في الألعاب الأولمبية

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) مالي في الألعاب الأولمبية علم مالي رمز ل.أ.د.  MLI ل.أ.و. اللجنة الأولمبية والرياضية الوطنية لمال�...

 

 

留守政府

この記事には参考文献や外部リンクの一覧が含まれていますが、脚注によって参照されておらず、情報源が不明瞭です。脚注を導入して、記事の信頼性向上にご協力ください。（2017年6月） 留守政府（るすせいふ）とは、明治初期において、明治政府首脳部で組織された岩倉使節団が欧米歴訪中にその留守を守るために組織された国内の体制を指す。明治4年11月12日（18...

Gu Jun

Dalam artikel ini, nama keluarganya adalah Gu. Gu JunInformasi pribadiKebangsaanTiongkokLahir3 Januari 1975 (umur 49)Wuxi, Jiangsu, TiongkokTinggi165 m (541 ft 4 in)Berat62 kg (137 pon)PeganganKananGanda putriPeringkat tertinggi1 bersama Ge Fei Rekam medali Bulutangkis Mewakili  Tiongkok Olimpiade Musim Panas Atlanta 1996 Ganda putri Sydney 2000 Ganda putri Kejuaraan Dunia Glasgow 1997 Ganda putri Kopenhagen 1999 Ganda putri Piala Dunia Jakarta 1996 Ganda pu...

 

 

Temple Shalom of Northwest Arkansas

Synagogue in Fayetteville, Arkansas, United States For similarly named synagogues, see Temple Shalom. Temple Shalom of Northwest ArkansasReligionAffiliationJudaismRite(Unaffiliated)Ecclesiastical or organisational statusSynagogueLeadershipRabbi Jacob Adler (Emeritus)StatusActiveLocationLocation699 North Sang Avenue, Fayetteville, ArkansasCountryUnited StatesLocation in ArkansasGeographic coordinates36°04′26″N 94°11′22″W / 36.073973°N 94.189321°W / 36.073973...

 

 

Battle of Mukden

Decisive battle in the Russo-Japanese war For the 1931 incident that led to the Japanese invasion of Manchuria, see Mukden Incident. Battle of MukdenPart of the Russo-Japanese WarRussian field gun firing during the battle of MukdenDate20 February – 10 March 1905(2 weeks and 4 days)LocationSouth of Mukden (modern Shenyang), ManchuriaResult Japanese victory[1]Territorialchanges Japanese occupy all of southern ManchuriaRussian forces retreat to northern ManchuriaBelligerents ...

Anastasia Golovashkina

American political consultant Anastasia GolovashkinaBorn(1993-12-24)24 December 1993RussiaDied18 July 2022(2022-07-18) (aged 28)Chicago, Illinois, U.S.EducationUniversity of ChicagoPolitical partyDemocratic Anastasia Golovashkina (December 24, 1993 – July 18, 2022) was a Russian-American political consultant who served as the social media director for Elizabeth Warren's 2020 presidential campaign.[1] During the 2020 Democratic Party presidential primaries, Golovashkina was diag...

 

 

ديكتاتورية البروليتاريا

إن ديكتاتورية البروليتاريا هي السيطرة السياسية والاقتصادية للطبقة العاملة على وسائل الإنتاج وأجهزة الدولة من خلال مجالسها العمالية ومندوبيها المنتخبين.[1][2][3] وتلك السيطرة العمالية لا يمكن أن تتحقق إلا بإرادة الطبقة العاملة أي لا يمكن أن تتحقق إلا بثورة العم...