Задача коммивояжёра

11

Е. Габович

Задача
коммивояжера

«Пользуйтесь услугами Аэрофлота!»
Два автомобильства, инженер А. Невский и экономист Б. Литейный, решили съездить в Закавказье, посетить Баку и Тбилиси, заехать в Москву, Киев и Горький, а затем вернуть в родной Ленинград. Начали обсуждать маршрут путешествия. Невский посмотрел на карту и предложил такую последовательность посещения городов:
Л → М → Г → Б → Т → К → Л
Литейный же, достав атлас автомобильных дорог, выписал расстояния между нужными им городами в таблицу (см. таблицу 1) и подсчитал длину предложенного маршрута:
696 + 410 + 2937 + 579 + 1863 + 1207 = 7692 км. «Длиноваато! — сказал он. — Расстояние аэрофлотское! А нельзя ли короче? Уверен ли ты, что этот маршрут является кратчайшим?»
Уверенности такой у Невского не было. Более того, обьясить, почему он решил ехать именно так, Невский не мог. Проство интуиция подсказывал ему, что такой маршрут, если и т.д.

Таблица 1

| Город | Л | М | К | Б | Т | Г |
| :— | :— | :— | :— | :— | :— | :— |
| Ленинград | — | 696 | 1207 | 3223 | 2797 | 1106 |
| Москва | 696 | — | 858 | 2527 | 2101 | 410 |
| Киев | 1207 | 858 | — | 2283 | 1863 | 1268 |
| Баку | 3223 | 2527 | 2283 | — | 579 | 2937 |
| Тбилиси | 2797 | 2101 | 1863 | 579 | — | 2511 |
| Горький | 1106 | 410 | 1286 | 2937 | 2511 | — |

12

не короче всех других, то близок к кратчайшейему.

«А не просмотреть ли нам все вообще маршруты? — предложил Литейный. — Много ли их?» Сталил подсчитывать. «Из Ленинграда можно поехать в любой из пятин городов. Если мы поедем, скажем, в Москве, то из нее можно направиться в любой из отличных от Ленинграда и Москвы городов. Итак, имеется 20 поездок вида $Л \rightarrow X \rightarrow Y$, где $Л \neq X \neq Y \neq Л$. Поездок вида $Л \rightarrow X \rightarrow Y \rightarrow Z$ уже 60, но из $Y$ можно поехать в любой из оставшихся трех городов. Если мы выберем $Z$, то можем считать следующим за $Z$ городом любой из последующих двух городов. Итак, 120 маршрутов, либо завершается путешествие однозначно: по пути домой поещается последний из шести городов. Многоваго! Так что это не метод, — перебирать все маршруты! Ведь если мы хотели посетить шесть городов, у нас было бы 720, а если семь, то уже 5040 маршрутов!»

«Тогда давай поступим так — предложил Невский, — поедем из Ленинграда в ближайший город, из него — в ближайший, еще не посещенный, и т. д. Это дает нам маршрут $Л \rightarrow M \rightarrow Γ \rightarrow K \rightarrow T \rightarrow Б \rightarrow Л$. Его длина, — сейчас подсчитано, — 8057 км. На 365 км длинее!»

Задача коммивояжера

Задача, которую решают Невский и Литейный, известна в математике под названием задачи коммивояжера *) (бродячего торговца).

Сформируем ее в общем виде: имеется $k$ городов, расстояния между которых известны; коммивояжеру нужно выйти из одного из этих городов, посетить остальные $k-1$ городов, побив в каждой из нихровно по одному разу, и вернуть в

*) Вероятно, впервые сформируем задачу коммивояжера известный математик Карл Менгер. Произошло это 5 февраля 1930 года на математическом колоквинуме в Вене. Менгер пользовался известным «Задача о посыльном».

Рис. 1.

исходный город; как найти кратчайший маршрут?

Очевидно, выбор начального пункта маршрута несуществен — задачу коммивояжера можно сформулировать и так: найти кратчайший замкнутый маршрут, прохождение по разу через каждый из $k$ городов.

Уражнение 1. Докажите, что общее число маршрутов коммивояжера равно $(k-1)! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot (k-1)$.

Заметим, что таблица расстояний, составленная Б. Литейным (математики называют такие таблицы матриц), оказывается симметричной относительно диагонали, на которой стоит проечерки. В задаче коммивояжера допускается и несимметричные таблицы. Несимметриная таблица расстояний может возникнуть, например, в следующей задаче (o колчевом автовосном маршруте). В городе, на некоторых улицах города разрешено только одностороннее движение, фиксированы $k$ точек (мест будуших остановок). Через них должны проечерки замкнутая автобусная линия. Требуется найти также циклическую последовательность прохождения точки остановок, при которой каждой последовательности один и только один раз, а весь маршрут имеет минимальную протяженность.

Уражнение 2. В пластинке размером $7 \times 9$ лучлазера должен проесть щелей в направлениях, указанных на рисунке 1 стрелками, и вернуть в исходное положение. Задача минимализии холодного проега лазерной головки есть задача коммивояжера. Выпишите матрицу расстояний для нее. (Обратите внимание на то, что она получается несимметричной.)

13

Из упражнения 2 мы видим, что «городами» в задаче коммувожера могут быть вовсе не города, а «растойнями» — вовсе не растойня. Например, под «растойнем» между двумя городами можно попытаться или продолжитьность путешествия между ними. В этом случае минимизируется, соответственно, суммарная стоимость путешествия или его продолжительность.

Рассмотрим еще для примера задачу о стане. Деталь в процессе обработки на стане подвергается $k$ операции. При переходе от одной операции к другой станок должен зановно настроиваться, что приводит к потери времени. Требуется найти такой порядок проведения всех операций (с возвращением станка в исходное состояние), при котором суммарные потери были бы наименьшими. Ясно, что здесь мы имеем дело с задачей коммувожера — с таблицей потерь времени на перестройку станка в качестве матрицы растойния. «Городами» являются состояние станка после различных операций.

К задаче коммувожера приводят задачи планирования производства и проектирования линейной связи (скажем, телефонной сети), задачи составления маршрута дляпочтального (врача, контролера телефонов-автоматов и т.п.) и даже некоторых задачи проектирования ЭВМ.

Полный перебор

Итак, в каждой конкретной задаче коммувожера требуется найти кратчайший тур при заданной матрице растойния. Можно случайно, что

| Номер операции | I | II | III | IV | V |
| :— | :— | :— | :— | :— | :— |
| I | — | 0 | 11 | 5 | 20 |
| II | 31 | — | 0 | 52 | 8 |
| III | 9 | 16 | — | 0 | 41 |
| IV | 64 | 31 | 61 | — | 0 |
| V | 0 | 93 | 19 | 7 | — |

сделать это окажется крайне просто. Например, если потери на переналку в задаче о стане заданы таблицей 2, то оченьно, что оптимальный является такая последовательность операций: $I \rightarrow II \rightarrow III \rightarrow IV \rightarrow V \rightarrow I$ (с нульым суммарным времени переналки).

Уражнение 3. Решите задачу коммувожера из упражнения 2, если известно, что во время хлопотного хода лазерная головка может передвигаться только параллельно краям пластинки.

Однако чашце всего для конкретных таблиц растойний бросаются в глаза решений нет. И если даже кто-нибудь подсказет нам, какой маршрут является кратчайшим, возможно больше трудности, когда мы захотим проверить, так ли это на самом деле.

Matematиков же интересют не столько решения конкретных задач коммувожера, сколько общие решения всех таких задач (или хотя бы всех задач коммувожера при $k \leq m$, где $m$ — некоторое фиксированное число).

Заметим, что в каждой конкретной задаче коммувожера можновести все маршрутов конечно. Поэтому можно организовать полный перебор всех маршрутов, вычислить их длины и выбрать кратчайший маршрут. Такой полный перебор в принципе является общим методом решения задачи коммувожера.

Однако вспомним Невского и Литейного. Хотя им предстояло провести замкнутый маршрут всего лишь через шесть городов, они не захотели перебирать все 120 туриов (правда, автоматически не заметили того, что из-за симметриности таблицы 1 только 60 туриов имеют различную длину). В общем же случае коммувожеру приходится выбирать кратчайший из $(k-1)$! возможность маршрутов. Это число с ростом $k$ растет очень быстро, а потому указывающий способ решения при больших значениях $k$ практически не применим. Так, автору известен пример, когда для осуществления перебора в задаче коммувожера с десятью городами $(k=10)$ на ЭВМ М-220А было израсходовано 4 часа 45 минут! Быст-

15

Эксперименты показали, что без использования специфических свойств каждой конкретной задачи коммуникатора существует ЭВМ и методы решения задач целочисленного линейного программирования позволяют справляться с задачи коммуникатора лишь при необходимости числе городов (не превысаяшем десяти). В то же время самые последние работы в этой области показывают, что сведение к задаче целочисленного линейного программирования может быть эффективно использовано в сочетании с другими методом решения задачи коммуникара — методом ветвей и границ.

Метод ветвей и границ

Нанлучшим методом решения задачи коммуникара в настоящее время является метод ограничного перебора, или метод ветвей и границ. Он применяется в нескольких модификации, имеющих различную эффективность.

Осуществляя полный перебор, мы можем, конечно, выписать все туры друг за другом. Можно поступить иначе: нарисовать дерево возможных поездок. Для случая четырех городов оно изображено на рисунке 2. В кругжках — номера городов; стрелками изображены поездки. Ясно, что при переходе к дереву поездок количество стрелок уменьшается по сравнению с их количеством в записи всех маршрутов (при $k > 3$). На пример, при выписывании всех маршрутов подряд стрелку I → II пришлось бы нарисовать дважды. Но еще большее экономии мы достигнем, если будем строить не все дерево поездок, а только некоторую его часть. Именено такое усеченное дерево, отличающее от дерева всех поездок отсутствием тех ветвей, которые не могут дать кратчайшего маршрута, и конструкруется в излагаемом ниже варианте метода ветвей и границ.

Опишем последовательность этапов такого метода решения задачи коммуникара (блок-схема излагаемого алгоритма приведена на рисунке 3). Выполнить этап, переходим к следующему, если нам не предписано иное.

1. Рисуем корневую вершину дерева (для определения будем считать, что она соответствует городу I). Присваиваем ей оценку 0.

2. Производим ветвление из любой вершины с минимальной оценкой (первоначально из корневой). Это значит, что мы проводим от выбранной вершины все те стрелки, которые исходили бы из нее в дереве возможных поездок, и рисуем соответствующие вершины дерева.

3. Каждый новой вершине присваиваем оценку, равную длине той части маршрута, которая описывает стрелками, ведущими из корневой вершины в данную.

16

Рис. 3.

4. Если получена вершина, соответствующая городу I, то нахо-
   дим длину Г кратчайшего из получен-
   ных к этому моменту туров. Если нет,
   переходим к этапу 2.

5. Отсекаем все вершины, из которых еще не производилось ветвление (концевые вершины) и оценка ко-
   торых не меняше Г. Это означает, что из таких вершин ветвление впредь не производится. Если не все конце-
   вые вершины отсечены, переходим к этапу 2. Если все, то задача решения: оптимальный тур имеет длину Г и восстанавливается по той концевой вершине, с помощью которого было получено последнее значение Г (см. этап 4).

Этап 2 описывает правило ветвления, этап 3 — процедур вычисления оценок, этап 4 — нахождение границ и этап 5 — процедур отсечения.

Решим методом ветвей и границ задачу коммивояжера с расстояниями, заданным таблицей 3.

Решение приведено на рисунке 4. Пер-
выые четыре ветвления изображены с помощью зеленьх стрелок. Присваиваем Г значение

Г=8 и отсекаем две вершины. Пятое ветвление соответствует синей стрелке. Мы выбрали из двух концевых вершин с минимальной оценкой 4 ту, которая дальше от корня (в надежде на более быстroe получение еще одного тура и уменьшение значения Г). При следующих ветвления отмечены красными стрелками. Телерь Г=5, и мы отсекаем все остальные концевые вершины. Решением является тур I→II→III→IV→I длины 5.

Описанный вариант метода ветвей и границ позволяет решать на ЭВМ задачу коммивояжера с k≤20. Ясно, что он действительное всегда приводит к кратчайему туру, либо в нем используется дерево возможных

Таблица 3

N I II III IV

I — 4 0 9

II 5 — 0 3

III 6 4 — 1

IV 0 2 6 —

17

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

Можно справиться и с сотней городов!

В 1963 году был опубликован очень удачный вариант метода ветвей и границ, в котором при вычислении оценок к длине уже пройденой части маршрута добавлялось число, оценивающее длину его остальной части. Правило ветвления в этом метода (его автор — Катта Мурти — американский математик индийского происхождения) таково, что при каждом ветвлении образуется две новые ветви *). Метод Мурти позволил за сравнительно короткое время решать на ЭВМ задачу коммивояжера для $k \leq 40$.

Позднее был разработан еще один вариант метода ветвей и границ (метод Истмена — Шапиро). С помощью этого метода удалось решить несколько задач коммивояжера при $k \leq 70$. Дальнейшая разработка метода Истмена — Шапиро позволила довести размер решаемых на ЭВМ задачу до 100—120 городов.

В метода Истмена — Шапиро для вычисления оценок используется то обстоятельство, что существует в связи эффективные машинные методы решения так называемой задачи о назначения *), тесно связанной с задачей коммивояжера. Содержательно задача о назначениях формулируется следующим образом: имеются $k$ человек и $k$ должностей, и известна матрица баллов несоответствия людей должностям. Требуется найти такое назначение работников на должности, которое минимизирует сумму баллов несоответствия. Здесь матрица баллов играет ту же роль, что и матрица расстояний в задаче коммивояжера. А назначения, как и позедки, можно записывать в виде $x \rightarrow y$. Разница лишь в том, что из назначений не обязательно складывается замкнутый маршрут (тур). Возможно, например, такое назначение $I \rightarrow V \rightarrow I$, $II \rightarrow II$, $III \rightarrow IV \rightarrow VI \rightarrow III$ (это значит, что первый человек назначется на пятую должность, пятый — на первую, второй — на вторую, третий — на четвертую и т. д.).

Итак, каждый тур можно считать назначением (но назначение $k$ лиц

*) Описание метода Мурти см., например, в брошюре В. И. Мудрова «Задча коммивояжера», М., «Знание», 1969.

*) Про задачу о назначениях было рассказано в статье М. И. Рейтмана «Транспортная задача» («Квант», 1974, № 7).

Рис. 4.

18

Оказывается туром в среднем лишь в одном из $k$ случайов: ведь существует ($k-1$!) туров, а общее число $k$-назначений равно $k!$. Поэтому сумма баллов для оптимального $k$-назначения не превыходит длины оптимального типа. А эту сумму баллов, как мы уже отмечали, ЭВМ находит сравнительно быстро. Ее-то и использует в качестве оценки в метода Истмена — Шапиро, в котором строится не дерево поедок, а совсем другое дерево, вершинами которого является вспомогательные задачи о назначениях (пример такого дерева избражен на рисунке 5).

По этому методу сначала решается задача о назначениях с матрицей расстояний задачи коммуникатора в качестве матрицы баллов. Ей соответствуют корневая вершина дерева. Сумма баллов для оптимального назначения считается оценкой корневой вершины (и исходной задачи коммуникара). Если решением является тур, то задача коммуникара решена: найdenный тур является оптимальным. Если же $k$-назначение состоит из нескольких циклических последовательностей, например, $I \rightarrow III \rightarrow VII \rightarrow V \rightarrow I$, $IV \rightarrow VI \rightarrow II \rightarrow IV$, то поскольку в оптимальном type не может быть «подтуров», все эти циклические последовательности нужно разорвать. В метода Истмена — Шапиро это осуществляется в ходе вводаления, причем всегда работает одна — наиболее короткая — последовательность назначений, с тем чтобы в дальнейшем решать меньшее число новых задач о назначениях.

В нашем примере — это вторая; в нее входят три города: $II$, $IV$ и $VI$. Накладываем запреты на позедки $IV \rightarrow VI$, $VI \rightarrow II$ и $II \rightarrow IV$, после чего решаем три новые задачи о назначениях с треями новых матрицами баллов, получающимся из матрицы, соответствующей корневой вершине: в первой из них элемент $c_{46}$, во второй — элемент $c_{62}$, а в третьей — элемент $c_{24}$ заменены символом $\infty$, содержательно ознакомим запрет соответствующего позедки (через $c_{ab}$ мы снова обозначили расстояние между городами $a$ и $b$). Если среди решений есть туры, то $\Gamma$ полагается равным длине кратчайшего из них. Задачи с оценкой, не меняшей чем $\Gamma$, «отсекаются». Очередное ввведение осуществляется для той из этих задач, у которой $k$-назначение не является туром, а оценка (сумма баллов несоответствия) оказывается наименьшей.

Прокомментируем процесс решения, схема которого приведена на рисунке 5.

Выили сделаны два вввления и решены шесть задачи о назначениях. Решением задачи 4 оказался цикл. С этого момента $\Gamma = 44$, и задачи с оценкой 45 и 44 отсекаются.

В решении задачи 3 входило назначение $IV \rightarrow V \rightarrow IV$. Второе вввление приводило к двум новым задачи: 5 и 6. Решение задачи 5 — цикл длины 42. Это новое значение $\Gamma$ позволяет отсекаться.

Эвристические методы

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

Субоптимальные является, например, метод «иди в ближний», т. е. в ближайший из непройденных го-

19

родов. В том, что этот метод не является точным, легко убедиться на примере следующей простой матрицы расстояний (см. таблицу 4).

Для нее процедура «иди в ближний» дает маршрут I→III→II→I длины 10, в то время как нелена процедура «иди в дальней» приводит к туру I→II→III→I длины 8. Так как других маршрутов у коммуникация сейчас нет, этот пример означает, что наш эвристический метод может иногда давать даже самый плоской из туров.

Тем не менее, прицели «иди в ближний» (и другие эвристические методы) нередко используется на практике — особенно при решении задачи коммуникация с очень большим числом городов. Делается это по нескольким принципам. Во-первых, этот метод довольно быстро работает. Во-вторых, практика показывает, что с ростом $k$ метод «иди в ближний» все чаще дает туры,лина которых незначительно отличается от длины кратчайшего тура (а, порой, и совпадает с ним). И, наконец, общее для всех эвристических методов обстоятельство: во многих практических задачах нас интересует не наплачшее решение, а лишь достаточно хорошо приближение к нему (ведь порой и расстояния между городами определяются несовсем точно). К тому же точно алгоритма «иди в ближний» увеличивается (но заго缕 увеличается и трудоемкость), если в ходе его работы строятся $k$ туров, первый из которых начинают конструкровать с первого города, второй — со второго и т. д.; некоторые из этих туров могут оказаться разными, и в заключение выбирается кратчайший из них.

Для задчи коммивояжаса создано немало весы эфективных эвристических методов. В частности, неплохо себя зарекомендовали методы ветвей и границ, работа которых обрывается на одном из найденных типов (не обязательно — оптимальным). Так, в 1976 г. два японских математika решили на ЭВМ НITAC-8800 задачу коммивояжара для 300 городов. При этом за 2 минуты было найдено решение, отлично оценесая от оптимального на 0,2 процента.

Удивительная страна

Представим себе, что уже знакомые нам А. Невский и Б. Литейный решили попутешествовать по небольшой стране (назовем ее Константей). Прибив в ее столицу и найдя в путешествительстве семь самых интересных городов Константей, они планируют маршрут своего поезда. На этот раз расстояния между городами оказались не только большими (см. таблицу 5). Поэтому друзья решили не гнаться за минимальное, а вычислить длины нескольких случайно взятых туров и выбрать кратчайший из них (такая процедура тоже представляется собой субоптимальный метод, известный под названием метода Monme-Karло). Выбор пал на следующие туры:

I→II→III→IV→V→VI→VII→VIII→I;
I→III→VII→II→IV→VI→VIII→I;
I→IV→VII→II→V→VIII→I.

Подсчитали их протяженность; оказалось, что все три тура имеют длину 794 км! Занитересовавшись, наши

20

герои проанализировали еще десять маршрутов. Каждый из них имел длину 794 км! Можно себе представить, как смутились наши героны. Но удивление их было бы еще больше, если бы они узнали, что при данной матрице расстояний все вообще туры имеют одинаковую длину.

Почему? Ларчик открывается простое: все числа 5 получены путем сложения друг с другом чисел 48, 55, 66, 38, 61, 42, 50 и 37. Например, в третьей строке стоит суммы 66+48=114, 66+55=121, 0, 66+38=104 и т. д. А так как при вычислении протяженности маршрута мы берем по одному и только одному числу из каждой строки и из каждой стольца таблицы 5, то в результате длина любого типа оказывается равной удвоенной сумме задуманных чисел (сумма восемми задуманных чисел равна 397, а 794=397×2).

Возникает вопрос: а нельзя ли описать все вообще матрицы расстояний, при которых любые два тура имеют одинаковую длину? Оказывается, можно: для любой такой матрицы обязательно найти числа $a_1, a_2, \dots, a_k$ и числа $b_1, b_2, \dots, b_k$, такие, что расстояние $c_{xy}$ от города $x$ до города $y$ ($x \neq y$) будет равно сумме $a_x + b_y$.

Докажем эту теорему для случая трех городов.

Пусть $c$ — длина каждой из двух туров:
$$c = c_{12} + c_{23} + c_{31} = c_{13} + c_{21} + c_{32}.$$
Выразим из этих соотношений $c_{31}$ и $c_{32}$:
$$c_{31} = c - c_{12} - c_{23},$$
$$c_{32} = c - c_{13} - c_{21}.$$
Нам нужно решить систему уравнений
$$x_1 + y_2 = c_{12}, x_1 + y_3 = c_{13},$$
$$x_2 + y_1 = c_{21}, x_2 + y_3 = c_{23},$$
$$x_3 + y_1 = c - c_{12} - c_{23},$$
$$x_3 + y_2 = c - c_{13} - c_{21}.$$
Приводим неизвестному $y_3$ произвольное значение $d$. Тогда из первых пятей уравнений находится, что $x_1 = c_{13} - d, x_2 = c_{23} - d, y_2 = c_{12} - c_{13} + d, y_1 = c_{21} - c_{23} + d,$
$$x_3 = c - c_{12} - c_{23} - c_{21} + c_{23} - d = c - d - c_{12} - c_{21}.$$
При этом оказывается удовлетворенным и шестое уравнение. Положив $d = 0$, получим набор $a_1 = c_{13}, a_2 = c_{23}, a_3 = c - c_{12} - c_{21}, b_1 = c_{21} - c_{23}, b_2 = c_{12} - c_{13}, b_3 = 0$ чисел с нужным нам свойством.

Сформирована выше теорема является довольно типичной для теоретических исследований по задание коммивояжера. В них важную роль играют различные специальные случаи. (Совпадение длинны всех туров — это тоже специальный случай. Впрочем, веса узкий.) Для специальных случаяев порой удаляется не только построить быстро работающий метод (при этом говорят о разрешимом случае), но и выяснить, какие протяжности может иметь оптимальный тур.

Читатель может продолжить знакомство с разрешимыми случаями задачи коммивояжера, решив предлагаемые ниже задачи. В части из них решить о путешествии по шахматной доске, где в роли коммивояжера выступают шахматные фигуры. При этом будем говорить не о.type коммивояжера, а о.type коня, ладьи и т. д. Тур шахматной фигуры продолжитровно один раз по всем полям шахматной доски и заканчивается возвращением на начальное поле.

Задание

1. Города расположены в вершинах выпуклого многоугольника. Докажите, что длина оптимального типа равна перimetру многоугольника.
2. Сводится ли к задание коммивояжера задача о кратчайшем маршруте туриста, который выздает из пункта 1, послеает пункты 2, 3, …, $k-1$ и покидает страну из пункта $k$? Тот же вопрос для задачи о минимизации пути посыльного, который направляется из пункта 1 в пункта 2, 3, …, $k$. Возможно ли это сведение для задачи о диверсантах, которые, чтобы взорвать объекты, расположенные в пунктах 1, 2, …, $k$, планируют место decantирования и кратчайший маршрут через все пункты?
3. На плоскости расположены 30 городов. Их координаты: $y = 0, 1, 2$ при $x = 0; y = 0, 1, 2, 4, 5, 6$ при $x = 1; y = 1, 2, 3, 4, 6, 7, 8$ при $x = 2; y = 0, 1, 3, 4, 6, 7, 8$ при $x = 3; y = 0, 1, 2, 3, 4, 5, 6$ при $x = 4$. Решите задачу коммивояжера. Докажите, что полученный тур оптимален.
4. При каких размерах шахматной доски на ней существует тур ладьи? Тур ослабленной ладьи, которая ходит только на соседние поля?
5. На шахматной доске с нечетным числом полей одно поле вырезано. При каких разложениях вырезанного поля существует тур ослабленной ладьи?
6. Найдите тур коня на пространственной «доске», имеющей форму прямоугольного параллелепипеда размером $3 \times 4 \times 6$. «Полями» сейчас считаются 72 куба единичного объема, на которых наша «доска» естественным образом разбиется.
7. Данны числа $k$ и $m$. Как построить матрицу расстояний для задачи коммивояжера с $k$ городами, решением которого был тур длины $km?$