Вычислительные машины и труднорешаемые задачи

Лекция 10. Вычислительные машины и труднорешаемые задачи

Я назвал эту лекцию точно также, как и одну из немногих книг, посвященную этой сложной проблеме. Книга была издана на русском языке в 1982 году в издательстве Мир очень ограниченным тиражом - всего 8000 экземпляров. Неудивительно. что она сразу же стала библиографической ценностью. Это книга Майкла Гэри и Давида Джонсона “Вычислительные машины и труднорешаемые задачи”.

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

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

Примечание 1. “Брандашмыг” - фантастический образ в сказке Льюиса Кэррола “Алиса в “Зазеркалье”. Это слово точного смысла не имеет. Как сказала сама Алиса, “такие слова наводят на всякие мысли, хотя и неясно - на какие”.

Естественно, что Вы с энтузиазмом бросаетесь на выполнение. Но через непродолжительное время ваш энтузиазм идет на убыль, так как ничего лучше полного перебора вариантов при анализе “брандашмыгов” в голову не приходит. Подобный подход потребует несколько лет машинного времени, так как набор характеристик весьма велик. Трудно ждать премии, а тем более повышения за такое решение поставленной проблемы. Скорее можно расстаться с хорошо оплачиваемой работой в хорошей фирме. Что делать?

Можно прийти к шефу и сказать “Я не смог справиться с этим заданием. Наверное, я слишком туп”.

Реакция шефа легко предсказуема.

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

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

С помощью упомянутой книги у Вас появляется возможность найти достойный выход из трудного положения. Можно попытаться доказать NP- полноту задачи о “брандашмыгах” и таким образом установить ее эквивалентность всем другим трудным задачам этого класса. Тогда можно прийти к шефу и доложить:

“Я не смог найти эффективный алгоритм решения задачи, но этого не смог сделать и никто из известных математиков”

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

Примечание 2. Гильберт Давид (1862 – 1943) - известный немецкий математик. В 1900 году  сформулировал проблемы, разработка которых в значительной мере предопределила развитие математики в 20 веке. К настоящему моменту ряд “проблем Гильберта” решен, для некоторых доказана невозможность решения, а некоторые еще ждут ответа.

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

Терминология.

Для начала давайте договоримся о терминологии. Поскольку в дальнейшем мы будем оперировать такими терминами