|
Старая темка, но не важно...
1. Направление развития
Пожалуй, наиболее захватывающей проблемой в математике является задача создание эффективного аппарата «универсального решателя задач». Не менее интересна и важна проблема «постановки» задач.
2. Состояние дел
Состояние дел в этой области неизвестно, т.к. по всей видимости, работы проводятся в секретных правительственных лабораториях (в основном, в США). Есть веские основания считать, что работы также ведутся в «компьютерных» транснациональных корпорациях (тоже, в основном, в США). Ну, и, конечно, этим занимаются любители искусственного интеллекта. Тем не менее, о видимой части этого айсберга я могу рассказать. В основном мои знания касаются задач математического программирования.
3. Класс NP-задач
В данной теме уже обсуждался класс NP-задач. Первоначальная идея создания автоматического решателя широкого класса задач уперлась в огромное количество шагов, которое нужно выполнить для решения задачи. Было установлено, что если научиться «хорошо» решать хотя бы одну задачу из этого класса, то остальные задачи можно свести к этой задаче. Некоторые участники обсуждения совершенно правильно указали на практическую бесполезность данного подхода – универсального алгоритма решения всех задач, по-видимому, нет. Я добавлю еще несколько аргументов к этой критике и опишу, каким образом создаются вполне универсальные решатели.
3.1. «Кодирование»
Представим себе, что в некоторой задаче, признанной NP-полной, 10000 булевых переменных. Специфика задачи такова, что, если зафиксировать некоторые 10 переменных, то получается задача с 9990 булевыми переменными, решаемая за квадратичное время. Здесь «переборная» часть задачи составляет всего 0.1% (10 переменных), а полиномиальная – 99.9%. Если эту задачу свести к другой задаче класса NP, то полиномиальная часть задачи окажется «зашифрованной» алгоритмом преобразования одной задачи к другой. После такого преобразования может оказаться, что окончание времени решения задачи может затянуться до того момента, когда потухнет солнце. Поэтому, за редким исключением, NP-задачи решают в том виде, в котором они возникают на практике и не сводят одну к другой.
3.2. Задачи оптимизации
Еще одна деталь опущена в классификации алгоритмов. На практике многие проблемы преследуют некоторую цель, т.е. являются задачами оптимизации. Получение более точного решения оптимизации связано с материальными затратами (временем, стоимостью оборудования и т.д.). Даже если есть полиномиальный алгоритм решения некоторой задачи, он может оказаться на практике бесполезным. Т.е. «стоимость» решения задачи является неотъемлемой частью при ее постановке. Для NP-класса такой «ничтожной» детали как бы не существует. Вероятно, это случилось из-за того, что задачи «решаются» на машине Тьюринга, а он занимался взломом немецких шифров на флоте во время второй мировой войны. А шифр либо взломан, либо нет.
3.3. Абсурдность классификации алгоритмов
Принадлежность, а тем более доказанность или недоказанность, к классу NP не означает ровным счетом ничего. Как я могу предположить, классификация сложности алгоритмов создавалась с целью получения универсального решателя широкого круга задач. Но эта идея была совершенно опошлена. Некий деятель по имени Джонсон (см. «Вычислительные машины и труднорешаемые задачи») нашел другое применение этой классификации. Он предложил использовать классификацию как метод оправдания для математиков. Якобы, если удастся доказать, что задача относится классу NP, то математик (инженер) при решении практической задачи имеет оправдание, почему он решает задачу плохо (долго и т.д.). В реальности же, важна не столько сама возможность классификация задачи, а знание (или получение/выделение) ее полиномиальной части (см. пример выше), а также снижение степени этого полинома. Поскольку в NP-классификации алгоритмов не важна доля полиномиальной части задачи, то сама классификация давно вступила в противоречие с практикой и здравым смыслом, превратившись в тормоз в развитии математики.
3.4. Неадекватность математических моделей реальности.
В большинстве практических задач имеет место неопределенность. К примеру, в задаче развозки товаров по магазинам (она как бы сводится к задаче о коммивояжере), может возникнуть множество проблем. В современных условиях – это пробки на дорогах, которые могут возникнуть то тут, то там. В реальности нужен не «оптимальный» маршрут, а рекомендации по объезду магазинов. Математически - это функция, которая дает «следующий» магазин в зависимости от конкретной ситуации на дорогах. Поэтому, если вопрос P=NP будет разрешен, благоденствия все равно не наступит.
4. Программирование в ограничениях.
На основе идеи частичной «полиномизации» возникло направление «программирование в ограничениях». Решатели таких систем имеют в своем составе системы перебора (ветвления) и множество алгоритмов, которые за полиномиальное время (и ресурсы) экспоненциально снижают пространство поиска. Задача формулируется в декларативной форме, а система уже самостоятельно подбирает схему ветвления и подходящие алгоритмы сокращения пространства поиска. Для облегчения формулирования задач используют специализированные языки (например, AMPL, коммерческие OPL, Mozec, NP-язык). Исследования в области программирования в ограничениях сосредоточены на увеличении доли полиномиальности для широкого круга задач.
5. Перспективы
Однажды я задался вопросом, а можно ли автоматизировать то, что делается «вручную» математиками в программировании в ограничениях. Для изучения вопроса рассматривал только задачи, которые (хотя бы гипотетически) можно решить перебором. Исходными данными было множество задач. По этим исходным данным нужно было автоматически «подбирать» решатель (алгоритм), с помощью которого эти задачи можно была эффективно решать. Идея состоит в том, что после обучения, решатель можно будет использовать для решения широкого круга проблем. На мой взгляд, это гораздо ближе к жизни, чем потуги по разрешению проблемы (NP=P). Кто пытался исследовать подобные задачи, наверняка знает, что у математики еще все впереди.
Основной акцент в науке в последние десятилетия переместился от физики к «науке о живом»: генетике, эволюции и т.п. Математикам не дурно бы плотно работать со специалистами этих областей. Уверен что новые удивительные математические открытия ждут нас в этой области. В том числе и отгадка природы интеллекта. В общем, ждем новостей от американцев. Надеюсь, это будет не в виде роботов-убийц...
|
) троек натуральных чисел, удовлетворяющих уравнению 
.