Некоторое время назад я писал про «Интернациональное программирование на естественных языках», в которой попытался найти достойную цель для абстрактного язык программирования, попробовав примерить на него роль связующего звена между миром программистов с компьютерами и не программистов.

Но в результате оказалось, что решение подобной задачи не требуется в принципе, т. к. для «не программистов» не стоит задача научиться писать программы. А если она и возникает, то вполне хватает обычных формализованных языков программирования, которых уже сейчас насчитывается наверно более десяти тысяч.

Тем не менее, меня не оставляло желание найти для нового языка такую область задач, которая позволила бы ему выделиться из тысячи других языком программирования. И как данный тезис был сформулирован в такой форме (за что большое спасибо комментаторам и самому Хабру), то сразу всплыло воспоминание из юности, когда удалось достать дискету с языком Пролог. Ух, с каким задором горели мои глаза, когда казалось, ну вот, еще чуть-чуть и будет создана система с базой знаний, у которой и можно будет получить заветный ответ 42 на любой вопрос.

Так почему этого так и не случилось? В чем проблема Пролога, да и любой системы / языка программирования, назначение которых анализировать факты и искать ответы на вопросы? Эта проблема называется «Комбинаторный взрыв» — экспоненциальная зависимость времени работы алгоритма от количества входных данных.

Подходы к написания программ

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

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

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

Именно к декларативному стилю относится язык Пролог, да и все остальные логические языки программирования. К декларативному стилю написания программ относится и язык структурированных запросов (SQL).

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

Другое дело, программирование в декларативном стиле. Программист хоть и может указать ограничения, которые следует применять при поиске решения, но это возможно только в том случае, когда известен алгоритм решения задачи. Но если известен алгоритм решения, то проще использовать императивный стиль, реализуя этот алгоритм!

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

Именно в этом случае и начинается экспоненциальный рост времени выполнения алгоритма. Начиная с определенного порога, время ожидания становится неприемлемым для реального использования. А термин «Комбинаторный взрыв» используется для описания эффекта от резкого («взрывного») роста времени выполнения алгоритма при увеличении размера входных данных.

Проблема поиска решений

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

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

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

Масштабирование производительности

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

Другое дело горизонтальное масштабирование, при котором выполнение алгоритма запускается на отдельных узлах, которые параллельно выполняют одну и ту же задачу. Такой способ масштабирования уже позволяет значительно сократить время получения итогового результата для сложных вычислительных задач. И хотя данный способ является решением «в лоб», но успехи в области data science доказывают успешность такого подхода.

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

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

Поиск обобщенного решения

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

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

Это возможно как алгоритмическими методами (откат и отсечение в Прологе), так и с применением машинного обучения для поиска различных закономерностей.

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

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

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

Область не решаемых задач