Что такое «задача коммивояжёра»

В 19-м и 20-м веке по горо­дам езди­ли ком­ми­во­я­жё­ры (сей­час их назы­ва­ют «тор­го­вые пред­ста­ви­те­ли»). Они ходи­ли по домам и пред­ла­га­ли людям купить раз­ные това­ры. Так­ти­ка была такой: ком­ми­во­я­жёр при­ез­жал в город, обхо­дил боль­шин­ство домов и отправ­лял­ся в сле­ду­ю­щий город. Горо­да были неболь­ши­ми, поэто­му обой­ти всё было вполне реально. 

Чем боль­ше горо­дов посе­тит ком­ми­во­я­жёр, тем боль­ше домов он смо­жет обой­ти и боль­ше зара­бо­тать с про­даж. Самая боль­шая про­бле­ма, кото­рая все­гда сто­я­ла перед ком­ми­во­я­жё­ра­ми, зву­ча­ла так:

как быст­рее все­го объ­е­хать все горо­да в этом районе?

В 19-м веке все доби­ра­лись из горо­да в город на лоша­дях и повоз­ках, поэто­му вре­мя пол­но­стью зави­се­ло от рас­сто­я­ния меж­ду горо­да­ми. С дру­гой сто­ро­ны, ком­ми­во­я­жё­ру нуж­но было вер­нуть­ся домой после поез­док, поэто­му клас­си­че­ская зада­ча ком­ми­во­я­жё­ра зву­чит так:

как най­ти самый корот­кий марш­рут меж­ду горо­да­ми, что­бы побыть в каж­дом хотя бы по одно­му разу и вер­нуть­ся домой.

Кажет­ся, что зада­ча очень про­стая и совре­мен­ные ком­пью­те­ры могут быст­ро её решить, но это не так. Если горо­дов будет боль­ше 66, то ком­пью­те­ру пона­до­бит­ся несколь­ко мил­ли­ар­дов лет, что­бы най­ти пра­виль­ный ответ. Давай­те выяс­ним, поче­му это так.

Что такое «задача коммивояжёра»

Что такого особенного в этой задаче?

На самом деле это зада­ча не про рас­сто­я­ния, а про поиск опти­маль­но­го реше­ния по выбран­но­му пара­мет­ру в слож­ной систе­ме. Дело в том, что рас­сто­я­ние — это толь­ко одна харак­те­ри­сти­ка марш­ру­та. А могут быть и другие: 

Вре­мя в пути. Вре­мя не обя­за­тель­но напря­мую зави­сит от рас­сто­я­ния. Напри­мер, в Санкт-Петербурге мож­но пой­ти ночью самым корот­ким путём и застрять на раз­вод­ке мостов. По рас­сто­я­нию это будет кило­метр, а по вре­ме­ни — три часа.

Коли­че­ство и часто­та. У нас могут быть лими­ты на посе­ще­ния: не более или не менее опре­де­лён­но­го коли­че­ства горо­дов. В клас­си­че­ской зада­че — нуж­но побыть в каж­дом горо­де не менее одно­го раза. Так­же могут быть огра­ни­че­ния вро­де «не более одно­го раза» или «побы­вать в каж­дом горо­де дважды».

Направ­ле­ние дви­же­ния. Не по всем доро­гам мож­но про­ехать в обе сто­ро­ны — есть направ­ле­ния с одно­сто­рон­ним дви­же­ни­ем. Это зна­чит, напри­мер, что из одной точ­ки до дру­гой не полу­чит­ся дое­хать напря­мую. Зна­чит, при­дёт­ся выби­рать дру­гой маршрут.

Зави­си­мо­сти. Напри­мер, вам нуж­но по пути отвез­ти доку­мен­ты в одно учре­жде­ние, но перед этим забрать их в дру­гом. Если не выпол­нить этот поря­док, поезд­ка теря­ет смысл, пото­му что не выпол­не­но важ­ное условие. 

Всё сра­зу. Может ока­зать­ся так, что нам нуж­но постро­ить такой маршрут:

  • посе­тить все горо­да цен­траль­но­го реги­о­на Рос­сии самым корот­ким путём;
  • в каж­дом горо­де посмот­реть три глав­ных достопримечательности;
  • потра­тив мини­мум денег на доро­гу и проживание;
  • побы­вать в каж­дом горо­де не боль­ше одно­го раза;
  • и успеть всё это за 5 дней. 

Всё и сразу не получится

Возь­мём для при­ме­ра марш­рут по горо­дам Рос­сии. В нём 5 условий:

  1. Все горо­да региона.
  2. Каж­дый город про­ез­жать не более одно­го раза.
  3. Общая дли­на марш­ру­та долж­на быть минимальной.
  4. Общая сум­ма потра­чен­ных денег на доро­гу и про­жи­ва­ние долж­на быть минимальной.
  5. Общая дли­тель­ность поезд­ки не долж­на пре­вы­шать 5 дней.

Ско­рее все­го, ни нам, ни ком­пью­те­ру не полу­чит­ся постро­ить такой марш­рут, что­бы выпол­нить все усло­вия сра­зу. Это ока­жет­ся физи­че­ски невозможно. 

Что­бы тако­го не было, зара­нее выби­ра­ют одно или два кри­тич­ных усло­вия, а осталь­ное как полу­чит­ся. Напри­мер, нам важ­но уло­жить­ся в 5 дней. Вто­рым важ­ным пара­мет­ром, допу­стим, выбе­рем про­сто посе­ще­ние каж­до­го горо­да. Вот что у нас полу­чит­ся в итоге:

  1. ⚠️ Все горо­да реги­о­на.
  2. ⚠️ Общая дли­тель­ность поезд­ки не долж­на пре­вы­шать 5 дней.
  3. Каж­дый город мож­но про­ез­жать сколь­ко угод­но раз.
  4. Общая дли­на марш­ру­та — как получится.
  5. Хоте­лось бы, что­бы общая сум­ма потра­чен­ных денег на доро­гу и про­жи­ва­ние долж­на быть мини­маль­ной, но на вся­кий слу­чай возь­мём с собой денег с запасом.

Теперь нам гораз­до про­ще постро­ить такой марш­рут, пото­му что есть глав­ные кри­те­рии, а осталь­ным мож­но пожертвовать.

Почему это сложно для компьютера

Возь­мём про­стой слу­чай: у нас есть горо­да и таб­ли­ца рас­сто­я­ний меж­ду ними. Зада­ча — най­ти самый корот­кий марш­рут посе­ще­ния всех горо­дов ров­но по одно­му разу, без воз­вра­ще­ния в пер­вый город.

  1. Если у нас в таб­ли­це 4 горо­да, то вари­ан­тов пер­во­го выбо­ра у нас тоже 4.
  2. Когда мы выбра­ли пер­вый город, то у нас есть 3 вари­ан­та, в какой город поехать вторым.
  3. Во вто­ром горо­де у нас вари­ан­тов сле­ду­ю­ще­го горо­да оста­лось 2 — тре­тий либо четвёртый.
  4. В тре­тьем горо­де у нас оста­ёт­ся все­го один вари­ант, куда поехать для завер­ше­ния маршрута.

Так как в горо­да мы можем поехать в любой после­до­ва­тель­но­сти, то все­го у нас полу­ча­ет­ся 4 × 3 × 2 × 1 = 24 вари­ан­та марш­ру­та. Это назы­ва­ет­ся фак­то­ри­ал чис­ла, когда нам нуж­но после­до­ва­тель­но пере­мно­жить все чис­ла от 1 до это­го числа.

Когда у нас 24 вари­ан­та и все­го один пара­метр — мини­маль­ный марш­рут, — ком­пью­тер лег­ко с этим спра­вит­ся про­стым пере­бо­ром. Но если таких горо­дов будет уже 15, у нас появит­ся почти пол­то­ра мил­ли­ар­да ком­би­на­ций марш­ру­тов. Это уже слож­нее, но за час-полтора мощ­ный ком­пью­тер спра­вит­ся и с этим. И это толь­ко с одним параметром!

Если мы к 15 доба­вим ещё два горо­да, то полу­чим уже 355 мил­ли­ар­дов ком­би­на­ций. Такой объ­ём вычис­ле­ний потре­бу­ет гораз­до боль­ше времени.Теоретический пре­дел для ком­пью­те­ра — 66 горо­дов. Если горо­дов 67, то чис­ло воз­мож­ных ком­би­на­ций марш­ру­тов будет рав­но 36×1093 — это боль­ше пре­де­ла Бре­мер­ман­на. Для справ­ки, в Рос­сии 173 города.

Что такое «задача коммивояжёра»

👉 Что за предел Бремерманна

Пред­ставь­те ком­пью­тер раз­ме­ром с нашу Зем­лю на совре­мен­ных тран­зи­стор­ных про­цес­со­рах. В нём мил­ли­ар­ды мил­ли­ар­дов тран­зи­сто­ров, и все они рабо­та­ют на мак­си­маль­но воз­мож­ной часто­те. Такой ком­пью­тер может обра­бо­тать 1075 опе­ра­ций в секун­ду. Если такой ком­пью­тер будет рабо­тать столь­ко, сколь­ко суще­ству­ет Зем­ля, то за всё это вре­мя он смо­жет обра­бо­тать 1093 бит инфор­ма­ции. А при 67 горо­дах наше чис­ло марш­ру­тов полу­ча­ет­ся в 36 раз боль­ше, поэто­му ком­пью­тер нико­гда не смо­жет рас­счи­тать нуж­ный нам маршрут. 

И что тогда делать? 

Если нам нужен самый корот­кий иде­аль­ный марш­рут, то мы смо­жем его най­ти толь­ко для неболь­шо­го чис­ла горо­дов. Но если мож­но отой­ти от иде­а­ла и сде­лать марш­рут чуть длин­нее, то с этим ком­пью­тер уже может справиться. 

Дело в том, что когда мы добав­ля­ем допу­сти­мую погреш­ность в реше­ние, ком­пью­те­ру ста­но­вит­ся намно­го про­ще най­ти ответ. В этом слу­чае зада­ча сво­дит­ся к тому, что­бы подо­брать любой марш­рут, кото­рый укла­ды­ва­ет­ся в рам­ки допу­сти­мой погреш­но­сти. Для это­го исполь­зу­ют спе­ци­аль­ные алго­рит­мы, кото­рые поз­во­ля­ют за при­ем­ле­мое вре­мя най­ти марш­рут с погреш­но­стью 1% от мини­маль­ной длины.

Где применяется

На алго­рит­мах реше­ния зада­чи ком­ми­во­я­жё­ра постро­е­ны все совре­мен­ные нави­га­то­ры в маши­нах и теле­фо­нах. Ведь ров­но это алго­ритм и дела­ет: ищет самый корот­кий марш­рут меж­ду дву­мя точ­ка­ми, а в каче­стве про­ме­жу­точ­ных «горо­дов» у него перекрёстки. 

Но это не един­ствен­ное при­ме­не­ние это­го алго­рит­ма, ещё он используется:

  • для орга­ни­за­ции логи­сти­ки и пере­во­зок в круп­ных ком­па­ни­ях, что­бы стро­ить опти­маль­ные марш­ру­ты по вре­ме­ни, объ­ё­му гру­за и топливу;
  • в систе­мах при­ня­тия реше­ний, когда на вхо­де есть мно­го пара­мет­ров и нуж­но най­ти опти­маль­ную цепоч­ку действий;
  • на про­из­вод­стве при орга­ни­за­ции кон­вей­е­ра, что­бы сокра­тить вре­мя про­стоя и сде­лать сбор­ку дета­лей мак­си­маль­но эффективной;
  • при состав­ле­нии тури­сти­че­ских маршрутов;
  • в эко­но­ми­ке для ана­ли­за эффек­тив­но­сти финан­со­вых инструментов.

Что дальше

В сле­ду­ю­щих ста­тьях нач­нём решать эту зада­чу раз­ны­ми спо­со­ба­ми и смот­реть, какие алго­рит­мы с ней справ­ля­ют­ся луч­ше всего.

Текст:

Миха­ил Полянин

Редак­ту­ра и иллюстрации:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Ана­ста­сия Гаврилова