Решатель
Решатель — это часть математического программного обеспечения , возможно, в форме автономной компьютерной программы или в виде библиотеки программного обеспечения , которая «решает» математическую задачу. Решатель берет описания задач в некоторой общей форме и вычисляет их решение. В решателе акцент делается на создании программы или библиотеки, которые можно легко применить к другим задачам аналогичного типа.
Типы решателей
Типы проблем, для решения которых существуют специализированные решатели, включают:
- Линейные и нелинейные уравнения . В случае одного уравнения «решатель» правильнее называть алгоритмом нахождения корня .
- Системы линейных уравнений .
- Нелинейные системы .
- Системы полиномиальных уравнений , которые являются частным случаем нелинейных систем, лучше решаются специальными решателями.
- Линейные и нелинейные задачи оптимизации
- Системы обыкновенных дифференциальных уравнений
- Системы дифференциально-алгебраических уравнений
- Проблемы выполнимости булевых уравнений , включая решатели SAT
- Решатели квантифицированных булевых формул [1]
- Проблемы удовлетворения ограничений
- Задачи на кратчайший путь
- Проблемы минимального остовного дерева
- Комбинаторная оптимизация [2]
- Решатели игр для проблем в теории игр [3]
- Задача трех тел [4]
General Problem Solver ( GPS ) — это конкретная компьютерная программа, созданная в 1957 году Гербертом Саймоном , Дж. К. Шоу и Алленом Ньюэллом , которая должна была работать как универсальный решатель проблем, который теоретически может быть использован для решения любой возможной проблемы, которая может быть формализована в символической системе, при условии правильной конфигурации входных данных. Это была первая компьютерная программа, которая отделила свои знания о проблемах (в форме правил домена ) от своей стратегии решения проблем (как общая поисковая система ).
Общие решатели обычно используют архитектуру, похожую на GPS, чтобы отделить определение проблемы от стратегии, используемой для ее решения. Преимущество такого отделения заключается в том, что решатель не зависит от деталей конкретного экземпляра проблемы. Стратегия, используемая общими решателями, была основана на общем алгоритме (обычно основанном на откате назад ) с единственной целью полноты. Это вызывает экспоненциальное время вычислений , которое резко ограничивает их удобство использования. Современные решатели используют более специализированный подход, который использует преимущества структуры проблем, так что решатель тратит как можно меньше времени на откат назад.
Для задач определенного класса (например, систем нелинейных уравнений ) обычно доступны несколько алгоритмов. Некоторые решатели реализуют несколько алгоритмов.
Смотрите также
- Математическое программное обеспечение для других типов математического программного обеспечения.
- Среда решения проблем : специализированное программное обеспечение, объединяющее автоматизированные методы решения проблем с ориентированными на человека инструментами для руководства разрешением проблем.
- Выполнимость по модулю теорий для решателей логических формул относительно комбинаций фоновых теорий, выраженных в классической логике первого порядка с равенством.
- Семантический рассуждающий
Списки решателей
- Список решателей линейного программирования
- Список решателей SMT
- Список решателей для обыкновенных дифференциальных уравнений
Ссылки
- ^ Использование QBF-решателей для решения игр и головоломок — Бостонский колледж
- ^ Чжан, Вэйсюн (2012-12-06). Поиск в пространстве состояний: алгоритмы, сложность, расширения и приложения. Springer Science & Business Media. ISBN 978-1-4612-1538-7.
- ^ Боулинг, Майкл и Мануэла Велосо. Анализ стохастической теории игр для многоагентного обучения с подкреплением. № CMU-CS-00-165. Carnegie-Mellon Univ Pittsburgh Pa School of Computer Science, 2000.
- ^ «Нейронная сеть решает задачу трех тел в 100 миллионов раз быстрее». MIT Technology Review . 26 октября 2019 г. Получено 16 мая 2021 г.
