0 added
0 removed
Original
2026-01-01
Modified
2026-03-10
1
<p>Теги: алгоритмы, задачи на графах, маршруты коммивояжёра, задача коммивояжёра, computer science</p>
1
<p>Теги: алгоритмы, задачи на графах, маршруты коммивояжёра, задача коммивояжёра, computer science</p>
2
<p>Есть N городов, связанных дорогами. Как помочь коммивояжёру проложить наиболее короткий/выгодный/дешёвый маршрут между этими городами, чтобы посетить каждый город хотя бы по одному разу и вернуться в исходную точку? Многие, изучающие<strong>computer science</strong>, знают о существовании этой задачи как одной из самых известных задач на графах. Все знают, что эта задача<strong>NP-полная</strong>и<strong>нерешаема</strong>в общем виде на современных компьютерах.</p>
2
<p>Есть N городов, связанных дорогами. Как помочь коммивояжёру проложить наиболее короткий/выгодный/дешёвый маршрут между этими городами, чтобы посетить каждый город хотя бы по одному разу и вернуться в исходную точку? Многие, изучающие<strong>computer science</strong>, знают о существовании этой задачи как одной из самых известных задач на графах. Все знают, что эта задача<strong>NP-полная</strong>и<strong>нерешаема</strong>в общем виде на современных компьютерах.</p>
3
<h2>Подробности</h2>
3
<h2>Подробности</h2>
4
<p>Прикинем, сколько же возможных маршрутов коммивояжёра существует. Если мы находимся в каком-то городе, одном из N-городов, то пойти мы можем в N - 1 город. На следующем шаге мы можем пойти в N - 2 города и т. д. Итого существует (N - 1)! различных маршрутов.</p>
4
<p>Прикинем, сколько же возможных маршрутов коммивояжёра существует. Если мы находимся в каком-то городе, одном из N-городов, то пойти мы можем в N - 1 город. На следующем шаге мы можем пойти в N - 2 города и т. д. Итого существует (N - 1)! различных маршрутов.</p>
5
<h2>Как давно эту задачу не могут решить?</h2>
5
<h2>Как давно эту задачу не могут решить?</h2>
6
<p>Интересна историческая подоплёка появления этой задачи. Как гласит википедия: “...известна изданная в 1832 году книга с названием "Коммивояжёр - как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах - советы старого курьера" (нем. Der Handlungsreisende - wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein - von einem alten Commis-Voyageur), в которой описана проблема, но математический аппарат для её решения не применяется.”</p>
6
<p>Интересна историческая подоплёка появления этой задачи. Как гласит википедия: “...известна изданная в 1832 году книга с названием "Коммивояжёр - как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах - советы старого курьера" (нем. Der Handlungsreisende - wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein - von einem alten Commis-Voyageur), в которой описана проблема, но математический аппарат для её решения не применяется.”</p>
7
<h2>И что сегодня?</h2>
7
<h2>И что сегодня?</h2>
8
<p>Впоследствии<strong>задачу коммивояжёра</strong>исследовали многие учёные в разных вариантах постановки и с разными ограничениями, применяя математический аппарат по максимуму. Какие только способы не применялись для её решения: от<strong>динамического программирования</strong>до<strong>нейросетей</strong>!</p>
8
<p>Впоследствии<strong>задачу коммивояжёра</strong>исследовали многие учёные в разных вариантах постановки и с разными ограничениями, применяя математический аппарат по максимуму. Какие только способы не применялись для её решения: от<strong>динамического программирования</strong>до<strong>нейросетей</strong>!</p>
9
<p>Исследование этой задачи до сих пор продолжается, и она привлекает учёных, несмотря на несложную и понятную всем формулировку.</p>
9
<p>Исследование этой задачи до сих пор продолжается, и она привлекает учёных, несмотря на несложную и понятную всем формулировку.</p>
10
<p><em>А какие вы можете предложить решения? Пишите в комментариях!</em></p>
10
<p><em>А какие вы можете предложить решения? Пишите в комментариях!</em></p>
11
11