Обсуждение:Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна - История изменений

https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5%3A%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0%2F%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%2FMTSP_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0 Обсуждение:Приближенный алгоритм для метрической задачи коммивояжера/Задачи/MTSP NP-полна - История изменений 2026-04-30T16:53:04Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/MTSP_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0&diff=516&oldid=prev Masim: /* Решение */ 2011-11-22T05:48:54Z

<p>‎<span dir="auto"><span class="autocomment">Решение</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 05:48, 22 ноября 2011</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >Строка 2:</td> <td colspan="2" class="diff-lineno">Строка 2:</td></tr> <tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.</div></td></tr> <tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>В TSP обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной (длина любого цикла возрастет ровно на <m>Cn</m>, где <m>n</m> - число городов). Под эквивалентостью имеется в виду совпадение маршрутов, а его длину в старой задаче  можно получить, вычитая из результата новой задачи величину <m>Cn</m>. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max_{i,j}{d_{ij}}</m>. В качестве константы <m>C</m> возьмем <m>D + 1</m>. Тогда для новых расстояний выполнено <m>D + 1 < d_{ij}^* \le 2D + 1</m>. При таких расстояниях справедливо неравенство треугольника. Что и требовалось.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>В TSP обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной (длина любого <ins class="diffchange diffchange-inline">гамильтонова </ins>цикла возрастет ровно на <m>Cn</m>, где <m>n</m> - число городов). Под эквивалентостью имеется в виду совпадение маршрутов, а его длину в старой задаче  можно получить, вычитая из результата новой задачи величину <m>Cn</m>. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max_{i,j}{d_{ij}}</m>. В качестве константы <m>C</m> возьмем <m>D + 1</m>. Тогда для новых расстояний выполнено <m>D + 1 < d_{ij}^* \le 2D + 1</m>. При таких расстояниях справедливо неравенство треугольника. Что и требовалось.</div></td></tr>  </table>

Masim https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/MTSP_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0&diff=515&oldid=prev Masim: /* Решение */ 2011-11-21T20:46:18Z

<p>‎<span dir="auto"><span class="autocomment">Решение</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 20:46, 21 ноября 2011</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >Строка 2:</td> <td colspan="2" class="diff-lineno">Строка 2:</td></tr> <tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.</div></td></tr> <tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>В TSP обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. <del class="diffchange diffchange-inline">Оченвидно, что если </del>мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max_{i,j}{d_{ij}}</m>. В качестве константы <m>C</m> возьмем <m>D + 1</m>. Тогда для новых расстояний выполнено <m>D + 1 < d_{ij}^* \le 2D + 1</m>. При таких расстояниях справедливо неравенство треугольника. Что и требовалось.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>В TSP обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. <ins class="diffchange diffchange-inline">Если </ins>мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной <ins class="diffchange diffchange-inline">(длина любого цикла возрастет ровно на <m>Cn</m>, где <m>n</m> - число городов). Под эквивалентостью имеется в виду совпадение маршрутов, а его длину в старой задаче  можно получить, вычитая из результата новой задачи величину <m>Cn</m></ins>. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max_{i,j}{d_{ij}}</m>. В качестве константы <m>C</m> возьмем <m>D + 1</m>. Тогда для новых расстояний выполнено <m>D + 1 < d_{ij}^* \le 2D + 1</m>. При таких расстояниях справедливо неравенство треугольника. Что и требовалось.</div></td></tr>  </table>

Masim https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/MTSP_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0&diff=514&oldid=prev Masim: /* Решение */ 2011-11-21T20:37:53Z

<p>‎<span dir="auto"><span class="autocomment">Решение</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 20:37, 21 ноября 2011</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Решение ==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Решение ==</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Обозначим </del>за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Оченвидно, что если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \<del class="diffchange diffchange-inline">max</del></m></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Сведем задачу TSP к MTSP. То есть, покажем, как решать TSP, если умеем решать MTSP.</ins></div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">В TSP обозначим </ins>за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Оченвидно, что если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \<ins class="diffchange diffchange-inline">max_{i,j}{d_{ij}}</ins></m><ins class="diffchange diffchange-inline">. В качестве константы <m>C</m> возьмем <m>D + 1</m>. Тогда для новых расстояний выполнено <m>D + 1 < d_{ij}^* \le 2D + 1</m>. При таких расстояниях справедливо неравенство треугольника. Что и требовалось.</ins></div></td></tr>  </table>

Masim https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/MTSP_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0&diff=513&oldid=prev Masim: /* Решение */ 2011-11-21T20:29:56Z

<p>‎<span dir="auto"><span class="autocomment">Решение</span></span></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 20:29, 21 ноября 2011</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Решение ==</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>== Решение ==</div></td></tr> <tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Обозначим за <m>d_{ij}</m> расстояние между городами <m>i</m> и <m>j</m>. Оченвидно, что если мы ко всем <m>d_{ij}</m> прибавим константу <m>C</m>, то получим задачу, эквивалентную исходной. Пусть <m>D</m> - максимум расстояний между городами, то есть <m>D = \max</m></ins></div></td></tr>  </table>

Masim https://discopal.ispras.ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5:%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/MTSP_NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0&diff=512&oldid=prev Masim: Created page with "== Решение ==" 2011-11-21T20:29:24Z

<p>Created page with "== Решение =="</p> <p><b>Новая страница</b></p><div>== Решение ==</div>

Masim