... американский офисный кролик понравился:) что будет, если соединить его и ... Андриано Челентано
перехдим в офис, так в офис. Итак:
Рассказ 5-й. Три задачи
Задача первая, совершенно канцелярская (из жизни нашего издательства)
Случайно перевернули ящик с авторскими договорами. Теперь надо их поставить обратно в ящик в алфавитном порядке фамилий. Чтобы почувствовать всю прелесть задачи, рекомендую Вам рассыпать какую-нибудь картотеку у себя на работе или в другом оффисе.
Казалось бы, чего тут сложного, группируй в кучки ... но как? «Вставляй в середину правильным образом». Это хороший метод, и он даже имеет название «сортировка включением». Но при этом приходится пролистывать стопочки, которые уже уложены. Не так-то легко решать задачу сортировки, хотя это и не безнадёжно трудно. Вполне по силам.
Теперь как проверить, что карточки рассортированы правильно?
Можно делать так: брать от начала к концу по две и проверять, правильно ли, что вторая стоит дальше первой (сравнивая каждые две подряд идущие). Если карточек 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) – это гипотеза, которая в математике не опровергнута и не доказана.
Мы можем почувствовать, что есть задачи принципиально разной сложности.
Возможно, есть неразрешимые даже для машин.
Возможно, простых задач нет.
Задача третья, охотничья
Допустим, охотник идёт по лесу и видит мелькнувшую впереди большую жёлтую кошку. Он стреляет в кошку.
Таки это и была кошка. В окрестностях села встречается хозяин кошки, который ломает ружьё и самого охотника об дерево.
Допустим, охотник идёт по лесу и видит быстро мелькнувшую кошку. Он полагает, что это и есть кошка, тем более, что до села недалеко. Теряет бдительность, и через полчаса становится добычей рыси, которая прыгает ему на плечи с ветки. Рысь то была…
Рысь лишь немногим больше хорошего кота. Что до кисточек, то их ещё надо разглядеть (если они вообще там есть). В рыси есть: усы, цвет=жёлтый, форма=кошка.форма и пр. ( вспомним рассказ про фреймовое представление знаний)
Допустим, Вы идёте по Москве, вдобавок без документов, и в конце квартала видите двоих мужчин с кучерявыми движениями, и один подносит к лицу не то рацию не то большой мобильник. Вы человек нервный, и прижимаетесь к стене. Те тоже нервные - они разворачиваются и убегают. Ни они, ни Вы и не милиционеры и не бандиты.
Всё это ошибки распознавания.
Рассмотрим эту задачу.
Назовём графом набор узлов, связанных линиями. Удобно представлять узлы в виде шариков различного размера и цвета. Связи – в виде цветных верёвочек. Связи показывают ОТНОШЕНИЯ между компонентами понятия, например, если на голове есть фуражка, то от головы идёт линия к фуражке. От человека – к мобильнику (коммуникатору). В узлах хранятся, например, числовые характеристики (размер коммуникатора= большой, маленький).
Предположим, что есть два графа, узлы и верёвочки которых перепутали, и в таком виде обе сети бросили на пол. Как узнать, одинаковые ли это графы?
Или хоть в каком-нибудь смысле похожие?
Задача установления изоморфима графов является NP-сложной.
То есть В ПРИНЦИПЕ, даже имея как угодно мощный компьютер, графы можно сравнить лишь приблизительно.
И если наши понятия о предметах представимы в виде графов (а фреймовые - представимы), тогда мы эти предметы даже толком сравнить не можем.
Идентифицировать (распознать) не можем.
Такие ситуации Вам знакомы. Иногда мы распознаём ситуацию с точностью до имеющегося у нас в понятиях фрейма (внешнй облик, одежда). Образ врага по одежде и речи. Что внутри фрейма (экземпляра врага), на разбор этого у нас не хватает времени… Действительно, иногда похоже, что сознание орудует фреймами и графами. Тогда не удивительно, что мы так глупы.
Это вовсе не разум слаб, это задачи сложны.
А если совершенство разума всё-таки возможно? Гипотеза (2) не опровергнута. Вдруг в мире фреймов(подграфов) и графов есть быстрые алгоритмы сравнения, только им надо научиться?
Вдруг марсиане что-то такое умеют?
Вдруг в наших понятиях вмещаются не все вообще графы, а только такие, с которыми возможно быстро работать?
Так думали математики некоторое время, пока не узнали, какие на самом деле и как мы решаем задачи. Об этом в следующих рассказах.