Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

* * *

NP-полные задачи

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

В 1900 году Давид Гильберт представил на Международном математическом конгрессе в Париже список задач, которые он считал наиболее важными для математиков XX века. Спустя сто лет Институт Клэя определил список «задач тысячелетия» и назначил премию в миллион долларов за решение каждой из них. Стоит отметить, что этот престижный институт был основан в 1998 году Аэндоном Клэем, известным предпринимателем и любителем математики. Клэй предложил за решение каждой из задач весьма привлекательную сумму, в отличие от Гильберта, который мог предложить тем, кто решит задачи из его списка, разве что вечную славу.

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

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

Немецкий математик Давид Гильберт.

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

Кто назовет 20?

Первый игрок называет одно из двух чисел — 1 или 2. На каждом шаге игроки по очереди прибавляют к результату 1 или 2. Выигрывает тот, кто первым назовет число 20. Существует выигрышная стратегия для этой игры или нет? Что изменится, если вместо 20 для победы нужно будет назвать 83 или 100?

Лабиринт в саду Роуз Болла

Благодаря занимательным задачам У. У. Роуз Болла, популярность получили многие разделы математики. В знаменитом лабиринте Болла стрелками отмечены вход и выход, а точкой — место, где лежат сокровища. Можно ли добраться до них? Попробуйте не подсматривать ответ, а найти решение сами. Получилось? Найденный маршрут будет состоять из линий и точек, обозначающих повороты. Каждое ребро полученного графа нужно пройти дважды (туда и обратно), поэтому все вершины маршрута должны иметь степень 2. Чтобы найти требуемый маршрут, достаточно отмечать коридоры, которые мы уже прошли, чтобы не терять времени понапрасну.

Лабиринт Роуз Болла.

Игра «змейка»

В этой игре, которую придумал Дэвид Сильверман, два игрока по очереди проводят единичные отрезки на сетке размерами 5x5 или 6x6 точек (размер игрового поля может быть произвольным). Отрезки можно добавлять только в начало и конец «змейки». Проигрывает тот, кто вынужден построить цикл. Существует ли выигрышная стратегия для этой игры?

Изящная нумерация графа

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

Ханойские башни

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

Начальное положение колец в игре «Ханойские башни».

Число решений для n колец равно 2 n — 1. С увеличением n число решений стремительно возрастает. Чтобы определить правильную последовательность ходов, можно использовать графы. Интерактивные версии этой игры есть в интернете.

Игра Ним

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

Две цепи Мартина Гарднера

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

Цепь в прямоугольнике

В этом прямоугольнике нужно провести пять линий, соединяющих А и A, В и В, С и С, D и D, E и E , не пересекая отрезки AD и ВС , отмеченные на рисунке, и не выходя за границы прямоугольника.