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

Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), метрическая задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.

Оптимизационная постановка задачи относится к классу очень NP-трудных задач, впрочем как и большинство её частных случаев. Версия «decision problem» (то есть такая, в которой ставится вопрос существует ли маршрут не длиннее, чем заданное значение k) относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.

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

История

Точно неизвестно, когда проблему коммивояжера исследовали впервые. Однако, известна изданная в 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), в которой описана проблема, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.

Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру (нем. Karl Menger), который сформулировал её на математическом коллоквиуме в 1930 году так:

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

Вскоре появилось известное сейчас название задача странствующего торговца (англ. Traveling Salesman Problem), которую предложил Хасслер Уитни (англ. Hassler Whitney) из Принстонского университета.

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

Многие современные распространенные методы дискретной оптимизации, такие как метод отсечений, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжёра.

В 1950-е и 1960-е годы задача коммивояжёра привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M. Johnson), которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для её решения метод отсечений. Используя этот метод, они построили путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения её приложений в информатике, экономике, химии и биологии.

Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-трудность задачи коммивояжёра. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.

Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Джованни Ринальди (итал. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашека Шватал (англ. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжёра различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1 % больше оптимальной.

Формальное определение

Представление в виде графа

Для возможности применения математического аппарата для решения проблемы, её следует представить в виде математической модели. Проблему коммивояжёра можно представить в виде модели на графе, то есть, используя вершины и ребра между ними. Таким образом, вершины графа соответствуют городам, а рёбра <math>\left ( i,j \right )</math> между вершинами <math>i</math> и <math>j</math> — пути сообщения между этими городами. Каждому ребру <math>\left ( i,j \right )</math> можно сопоставить критерий выгодности маршрута <math>c_{ij} \geqslant 0</math>, который можно понимать как, например, расстояние между городами, время или стоимость поездки.

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

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

Таким образом, решение задачи коммивояжёра — это нахождение гамильтонова цикла минимального веса в полном взвешенном графе.

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

Асимметричная и симметричная задачи

В общем случае, асимметричная задача коммивояжёра отличается тем, что она моделируется ориентированным графом. Таким образом, следует также учитывать, в каком направлении находятся ребра.

В случае симметричной задачи все пары ребер между одними и теми же вершинами имеют одинаковую длину, то есть, для ребра <math>\left ( i,j \right )</math> одинаковы длины <math>c_{ij} = c_{ji}</math>. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая. Симметричная задача моделируется неориентированным графом (см. рисунок).

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

Метрическая задача

Симметричную задачу коммивояжёра называют метрической, если относительно длин ребер выполняется неравенство треугольника. Условно говоря, в таких задачах обходные пути длиннее прямых, то есть, ребро от вершины <math>i</math> до вершины <math>j</math> никогда не бывает длиннее пути через промежуточную вершину <math>k</math>:

<math>c_{ij} \leqslant c_{ik} + c_{kj}</math>.

Такое свойство длины ребер определяет измеримое пространство на множестве ребер и меру расстояния, удовлетворяющую интуитивному пониманию расстояния.

Распространенные на практике функции расстояния являются также метриками и удовлетворяют неравенству треугольника:

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

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

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

Если на практике в условиях задачи разрешается посещать города несколько раз, то симметричную задачу можно свести к метрической. Для этого задачу рассматривают на так называемом графе расстояний. Этот граф имеет такое же множество вершин, как и исходный, и является полностью связным. Длина рёбер <math>c_{ij}</math> между вершинами <math>i</math> и <math>j</math> на графе расстояний соответствует длине кратчайшего расстояния между вершинами <math>i</math> и <math>j</math> в исходном графе. Для определенных таким образом длин <math>c_{ij}</math> выполняется неравенство треугольника, и каждому маршруту на графе расстояний всегда соответствует маршрут с возможными повторениями вершин в исходном графе.

Формулировка в виде задачи дискретной оптимизации

Одним из подходов к решению задачи является формулировка её в виде задачи дискретной оптимизации, при этом решения представляются в виде переменных, а связи — в виде отношений неравенства между ними. Таким образом, возможно несколько вариантов. Например, симметричную задачу можно представить в виде множества ребер <math>V</math>. Каждому ребру <math>\{i, j\}</math> сопоставляется двоичная переменная <math>x_{ij} \in \{0,1\}</math>, равная 1, если ребро принадлежит маршруту, и 0 — в противном случае. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства. Каждая вершина должна сообщаться через пару ребер с остальным вершинам, то есть, через входное и выходное ребро:

<math>\forall i \in V,\; \sum_{j \in V \setminus \{i\}} x_{ij} = 2 \qquad (1)</math>

В сумме каждое слагаемое <math>x_{ij}</math> равно или 1 (принадлежит маршруту) или 0 (не принадлежит). То есть, полученная сумма равна количеству ребер в маршруте, имеющих вершину <math>i</math> на одном из концов. Она равна 2, так как каждая вершина имеет входное и выходное ребро. В приведенном рядом рисунке вершина <math>i</math> показана с входным и выходными ребрами, а ребра маршрута обозначены толстыми линиями. Рядом с ребрами указаны длины <math>x_{ij}</math>, прилагаемые к указанной выше сумме. Описанные ранее условия кратности выполняются не только маршрутами, но и значениями переменных, соответствующих отдельным циклам, где каждая вершина принадлежит лишь одному циклу (см. рисунок). Чтобы избежать подобных случаев, должны выполняться так называемые неравенства циклов (или условия устранения подмаршрутов), которые были определены Данцигом, Фалкерсоном и Джонсоном в 1954 году под названием условия петель (англ. loop conditions). Этими неравенствами определялось дополнительное условие того, что каждое множество вершин <math>S \subset V</math> является либо пустым, либо содержит все вершины, сочетающееся с остальным вершинам через минимум два ребра:

<math>\sum_{i \in S, \; j \notin S} x_{ij} \geqslant 2 \qquad (2)</math>

для всех множеств вершин <math>S</math>, где <math>1 \leqslant |S| \leqslant |V|-1</math>. Эта сумма равна сумме длин ребер маршрута между вершиной <math>i \in S</math> и вершиной <math>j \notin S</math>. Чтобы устранить лишние неравенства, можно ограничиться множествами вершин <math>S</math> с минимум двумя и максимум <math>|V| - 2</math> вершинами. На рисунке рядом ребра <math>\{i,j\}</math> с длинами <math>x_{ij} = 1</math> обозначены толстыми линиями, остальные ребра имеют длину <math>x_{ij} = 0</math>. Введение дополнительных условий (2) для множества вершин <math>S</math>, состоящего из трех левых вершин, будет гарантировать, что <math>S</math> сочетается через минимум два ребра маршрута с тремя вершинами справа, чтобы устранить оба цикла. Количество неравенств устранения циклов согласно Данцигу, Фалкерсону и Джонсону равняется <math>2^{n}-2(n-1)</math>.

В 1960 году Миллер, Такер и Землин изобрели альтернативные условия устранения подмаршрутов путём введения <math>n</math> новых переменных, определяющих порядок посещенных городов, требующих только <math>n^2 - n + 1</math> дополнительных неравенств. Более того, из-за двойственности <math>x_{ij}</math> в формулировках Миллера, Такера и Землина задача коммивояжёра остается NP-сложной.

Так, каждый вектор с элементами, равными 0 и 1, удовлетворяющий всем неравенствам, определяет корректный маршрут, который является решением переформулированной задачи коммивояжёра: вычислить

<math>\min \; \left\{ \sum_{i \in V} \sum_{j \in V \setminus \{i\}} c_{ij} x_{ij} \;|\; x \mbox{ valid (1) (2),}\; x_{ij} \in \{0,1\} \right\}. \qquad (3)</math>

Поскольку переменные <math>x_{ij}</math> имеют значения только 0 и 1, сумма равна общей длине <math>c_{ij}</math> ребер <math>\{i,j\}</math>, принадлежащих маршруту.

Количество неравенств типа (2) растет экспоненциально по мере увеличения количества городов, поскольку почти каждое из <math>2^{|V|}</math> подмножеств узлов определяет одно неравенство. Эту проблему можно решить применением метода отсечения плоскостью, благодаря которому неравенства добавляются, только когда эти неравенства действительно необходимы. С геометрической точки зрения, линейные неравенства можно представить как гиперплоскости в пространстве переменных. Множество векторов, удовлетворяющих этим неравенствам, образуют в таком пространстве политоп (многомерный многогранник), или многомерный многоугольник, точная форма определяется длинами <math>c_{ij}</math> и является в основном неизвестной. Однако, можно показать, что условия (1) и (2) определяют грани (фацет) политопа, то есть боковые поверхности политопа с наивысшей размерностью. Поэтому они относятся к самым сильным линейным неравенствам, которые могут описывать маршрут. Также существует много разных граней, определяемых неравенствами, известными лишь в немногих случаях. Хотя (1) и (2) вместе с ограничениями полностью моделируют проблему только для двоичных векторов, эти неравенства могут использоваться в методе ветвей и границ, чтобы отбросить решения методами линейной оптимизации с нецелыми координатами (см. раздел точные методы ниже).

Алгоритмическая сложность

Поскольку коммивояжёр в каждом из городов встает перед выбором следующего города из тех, что он ещё не посетил, существует <math>(n-1)!</math> маршрутов для асимметричной и <math>(n-1)!/2</math> маршрутов для симметричной задачи коммивояжёра. Таким образом, размер пространства поиска зависит экспоненциально от количества городов.

Различные варианты задачи коммивояжёра (метрическая, симметричная и асимметричная) NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной машины Тьюринга, способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов.

Также известно, что при условии <math>P \neq NP</math> не существует алгоритма, который для некоторого полинома <math>p</math> вычислял бы такие решения задачи коммивояжёра, которые отличались бы от оптимального максимум на коэффициент <math>2^{p(n)}</math>.

Однако, существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность, лучшую чем 1,5 от оптимальной. По предположению <math>P \neq NP</math>, существует (неизвестная) константа <math>c > 0</math>, такая, что ни один алгоритм с полиномиальным временем не может гарантировать точность <math>1 + c</math>. Как было показано Арора, для евклидовой задачи коммивояжёра существует схема полиномиального времени PTAS для поиска приближённого решения.

Замкнутый и незамкнутый варианты задачи

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

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

Чтобы свести замкнутый вариант к незамкнутому, нужно определить число <math>K</math>, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве <math>K</math> можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину <math>v_n</math> (предполагаем, что вершины исходного графа пронумерованы числами от 0 до <math>n-1</math>, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину <math>v_n</math>, определяются следующим образом:

• <math>c_{n, i} = 3K</math>
• <math>c_{0, n} = 3K</math>
• <math>c_{i, n} = c_{i, 0} + 2K</math> при <math>i</math> от <math>1</math> до <math>n-1</math>

Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на <math>2K</math> больше.

Методы решения

Простейшие

• полный перебор
• случайный перебор
• жадные алгоритмы
  • метод ближайшего соседа
  • метод включения ближайшего города
  • метод самого дешёвого включения
• метод минимального остовного дерева
• метод имитации отжига

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра — методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time-алгоритмы^{[уточнить]}, то есть постепенно улучшающие некоторое текущее приближенное решение.

Существуют также постановки, в которых задача коммивояжёра становится NP-полной. Обычно такие постановки выглядят следующим образом: существует ли на заданном графе G такой обход, что его стоимость не превышает x. Часто на ней проводят обкатку новых подходов к эвристическому сокращению полного перебора.

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

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

Можно найти точное решение задачи коммивояжёра, то есть «вручную» вычислить длины всех возможных маршрутов и выбрать маршрут с наименьшей длиной. Однако даже для небольшого количества городов решать задачу таким способом практически невозможно. Для простого варианта, симметричной задачи с <math>n</math> городами, существует <math>(n-1)!/2</math> возможных маршрутов, то есть для 15 городов существует 43 миллиарда маршрутов и для 18 городов уже 177 триллионов. То, как стремительно растет продолжительность вычислений, можно показать на следующем примере. Если бы существовало устройство, находящее решение для 30 городов за час, то для двух дополнительных городов требуется в тысячу раз больше времени; то есть, более чем 40 суток.

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

В геометрической интерпретации, эти методы рассматривают задачу как выпуклый политоп, то есть многомерный многоугольник в <math>m</math>-мерном единичном кубе <math>[0,1]^m</math>, где <math>m</math> равно количеству ребер в графе. Каждое ребро этого единичного куба соответствует маршруту, то есть вектору с элементами 0/1, что удовлетворяет описанным выше линейным неравенствам. Гиперплоскости, описываемые этими неравенствами, отсекают такие ребра единичного куба, которые не соответствуют ни одному маршруту.

На рисунке рядом показано применение метода для задачи с тремя узлами. В соответствие трем возможным ребрам между вершинами сопоставляются бинарные переменные <math>x_1,\, x_2</math> и <math>x_3</math>. В этом случае существует лишь один возможный маршрут, а именно тот, что проходит через три вершины. Этот маршрут удовлетворяет неравенству <math>x_1 + x_2 + x_3 \geqslant 2</math>, которое утверждает, что маршрут должен проходить через минимум две вершины. Кроме этого маршрута, что соответствует вектору (1,1,1), неравенству удовлетворяют также все точки в отмеченной красным части этого неравенства. Плоскости, проходящие через красные линии, отсекают все углы, отвечающие несуществующим маршрутам с максимум одним ребром, а именно, ноль-вектор (0, 0, 0), единичные векторы (1, 0, 0), (0, 1, 0) и (0, 0, 1). Сильное неравенство <math>x_1 + x_2 + x_3 \geqslant 3</math> отсечет от единичного куба все, кроме единственной допустимой точки (1, 1, 1). В этом отдельном случае тот же эффект можно получить тремя неравенствами типа (1).

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

Однако этого метода для быстрого поиска маршрутов обычно недостаточно. Основное преимущество точных методов заключается в том, что имея достаточно времени, они вычисляют кратчайший маршрут. Имея нижнюю границу для оптимальных решений, можно оценить то, насколько отличается найденный маршрут от оптимального. Например, имея нижнюю границу на уровне 100, и после нахождения маршрута длиной 102, оптимальный маршрут может находиться в пределах от 100 до 102. Так называемый интервал оптимальности, или максимальное относительное расстояние между длиной оптимального маршрута и кратчайшим известным маршрутом составит (102—100)/100 = 2%, то есть длина найденного маршрута 102 максимум на 2 % отличается от оптимальной. Когда длина вычисленного маршрута равна длине предыдущего, считается, что найденное решение является оптимальным. Для поиска маршрутов приемлемой длины точные методы могут комбинироваться с эвристическими.

Метод ветвей и границ для решения задачи коммивояжёра был предложен в 1963 году группой авторов (Дж. Литл, К. Мурти, Д. Суини, К. Кэрол).

Метод эластичной сети

См. также: Упругая карта и Выпуклая оболочка

История

В 1987 году его использовали Дурбин (Durbin) и Уиллшоу (Willshaw), указавшие аналогию с механизмами установления упорядоченных нейронных связей.

Каждый из маршрутов коммивояжёра рассматривался как отображение окружности на плоскость (в каждый город на плоскости отображается некоторая точка этой окружности). Соседние точки на окружности должны отображаться в точки, по возможности ближайшие и на плоскости.

Алгоритм

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

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

Дурбин и Уиллшоу показали, что для задачи с 30 городами, рассмотренной Хопфилдом и Танком, метод эластичной сети генерирует наикратчайший маршрут примерно за 1000 итераций. Для 100 городов найденный этим методом маршрут лишь на 1 % превосходил оптимальный.

См. также

• Граф (математика)
• Оптимизация
• Комбинаторика
• Исследование операций
• Математическое программирование
• Дискретная математика
• Транспортная логистика
• Проблема Штейнера

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.
• В.И. Мудров. Задача о коммивояжёре. — М.: «Знание», 1969. — С. 62.
• Ежов А., Шумский С. Нейрокомпьютинг и его применения в экономике и бизнесе . — М.: МИФИ, 1998. — С. 216.

Отрывок, характеризующий Задача коммивояжёра

– Ты полагал! – закричал князь, всё поспешнее и несвязнее выговаривая слова. – Ты полагал… Разбойники! прохвосты! Я тебя научу полагать, – и, подняв палку, он замахнулся ею на Алпатыча и ударил бы, ежели бы управляющий невольно не отклонился от удара. – Полагал! Прохвосты! – торопливо кричал он. Но, несмотря на то, что Алпатыч, сам испугавшийся своей дерзости – отклониться от удара, приблизился к князю, опустив перед ним покорно свою плешивую голову, или, может быть, именно от этого князь, продолжая кричать: «прохвосты! закидать дорогу!» не поднял другой раз палки и вбежал в комнаты.
Перед обедом княжна и m lle Bourienne, знавшие, что князь не в духе, стояли, ожидая его: m lle Bourienne с сияющим лицом, которое говорило: «Я ничего не знаю, я такая же, как и всегда», и княжна Марья – бледная, испуганная, с опущенными глазами. Тяжелее всего для княжны Марьи было то, что она знала, что в этих случаях надо поступать, как m lle Bourime, но не могла этого сделать. Ей казалось: «сделаю я так, как будто не замечаю, он подумает, что у меня нет к нему сочувствия; сделаю я так, что я сама скучна и не в духе, он скажет (как это и бывало), что я нос повесила», и т. п.
Князь взглянул на испуганное лицо дочери и фыркнул.
– Др… или дура!… – проговорил он.
«И той нет! уж и ей насплетничали», подумал он про маленькую княгиню, которой не было в столовой.
– А княгиня где? – спросил он. – Прячется?…
– Она не совсем здорова, – весело улыбаясь, сказала m llе Bourienne, – она не выйдет. Это так понятно в ее положении.
– Гм! гм! кх! кх! – проговорил князь и сел за стол.
Тарелка ему показалась не чиста; он указал на пятно и бросил ее. Тихон подхватил ее и передал буфетчику. Маленькая княгиня не была нездорова; но она до такой степени непреодолимо боялась князя, что, услыхав о том, как он не в духе, она решилась не выходить.
– Я боюсь за ребенка, – говорила она m lle Bourienne, – Бог знает, что может сделаться от испуга.
Вообще маленькая княгиня жила в Лысых Горах постоянно под чувством страха и антипатии к старому князю, которой она не сознавала, потому что страх так преобладал, что она не могла чувствовать ее. Со стороны князя была тоже антипатия, но она заглушалась презрением. Княгиня, обжившись в Лысых Горах, особенно полюбила m lle Bourienne, проводила с нею дни, просила ее ночевать с собой и с нею часто говорила о свекоре и судила его.
– Il nous arrive du monde, mon prince, [К нам едут гости, князь.] – сказала m lle Bourienne, своими розовенькими руками развертывая белую салфетку. – Son excellence le рrince Kouraguine avec son fils, a ce que j'ai entendu dire? [Его сиятельство князь Курагин с сыном, сколько я слышала?] – вопросительно сказала она.
– Гм… эта excellence мальчишка… я его определил в коллегию, – оскорбленно сказал князь. – А сын зачем, не могу понять. Княгиня Лизавета Карловна и княжна Марья, может, знают; я не знаю, к чему он везет этого сына сюда. Мне не нужно. – И он посмотрел на покрасневшую дочь.
– Нездорова, что ли? От страха министра, как нынче этот болван Алпатыч сказал.
– Нет, mon pere. [батюшка.]
Как ни неудачно попала m lle Bourienne на предмет разговора, она не остановилась и болтала об оранжереях, о красоте нового распустившегося цветка, и князь после супа смягчился.
После обеда он прошел к невестке. Маленькая княгиня сидела за маленьким столиком и болтала с Машей, горничной. Она побледнела, увидав свекора.
Маленькая княгиня очень переменилась. Она скорее была дурна, нежели хороша, теперь. Щеки опустились, губа поднялась кверху, глаза были обтянуты книзу.
– Да, тяжесть какая то, – отвечала она на вопрос князя, что она чувствует.
– Не нужно ли чего?
– Нет, merci, mon pere. [благодарю, батюшка.]
– Ну, хорошо, хорошо.
Он вышел и дошел до официантской. Алпатыч, нагнув голову, стоял в официантской.
– Закидана дорога?
– Закидана, ваше сиятельство; простите, ради Бога, по одной глупости.
Князь перебил его и засмеялся своим неестественным смехом.
– Ну, хорошо, хорошо.
Он протянул руку, которую поцеловал Алпатыч, и прошел в кабинет.
Вечером приехал князь Василий. Его встретили на прешпекте (так назывался проспект) кучера и официанты, с криком провезли его возки и сани к флигелю по нарочно засыпанной снегом дороге.
Князю Василью и Анатолю были отведены отдельные комнаты.
Анатоль сидел, сняв камзол и подпершись руками в бока, перед столом, на угол которого он, улыбаясь, пристально и рассеянно устремил свои прекрасные большие глаза. На всю жизнь свою он смотрел как на непрерывное увеселение, которое кто то такой почему то обязался устроить для него. Так же и теперь он смотрел на свою поездку к злому старику и к богатой уродливой наследнице. Всё это могло выйти, по его предположению, очень хорошо и забавно. А отчего же не жениться, коли она очень богата? Это никогда не мешает, думал Анатоль.
Он выбрился, надушился с тщательностью и щегольством, сделавшимися его привычкою, и с прирожденным ему добродушно победительным выражением, высоко неся красивую голову, вошел в комнату к отцу. Около князя Василья хлопотали его два камердинера, одевая его; он сам оживленно оглядывался вокруг себя и весело кивнул входившему сыну, как будто он говорил: «Так, таким мне тебя и надо!»
– Нет, без шуток, батюшка, она очень уродлива? А? – спросил он, как бы продолжая разговор, не раз веденный во время путешествия.
– Полно. Глупости! Главное дело – старайся быть почтителен и благоразумен с старым князем.
– Ежели он будет браниться, я уйду, – сказал Анатоль. – Я этих стариков терпеть не могу. А?
– Помни, что для тебя от этого зависит всё.
В это время в девичьей не только был известен приезд министра с сыном, но внешний вид их обоих был уже подробно описан. Княжна Марья сидела одна в своей комнате и тщетно пыталась преодолеть свое внутреннее волнение.
«Зачем они писали, зачем Лиза говорила мне про это? Ведь этого не может быть! – говорила она себе, взглядывая в зеркало. – Как я выйду в гостиную? Ежели бы он даже мне понравился, я бы не могла быть теперь с ним сама собою». Одна мысль о взгляде ее отца приводила ее в ужас.
Маленькая княгиня и m lle Bourienne получили уже все нужные сведения от горничной Маши о том, какой румяный, чернобровый красавец был министерский сын, и о том, как папенька их насилу ноги проволок на лестницу, а он, как орел, шагая по три ступеньки, пробежал зa ним. Получив эти сведения, маленькая княгиня с m lle Bourienne,еще из коридора слышные своими оживленно переговаривавшими голосами, вошли в комнату княжны.
– Ils sont arrives, Marieie, [Они приехали, Мари,] вы знаете? – сказала маленькая княгиня, переваливаясь своим животом и тяжело опускаясь на кресло.
Она уже не была в той блузе, в которой сидела поутру, а на ней было одно из лучших ее платьев; голова ее была тщательно убрана, и на лице ее было оживление, не скрывавшее, однако, опустившихся и помертвевших очертаний лица. В том наряде, в котором она бывала обыкновенно в обществах в Петербурге, еще заметнее было, как много она подурнела. На m lle Bourienne тоже появилось уже незаметно какое то усовершенствование наряда, которое придавало ее хорошенькому, свеженькому лицу еще более привлекательности.
– Eh bien, et vous restez comme vous etes, chere princesse? – заговорила она. – On va venir annoncer, que ces messieurs sont au salon; il faudra descendre, et vous ne faites pas un petit brin de toilette! [Ну, а вы остаетесь, в чем были, княжна? Сейчас придут сказать, что они вышли. Надо будет итти вниз, а вы хоть бы чуть чуть принарядились!]
Маленькая княгиня поднялась с кресла, позвонила горничную и поспешно и весело принялась придумывать наряд для княжны Марьи и приводить его в исполнение. Княжна Марья чувствовала себя оскорбленной в чувстве собственного достоинства тем, что приезд обещанного ей жениха волновал ее, и еще более она была оскорблена тем, что обе ее подруги и не предполагали, чтобы это могло быть иначе. Сказать им, как ей совестно было за себя и за них, это значило выдать свое волнение; кроме того отказаться от наряжения, которое предлагали ей, повело бы к продолжительным шуткам и настаиваниям. Она вспыхнула, прекрасные глаза ее потухли, лицо ее покрылось пятнами и с тем некрасивым выражением жертвы, чаще всего останавливающемся на ее лице, она отдалась во власть m lle Bourienne и Лизы. Обе женщины заботились совершенно искренно о том, чтобы сделать ее красивой. Она была так дурна, что ни одной из них не могла притти мысль о соперничестве с нею; поэтому они совершенно искренно, с тем наивным и твердым убеждением женщин, что наряд может сделать лицо красивым, принялись за ее одеванье.
– Нет, право, ma bonne amie, [мой добрый друг,] это платье нехорошо, – говорила Лиза, издалека боком взглядывая на княжну. – Вели подать, у тебя там есть масака. Право! Что ж, ведь это, может быть, судьба жизни решается. А это слишком светло, нехорошо, нет, нехорошо!
Нехорошо было не платье, но лицо и вся фигура княжны, но этого не чувствовали m lle Bourienne и маленькая княгиня; им все казалось, что ежели приложить голубую ленту к волосам, зачесанным кверху, и спустить голубой шарф с коричневого платья и т. п., то всё будет хорошо. Они забывали, что испуганное лицо и фигуру нельзя было изменить, и потому, как они ни видоизменяли раму и украшение этого лица, само лицо оставалось жалко и некрасиво. После двух или трех перемен, которым покорно подчинялась княжна Марья, в ту минуту, как она была зачесана кверху (прическа, совершенно изменявшая и портившая ее лицо), в голубом шарфе и масака нарядном платье, маленькая княгиня раза два обошла кругом нее, маленькой ручкой оправила тут складку платья, там подернула шарф и посмотрела, склонив голову, то с той, то с другой стороны.
– Нет, это нельзя, – сказала она решительно, всплеснув руками. – Non, Marie, decidement ca ne vous va pas. Je vous aime mieux dans votre petite robe grise de tous les jours. Non, de grace, faites cela pour moi. [Нет, Мари, решительно это не идет к вам. Я вас лучше люблю в вашем сереньком ежедневном платьице: пожалуйста, сделайте это для меня.] Катя, – сказала она горничной, – принеси княжне серенькое платье, и посмотрите, m lle Bourienne, как я это устрою, – сказала она с улыбкой предвкушения артистической радости.
Но когда Катя принесла требуемое платье, княжна Марья неподвижно всё сидела перед зеркалом, глядя на свое лицо, и в зеркале увидала, что в глазах ее стоят слезы, и что рот ее дрожит, приготовляясь к рыданиям.
– Voyons, chere princesse, – сказала m lle Bourienne, – encore un petit effort. [Ну, княжна, еще маленькое усилие.]
Маленькая княгиня, взяв платье из рук горничной, подходила к княжне Марье.
– Нет, теперь мы это сделаем просто, мило, – говорила она.
Голоса ее, m lle Bourienne и Кати, которая о чем то засмеялась, сливались в веселое лепетанье, похожее на пение птиц.
– Non, laissez moi, [Нет, оставьте меня,] – сказала княжна.
И голос ее звучал такой серьезностью и страданием, что лепетанье птиц тотчас же замолкло. Они посмотрели на большие, прекрасные глаза, полные слез и мысли, ясно и умоляюще смотревшие на них, и поняли, что настаивать бесполезно и даже жестоко.
– Au moins changez de coiffure, – сказала маленькая княгиня. – Je vous disais, – с упреком сказала она, обращаясь к m lle Bourienne, – Marieie a une de ces figures, auxquelles ce genre de coiffure ne va pas du tout. Mais du tout, du tout. Changez de grace. [По крайней мере, перемените прическу. У Мари одно из тех лиц, которым этот род прически совсем нейдет. Перемените, пожалуйста.]
– Laissez moi, laissez moi, tout ca m'est parfaitement egal, [Оставьте меня, мне всё равно,] – отвечал голос, едва удерживающий слезы.
M lle Bourienne и маленькая княгиня должны были признаться самим себе, что княжна. Марья в этом виде была очень дурна, хуже, чем всегда; но было уже поздно. Она смотрела на них с тем выражением, которое они знали, выражением мысли и грусти. Выражение это не внушало им страха к княжне Марье. (Этого чувства она никому не внушала.) Но они знали, что когда на ее лице появлялось это выражение, она была молчалива и непоколебима в своих решениях.
– Vous changerez, n'est ce pas? [Вы перемените, не правда ли?] – сказала Лиза, и когда княжна Марья ничего не ответила, Лиза вышла из комнаты.
Княжна Марья осталась одна. Она не исполнила желания Лизы и не только не переменила прически, но и не взглянула на себя в зеркало. Она, бессильно опустив глаза и руки, молча сидела и думала. Ей представлялся муж, мужчина, сильное, преобладающее и непонятно привлекательное существо, переносящее ее вдруг в свой, совершенно другой, счастливый мир. Ребенок свой, такой, какого она видела вчера у дочери кормилицы, – представлялся ей у своей собственной груди. Муж стоит и нежно смотрит на нее и ребенка. «Но нет, это невозможно: я слишком дурна», думала она.
– Пожалуйте к чаю. Князь сейчас выйдут, – сказал из за двери голос горничной.
Она очнулась и ужаснулась тому, о чем она думала. И прежде чем итти вниз, она встала, вошла в образную и, устремив на освещенный лампадой черный лик большого образа Спасителя, простояла перед ним с сложенными несколько минут руками. В душе княжны Марьи было мучительное сомненье. Возможна ли для нее радость любви, земной любви к мужчине? В помышлениях о браке княжне Марье мечталось и семейное счастие, и дети, но главною, сильнейшею и затаенною ее мечтою была любовь земная. Чувство было тем сильнее, чем более она старалась скрывать его от других и даже от самой себя. Боже мой, – говорила она, – как мне подавить в сердце своем эти мысли дьявола? Как мне отказаться так, навсегда от злых помыслов, чтобы спокойно исполнять Твою волю? И едва она сделала этот вопрос, как Бог уже отвечал ей в ее собственном сердце: «Не желай ничего для себя; не ищи, не волнуйся, не завидуй. Будущее людей и твоя судьба должна быть неизвестна тебе; но живи так, чтобы быть готовой ко всему. Если Богу угодно будет испытать тебя в обязанностях брака, будь готова исполнить Его волю». С этой успокоительной мыслью (но всё таки с надеждой на исполнение своей запрещенной, земной мечты) княжна Марья, вздохнув, перекрестилась и сошла вниз, не думая ни о своем платье, ни о прическе, ни о том, как она войдет и что скажет. Что могло всё это значить в сравнении с предопределением Бога, без воли Которого не падет ни один волос с головы человеческой.


Когда княжна Марья взошла в комнату, князь Василий с сыном уже были в гостиной, разговаривая с маленькой княгиней и m lle Bourienne. Когда она вошла своей тяжелой походкой, ступая на пятки, мужчины и m lle Bourienne приподнялись, и маленькая княгиня, указывая на нее мужчинам, сказала: Voila Marie! [Вот Мари!] Княжна Марья видела всех и подробно видела. Она видела лицо князя Василья, на мгновенье серьезно остановившееся при виде княжны и тотчас же улыбнувшееся, и лицо маленькой княгини, читавшей с любопытством на лицах гостей впечатление, которое произведет на них Marie. Она видела и m lle Bourienne с ее лентой и красивым лицом и оживленным, как никогда, взглядом, устремленным на него; но она не могла видеть его, она видела только что то большое, яркое и прекрасное, подвинувшееся к ней, когда она вошла в комнату. Сначала к ней подошел князь Василий, и она поцеловала плешивую голову, наклонившуюся над ее рукою, и отвечала на его слова, что она, напротив, очень хорошо помнит его. Потом к ней подошел Анатоль. Она всё еще не видала его. Она только почувствовала нежную руку, твердо взявшую ее, и чуть дотронулась до белого лба, над которым были припомажены прекрасные русые волосы. Когда она взглянула на него, красота его поразила ее. Анатопь, заложив большой палец правой руки за застегнутую пуговицу мундира, с выгнутой вперед грудью, а назад – спиною, покачивая одной отставленной ногой и слегка склонив голову, молча, весело глядел на княжну, видимо совершенно о ней не думая. Анатоль был не находчив, не быстр и не красноречив в разговорах, но у него зато была драгоценная для света способность спокойствия и ничем не изменяемая уверенность. Замолчи при первом знакомстве несамоуверенный человек и выкажи сознание неприличности этого молчания и желание найти что нибудь, и будет нехорошо; но Анатоль молчал, покачивал ногой, весело наблюдая прическу княжны. Видно было, что он так спокойно мог молчать очень долго. «Ежели кому неловко это молчание, так разговаривайте, а мне не хочется», как будто говорил его вид. Кроме того в обращении с женщинами у Анатоля была та манера, которая более всего внушает в женщинах любопытство, страх и даже любовь, – манера презрительного сознания своего превосходства. Как будто он говорил им своим видом: «Знаю вас, знаю, да что с вами возиться? А уж вы бы рады!» Может быть, что он этого не думал, встречаясь с женщинами (и даже вероятно, что нет, потому что он вообще мало думал), но такой у него был вид и такая манера. Княжна почувствовала это и, как будто желая ему показать, что она и не смеет думать об том, чтобы занять его, обратилась к старому князю. Разговор шел общий и оживленный, благодаря голоску и губке с усиками, поднимавшейся над белыми зубами маленькой княгини. Она встретила князя Василья с тем приемом шуточки, который часто употребляется болтливо веселыми людьми и который состоит в том, что между человеком, с которым так обращаются, и собой предполагают какие то давно установившиеся шуточки и веселые, отчасти не всем известные, забавные воспоминания, тогда как никаких таких воспоминаний нет, как их и не было между маленькой княгиней и князем Васильем. Князь Василий охотно поддался этому тону; маленькая княгиня вовлекла в это воспоминание никогда не бывших смешных происшествий и Анатоля, которого она почти не знала. M lle Bourienne тоже разделяла эти общие воспоминания, и даже княжна Марья с удовольствием почувствовала и себя втянутою в это веселое воспоминание.
– Вот, по крайней мере, мы вами теперь вполне воспользуемся, милый князь, – говорила маленькая княгиня, разумеется по французски, князю Василью, – это не так, как на наших вечерах у Annette, где вы всегда убежите; помните cette chere Annette? [милую Аннет?]
– А, да вы мне не подите говорить про политику, как Annette!
– А наш чайный столик?
– О, да!
– Отчего вы никогда не бывали у Annette? – спросила маленькая княгиня у Анатоля. – А я знаю, знаю, – сказала она, подмигнув, – ваш брат Ипполит мне рассказывал про ваши дела. – О! – Она погрозила ему пальчиком. – Еще в Париже ваши проказы знаю!
– А он, Ипполит, тебе не говорил? – сказал князь Василий (обращаясь к сыну и схватив за руку княгиню, как будто она хотела убежать, а он едва успел удержать ее), – а он тебе не говорил, как он сам, Ипполит, иссыхал по милой княгине и как она le mettait a la porte? [выгнала его из дома?]
– Oh! C'est la perle des femmes, princesse! [Ах! это перл женщин, княжна!] – обратился он к княжне.
С своей стороны m lle Bourienne не упустила случая при слове Париж вступить тоже в общий разговор воспоминаний. Она позволила себе спросить, давно ли Анатоль оставил Париж, и как понравился ему этот город. Анатоль весьма охотно отвечал француженке и, улыбаясь, глядя на нее, разговаривал с нею про ее отечество. Увидав хорошенькую Bourienne, Анатоль решил, что и здесь, в Лысых Горах, будет нескучно. «Очень недурна! – думал он, оглядывая ее, – очень недурна эта demoiselle de compagn. [компаньонка.] Надеюсь, что она возьмет ее с собой, когда выйдет за меня, – подумал он, – la petite est gentille». [малютка – мила.]
Старый князь неторопливо одевался в кабинете, хмурясь и обдумывая то, что ему делать. Приезд этих гостей сердил его. «Что мне князь Василий и его сынок? Князь Василий хвастунишка, пустой, ну и сын хорош должен быть», ворчал он про себя. Его сердило то, что приезд этих гостей поднимал в его душе нерешенный, постоянно заглушаемый вопрос, – вопрос, насчет которого старый князь всегда сам себя обманывал. Вопрос состоял в том, решится ли он когда либо расстаться с княжной Марьей и отдать ее мужу. Князь никогда прямо не решался задавать себе этот вопрос, зная вперед, что он ответил бы по справедливости, а справедливость противоречила больше чем чувству, а всей возможности его жизни. Жизнь без княжны Марьи князю Николаю Андреевичу, несмотря на то, что он, казалось, мало дорожил ею, была немыслима. «И к чему ей выходить замуж? – думал он, – наверно, быть несчастной. Вон Лиза за Андреем (лучше мужа теперь, кажется, трудно найти), а разве она довольна своей судьбой? И кто ее возьмет из любви? Дурна, неловка. Возьмут за связи, за богатство. И разве не живут в девках? Еще счастливее!» Так думал, одеваясь, князь Николай Андреевич, а вместе с тем всё откладываемый вопрос требовал немедленного решения. Князь Василий привез своего сына, очевидно, с намерением сделать предложение и, вероятно, нынче или завтра потребует прямого ответа. Имя, положение в свете приличное. «Что ж, я не прочь, – говорил сам себе князь, – но пусть он будет стоить ее. Вот это то мы и посмотрим».
– Это то мы и посмотрим, – проговорил он вслух. – Это то мы и посмотрим.
И он, как всегда, бодрыми шагами вошел в гостиную, быстро окинул глазами всех, заметил и перемену платья маленькой княгини, и ленточку Bourienne, и уродливую прическу княжны Марьи, и улыбки Bourienne и Анатоля, и одиночество своей княжны в общем разговоре. «Убралась, как дура! – подумал он, злобно взглянув на дочь. – Стыда нет: а он ее и знать не хочет!»
Он подошел к князю Василью.
– Ну, здравствуй, здравствуй; рад видеть.
– Для мила дружка семь верст не околица, – заговорил князь Василий, как всегда, быстро, самоуверенно и фамильярно. – Вот мой второй, прошу любить и жаловать.
Князь Николай Андреевич оглядел Анатоля. – Молодец, молодец! – сказал он, – ну, поди поцелуй, – и он подставил ему щеку.
Анатоль поцеловал старика и любопытно и совершенно спокойно смотрел на него, ожидая, скоро ли произойдет от него обещанное отцом чудацкое.
Князь Николай Андреевич сел на свое обычное место в угол дивана, подвинул к себе кресло для князя Василья, указал на него и стал расспрашивать о политических делах и новостях. Он слушал как будто со вниманием рассказ князя Василья, но беспрестанно взглядывал на княжну Марью.
– Так уж из Потсдама пишут? – повторил он последние слова князя Василья и вдруг, встав, подошел к дочери.
– Это ты для гостей так убралась, а? – сказал он. – Хороша, очень хороша. Ты при гостях причесана по новому, а я при гостях тебе говорю, что вперед не смей ты переодеваться без моего спроса.
– Это я, mon pиre, [батюшка,] виновата, – краснея, заступилась маленькая княгиня.
– Вам полная воля с, – сказал князь Николай Андреевич, расшаркиваясь перед невесткой, – а ей уродовать себя нечего – и так дурна.
И он опять сел на место, не обращая более внимания на до слез доведенную дочь.
– Напротив, эта прическа очень идет княжне, – сказал князь Василий.
– Ну, батюшка, молодой князь, как его зовут? – сказал князь Николай Андреевич, обращаясь к Анатолию, – поди сюда, поговорим, познакомимся.
«Вот когда начинается потеха», подумал Анатоль и с улыбкой подсел к старому князю.
– Ну, вот что: вы, мой милый, говорят, за границей воспитывались. Не так, как нас с твоим отцом дьячок грамоте учил. Скажите мне, мой милый, вы теперь служите в конной гвардии? – спросил старик, близко и пристально глядя на Анатоля.
– Нет, я перешел в армию, – отвечал Анатоль, едва удерживаясь от смеха.
– А! хорошее дело. Что ж, хотите, мой милый, послужить царю и отечеству? Время военное. Такому молодцу служить надо, служить надо. Что ж, во фронте?
– Нет, князь. Полк наш выступил. А я числюсь. При чем я числюсь, папа? – обратился Анатоль со смехом к отцу.
– Славно служит, славно. При чем я числюсь! Ха ха ха! – засмеялся князь Николай Андреевич.
И Анатоль засмеялся еще громче. Вдруг князь Николай Андреевич нахмурился.
– Ну, ступай, – сказал он Анатолю.
Анатоль с улыбкой подошел опять к дамам.
– Ведь ты их там за границей воспитывал, князь Василий? А? – обратился старый князь к князю Василью.
– Я делал, что мог; и я вам скажу, что тамошнее воспитание гораздо лучше нашего.
– Да, нынче всё другое, всё по новому. Молодец малый! молодец! Ну, пойдем ко мне.
Он взял князя Василья под руку и повел в кабинет.
Князь Василий, оставшись один на один с князем, тотчас же объявил ему о своем желании и надеждах.
– Что ж ты думаешь, – сердито сказал старый князь, – что я ее держу, не могу расстаться? Вообразят себе! – проговорил он сердито. – Мне хоть завтра! Только скажу тебе, что я своего зятя знать хочу лучше. Ты знаешь мои правила: всё открыто! Я завтра при тебе спрошу: хочет она, тогда пусть он поживет. Пускай поживет, я посмотрю. – Князь фыркнул.
– Пускай выходит, мне всё равно, – закричал он тем пронзительным голосом, которым он кричал при прощаньи с сыном.
– Я вам прямо скажу, – сказал князь Василий тоном хитрого человека, убедившегося в ненужности хитрить перед проницательностью собеседника. – Вы ведь насквозь людей видите. Анатоль не гений, но честный, добрый малый, прекрасный сын и родной.
– Ну, ну, хорошо, увидим.
Как оно всегда бывает для одиноких женщин, долго проживших без мужского общества, при появлении Анатоля все три женщины в доме князя Николая Андреевича одинаково почувствовали, что жизнь их была не жизнью до этого времени. Сила мыслить, чувствовать, наблюдать мгновенно удесятерилась во всех их, и как будто до сих пор происходившая во мраке, их жизнь вдруг осветилась новым, полным значения светом.
Княжна Марья вовсе не думала и не помнила о своем лице и прическе. Красивое, открытое лицо человека, который, может быть, будет ее мужем, поглощало всё ее внимание. Он ей казался добр, храбр, решителен, мужествен и великодушен. Она была убеждена в этом. Тысячи мечтаний о будущей семейной жизни беспрестанно возникали в ее воображении. Она отгоняла и старалась скрыть их.
«Но не слишком ли я холодна с ним? – думала княжна Марья. – Я стараюсь сдерживать себя, потому что в глубине души чувствую себя к нему уже слишком близкою; но ведь он не знает всего того, что я о нем думаю, и может вообразить себе, что он мне неприятен».
И княжна Марья старалась и не умела быть любезной с новым гостем. «La pauvre fille! Elle est diablement laide», [Бедная девушка, она дьявольски дурна собою,] думал про нее Анатоль.
M lle Bourienne, взведенная тоже приездом Анатоля на высокую степень возбуждения, думала в другом роде. Конечно, красивая молодая девушка без определенного положения в свете, без родных и друзей и даже родины не думала посвятить свою жизнь услугам князю Николаю Андреевичу, чтению ему книг и дружбе к княжне Марье. M lle Bourienne давно ждала того русского князя, который сразу сумеет оценить ее превосходство над русскими, дурными, дурно одетыми, неловкими княжнами, влюбится в нее и увезет ее; и вот этот русский князь, наконец, приехал. У m lle Bourienne была история, слышанная ею от тетки, доконченная ею самой, которую она любила повторять в своем воображении. Это была история о том, как соблазненной девушке представлялась ее бедная мать, sa pauvre mere, и упрекала ее за то, что она без брака отдалась мужчине. M lle Bourienne часто трогалась до слез, в воображении своем рассказывая ему , соблазнителю, эту историю. Теперь этот он , настоящий русский князь, явился. Он увезет ее, потом явится ma pauvre mere, и он женится на ней. Так складывалась в голове m lle Bourienne вся ее будущая история, в самое то время как она разговаривала с ним о Париже. Не расчеты руководили m lle Bourienne (она даже ни минуты не обдумывала того, что ей делать), но всё это уже давно было готово в ней и теперь только сгруппировалось около появившегося Анатоля, которому она желала и старалась, как можно больше, нравиться.