Введение в нейронные сети. 7 рассказов о математике

Александр Титов (С.-Петербург)

Рассказ 5-й. Три задачи

Задача первая, совершенно канцелярская (из жизни издательства)

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

Казалось бы, чего тут сложного, группируй в кучки… но как?

Paper stack

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

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

Теперь как проверить, что карточки рассортированы правильно?

Можно делать так: брать от начала к концу по две и проверять, правильно ли, что вторая стоит дальше первой (сравнивая каждые две подряд идущие). Если карточек N, то придется сделать N сравнений (и по N операций доставания пары карточек и закладки их обратно). То есть всего придется сделать что-то около 2*N на доставание да 2*N на возврат обратно да N сравнений, всего 5*N операций. И насколько же это легче, чем сортировать!!! Знай себе перебирай карточки да смотри на каждые две под пальцами. Пролистал, и готово.

Математики говорят, что трудоемкость этой проверки О(N) операций. То есть операций нужно примерно N (множитель 5 несущественен. Ну, может, 4 или 6. Считается, что на трудоемкость это не сильно влияет)

Но раз так легко проверить, почему не так легко сделать?

Решить задачу сортировки действительно труднее, чем проверить решение. Плохие алгоритмы сортировки имеют сложность О(N в квадрате). Пишем O(N**2). Здесь «**» — обозначение степени. 2**3=2*2*2=8

То есть если вы опрометчиво рассыпали не 20, а сотни две карточек, то для укладки их обратно вам придется сделать 200**2=200*200=40 000 операций. Это будут операции подхода к кучке, просмотра каждой карточки в той кучке, куда вставлять, сравнения с той, что в руках и т.п. Простые операции, но их 40 тысяч.

Лучшие известные алгоритмы сортировки имеют трудоемкость O(N *logN). Это при больших N куда меньше, чем N**2, но куда больше, чем просто N… Логарифм по какому именно основанию, это для оценки трудоемкости считается несущественным.

Задача вторая, «экономическая»

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

Начнем с более простого, а именно: как проверить полученное решение. Допустим, что решения лежат где-то в куче, и на каждом написана его длина пути. Берем первое и кладем посреди комнаты. Берем следующее и смотрим: если оно длиннее, чем то, выбрасываем его. А если очередное выбранное из кучи короче того, что посреди комнаты, тогда кладем его в середину, а то выбрасываем. Это – алгоритм поиска наименьшего, он имеет трудоемкость O(N)! Но мы забыли, что еще нужно было проверять правильность пути в каждом варианте! То есть проверять тот факт, что коммивояжер на данном пути не схалтурил, был в каждом городе. И только по одному разу. Наверно, теперь труднее, чем O(N)…

Можно доказать, что трудоемкость ПРОВЕРКИ задачи коммивояжера (К) такая же, как у РЕШЕНИЯ, но задачи сортировки.

А вот какая же тогда трудоемкость решения задачи К?

Трудоемкость куда больше, чем O(N**2) и даже больше, чем O(N**M), где M-любая константа. Такие задачи историк математики Б.В Бирюков назвал NP-сложными (НеПолиномиально сложными). Похожий распространенный термин: NP-полная задача (NP-complete).

Итак, для решения задачи обхода 20 городов может понадобиться куда больше, чем 20**4= 20*20*20*20=160000 операций… Конечно, если повезет, и будет какая-нибудь очень легкая комбинация городов (например — много расположены в ряд), то меньше. А в общем случае без компьютера точно не обойтись.

А при больших N и компьютер не поможет.

Задача К имеет трудоемкость O(M**N). Чему равно M, несущественно. Все равно это такие большие числа… Пусть 100 городов, тогда пусть 2*100, это сколько будет?…

Сегодня не умеем решать задачу К.

Ничем. Ни мозгами, на компьютерами…. С увеличением N трудоемкость растет слишком быстро. Не хватит всех компьютеров галактики.

Задача же сортировки P-сложная (полиномиально-сложная)(принципиально проще).

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

(1) Если решение задачи проверить просто, это была трудная (но решаемая) задача

Если решение задачи очевидно, то это была простая задача

Уж если и решение задачи проверить трудно, то это была совсем неподъемная задача.

(2) Голос оптимиста: если уж возможна P-сложная проверка, то и сама задача была не более чем P-сложная. Это голос вредных преподов: «Мы же тут за пивком их контрольные проверяем, так значит, они там за пивком вполне могут их решать». По этому мнению, сложность проверки и решения принципиально одинаковы. И тогда задача К на самом-то деле тоже всего лишь P-сложная (как и сортировка), но мы просто еще не знаем этого алгоритма, а знаем только NP-сложные алгоритмы.

Для отдыха: является ли (2) отрицанием (1)?

Предположение вредных преподов (2) – это гипотеза, которая в математике не опровергнута и не доказана.

Мы можем почувствовать, что есть задачи принципиально разной сложности.

Возможно, есть неразрешимые даже для машин.

Возможно, простых задач нет.

Задача третья, охотничья

Допустим, охотник идет по лесу и видит мелькнувшую впереди большую желтую кошку. Он стреляет в кошку.

Таки это и была кошка…

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

Whiskers

Рысь лишь немногим больше хорошего кота. Что до кисточек, то их еще надо разглядеть (если они вообще там есть). В рыси есть: усы, цвет=желтый, форма=кошка.форма и пр. (вспомним рассказ про фреймовое представление знаний)

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

Все это ошибки распознавания.

Рассмотрим эту задачу.

Назовем графом набор узлов, связанных линиями. Удобно представлять узлы в виде шариков различного размера и цвета. Связи – в виде цветных веревочек. Связи показывают ОТНОШЕНИЯ между компонентами понятия, например, если на голове есть фуражка, то от головы идет линия к фуражке. От человека – к мобильнику (коммуникатору). В узлах хранятся, например, числовые характеристики (размер коммуникатора=большой, маленький).

Предположим, что есть два графа, узлы и веревочки которых перепутали, и в таком виде обе сети бросили на пол. Как узнать, одинаковые ли это графы? Или хоть в каком-нибудь смысле похожие?

Оказывается, задача установления изоморфизма графов является NP-сложной.

То есть, В ПРИНЦИПЕ, даже имея как угодно мощный компьютер, графы можно сравнить лишь приблизительно.

И если наши понятия о предметах представимы в виде графов (а фреймовые — представимы), тогда мы эти предметы даже толком сравнить не можем. Идентифицировать (распознать) не можем.

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

Это вовсе не разум слаб, это задачи сложны.

А если совершенство разума все-таки возможно? Гипотеза (2) не опровергнута. Вдруг в мире фреймов (подграфов) и графов есть быстрые алгоритмы сравнения, только им надо научиться?

Вдруг марсиане что-то такое умеют?

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

Так думали математики некоторое время, пока не узнали, какие на самом деле и как мы решаем задачи. Об этом в следующих рассказах.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>