https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B8%D1%81%D1%82%D0%BE%D1%84%D0%B8%D0%B4%D0%B5%D1%81%D0%B0 2026-05-06T09:08:26Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%B8%D1%81%D1%82%D0%BE%D1%84%D0%B8%D0%B4%D0%B5%D1%81%D0%B0&diff=874&oldid=prev 2008-10-23T16:47:53Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Алгоритм Кристофидеса предназначен для решения [[Задача коммивояжера#метрическая задача коммивояжера|метрической версии задачи о коммивояжере]].<br /> <br /> Пусть на входе мы имеем ''m x n'' матрицу расстояний ''d&lt;sub&gt;ij&lt;/sub&gt;'' для графа ''G''.<br /> Тогда алгоритм будет состоять из следующих шагов:<br /> # Найти [[минимальное остовное дерево]] ''T'' с матрицей весов ''d&lt;sub&gt;ij&lt;/sub&gt;'';<br /> # Выделить множество ''N(T)'' всех вершин нечетной степени в ''T'' и найти кратчайшее совершенное паросочетание ''M'' в полном графе ''G'' с множеством вершин ''N(T)'';<br /> <br /> # Построить [[эйлеров цикл|эйлеров граф]] ''G&lt;sub&gt;E&lt;/sub&gt;'' с множеством вершин &lt;m&gt;\{v_1, \ldots, v_n\}&lt;/m&gt; и множеством ребер &lt;m&gt;T \cup M&lt;/m&gt;;<br /> # Найти [[эйлеров цикл|эйлеров обход]] ''P&lt;sub&gt;E&lt;/sub&gt;'' в ''G&lt;sub&gt;E&lt;/sub&gt;'';<br /> # Построить гамильтонов цикл (соответствующий вложенный тур) ''P&lt;sub&gt;H&lt;/sub&gt;'' из ''P&lt;sub&gt;E&lt;/sub&gt;'', последовательным вычеркиванием посещенных вершин.<br /> <br /> <br /> [[Image:Alg-tsp-christofides.png]]<br /> <br /> [[Category:Алгоритмы]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop