Решатель

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

Типы решателей

Типы проблем с существующими специализированными решателями включают в себя:

Линейные и нелинейные уравнения . В случае одного уравнения «решатель» правильнее называть алгоритмом поиска корня .
Системы линейных уравнений .
Нелинейные системы .
Системы полиномиальных уравнений , которые являются частным случаем нелинейных систем, лучше решаются специальными решателями.
линейной и нелинейной оптимизации Задачи
Системы обыкновенных дифференциальных уравнений
Системы дифференциально-алгебраических уравнений
Проблемы логической выполнимости , включая решатели SAT
количественных логических формул Решатели ^[1]
Проблемы удовлетворения ограничений
Проблемы кратчайшего пути
с минимальным связующим деревом Проблемы
Комбинаторная оптимизация ^[2]
Решатели задач по теории игр ^[3]
Задача трех тел ^[4]

General Issue Solver ( GPS ) — это особая компьютерная программа, созданная в 1957 году Гербертом Саймоном , Дж. К. Шоу и Алленом Ньюэллом и предназначенная для работы в качестве универсального средства решения проблем, которое теоретически можно использовать для решения любой возможной проблемы, которая может быть формализована в виде символическую систему при правильной входной конфигурации. Это была первая компьютерная программа, которая отделила знание проблем (в форме правил предметной области ) от стратегии решения проблем (в качестве общей поисковой системы ).

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

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

См. также

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

Списки решателей

Ссылки

^ Использование решателей QBF для решения игр и головоломок - Бостонский колледж
^ Чжан, Вэйсюн (6 декабря 2012 г.). Поиск в пространстве состояний: алгоритмы, сложность, расширения и приложения . Springer Science & Business Media. ISBN 978-1-4612-1538-7 .
^ Боулинг, Майкл и Мануэла Велосо. Анализ стохастической теории игр для многоагентного обучения с подкреплением . № КМУ-КС-00-165. Школа компьютерных наук Университета Карнеги-Меллона, Питтсбург, Пенсильвания, 2000.
^ «Нейронная сеть решает задачу трёх тел в 100 миллионов раз быстрее» . Обзор технологий Массачусетского технологического института . 26 октября 2019 г. Проверено 16 мая 2021 г.

[1] Использование решателей QBF для решения игр и головоломок - Бостонский колледж

[2] Чжан, Вэйсюн (6 декабря 2012 г.). Поиск в пространстве состояний: алгоритмы, сложность, расширения и приложения . Springer Science & Business Media. ISBN 978-1-4612-1538-7 .

[3] Боулинг, Майкл и Мануэла Велосо. Анализ стохастической теории игр для многоагентного обучения с подкреплением . № КМУ-КС-00-165. Школа компьютерных наук Университета Карнеги-Меллона, Питтсбург, Пенсильвания, 2000.

[4] «Нейронная сеть решает задачу трёх тел в 100 миллионов раз быстрее» . Обзор технологий Массачусетского технологического института . 26 октября 2019 г. Проверено 16 мая 2021 г.

[1]

[2]

[3]

[4]