OberonCore
https://forum.oberoncore.ru/

Алгоритм упрощения математических выражений
https://forum.oberoncore.ru/viewtopic.php?f=27&t=5327
Страница 1 из 1

Автор:  Rifat [ Воскресенье, 18 Январь, 2015 18:29 ]
Заголовок сообщения:  Алгоритм упрощения математических выражений

Например, требуется упростить,
2*x*3*(y+1) - 6*x
до
6*x*y
В принципе запрограммировать данное упрощение можно, но при этом не совсем понятно какие структуры данных и алгоритмы лучше для этого использовать.

Может быть кто-нибудь читал какую-нибудь статью или книгу, где описывается подобный алгоритм и детально описываются применяемые структуры данных?

Автор:  Борис Рюмшин [ Воскресенье, 18 Январь, 2015 19:02 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Символьные вычисления это. https://ru.wikipedia.org/wiki/%D0%A1%D0 ... 0%B8%D1%8F

Литературу не посоветую, но область этих алгоритмов уже хорошо обкатана в коммерческих (Maple, Mathematica и т.п.) и некоммерческих (Maxima) продуктах. А кое-кто и сам такие алгоритмы программирует...

Автор:  Alexey_Donskoy [ Воскресенье, 18 Январь, 2015 19:49 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Rifat писал(а):
не совсем понятно какие структуры данных и алгоритмы лучше для этого использовать.
Литературу не посоветую.
Сам делал, представляя формулу в виде дерева.
Ключевые процедуры:
- определение эквивалентности веток (рекурсивная функция с перебором порядка следования подветок в узлах);
- приведение констант (отлавливаются случаи умножения на 1 и на 0, например, а также деление и вычитание одинаковых веток;
- вынесение общего множителя за скобку;
- раскрытие скобок;
- прочая специфика (тригонометрические преобразования в моём случае).

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

Автор:  Info21 [ Воскресенье, 18 Январь, 2015 22:33 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

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

Автор:  Rifat [ Воскресенье, 18 Январь, 2015 22:39 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

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

Автор:  Alexey_Donskoy [ Понедельник, 19 Январь, 2015 01:07 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Rifat писал(а):
При программировании же этих алгоритмов возникает много вопросов, как лучше организовать структуру данных, как производить поиск совпадающего многочлена, например.
Задавайте конкретные вопросы, отвечу.

Про многочлен. На уровне верхнего узла это есть сумма слагаемых.
Сначала сравниваем количество слагаемых. Если одинаково, то рекурсивно сравниваем слагаемые (с перебором разного порядка следования слагаемых).

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

Автор:  Rifat [ Среда, 21 Январь, 2015 17:53 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Поискал в интернете по поводу упрощения выражений. Вообще, общий алгоритм для упрощения относится к term rewriting system, но детальное описание со структурами данных я не нашел. Во многих случаях для term rewriting используются функциональные языки, типа Lisp, видимо там это делается достоточно просто.
А так похоже надо будет реализовывать Ad hoc алгоритм.

Автор:  Rifat [ Четверг, 13 Июль, 2017 15:23 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Много времени прошло со времени начального поста. Снова занялся той идеей.
И сформулировал требования к структуре данных, которую хочу реализовать:
1. Выражение должно представляться в виде дерева, но не бинарного. Например, если складываются несколько переменных, то должна быть одна вершина "сложение" и список переменных, которые складываются.
2. При печати дерева, выражение должно печататься в том же виде, как оно было введено пользователем. А внутри дерево может быть организовано, как будет удобнее.
3. Определение одинаковых подвыражений должно быть очень дешево.
4. Должна сохраняться версионность изменений, чтобы можно было посмотреть как выражение выглядело на каждом этапе.

Автор:  Valery Solovey [ Пятница, 14 Июль, 2017 01:22 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

А в чём польза от недвоичного дерева?

Автор:  Rifat [ Пятница, 14 Июль, 2017 09:37 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Допустим, нужно вычислить предикат x + y + z = z + y + x. Если у недвоичного дерева в вершине сложения будут перечислены: x, y, z, а у другой вершины z, y, x, то будет проще их привести к одинаковому виду, отсортировав имена переменных лексикографически. И сразу будет видно, что подвыражения одинаковые, и соответственно предикат TRUE.
Если же, представлять выражение в виде двоичного дерева, то приведение к одинаковому виду будет сложнее, так как нужно будет переставлять местами переменные из разных вершин. К тому же, структура двоичного дерева может отличаться, например, одно поддерево будет выглядеть как (x + y) + z, а другое как x + (y + z). И определение одинаковости этих подвыражений будет затруднено.

Автор:  Илья Ермаков [ Пятница, 14 Июль, 2017 13:07 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

А почему бинарное дерево обсуждается как "естественное", а другие - "экстравагантные"?

Как раз естественно сразу считать узел n-арным оператором.

Автор:  Valery Solovey [ Суббота, 15 Июль, 2017 16:22 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Rifat писал(а):
Допустим, нужно вычислить предикат x + y + z = z + y + x. Если у недвоичного дерева в вершине сложения будут перечислены: x, y, z, а у другой вершины z, y, x, то будет проще их привести к одинаковому виду, отсортировав имена переменных лексикографически.
Выглядит надуманным. Польза минимальна, и работает это только со скалярными x, y и z. С другой же стороны, анализ поддерева, у которого всего две ветви, кажется более простым. Да и операция сложения, вообще-то, двухместная. А возможность перемены мест слагаемых - это правило, которое навешивается сверху на формулу целиком (или на двоичное дерево).

Автор:  Rifat [ Суббота, 15 Июль, 2017 18:18 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

Спор по поводу бинарное или не бинарное дерево не так важен пока.
Сейчас думаю над тем как определить, что (x=y) & (y = z) & not (x = z) всегда False.
Кто как думает какой алгоритм и структуры данных нужны для этого.

Автор:  PSV100 [ Вторник, 25 Июль, 2017 19:40 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

В качестве отправной точки можно взглянуть на изложения Поспелова (Поспелов Д.А. Ситуационное управление. Теория и практика. - 1986):
http://raai.org/about/persons/pospelov/ ... pravl.djvu

гл. 5.2, стр. 223 -- насчёт программы "логик-теоретик" (не помню всего, но у автора проблематика логики размазана по всей книге, поэтому м.б. есть и ещё чего-то такого).

Автор:  Rifat [ Пятница, 28 Июль, 2017 13:27 ]
Заголовок сообщения:  Re: Алгоритм упрощения математических выражений

В статье на Хабрахабре описаны некоторые приёмы упрощения, там же, кстати, есть ответ почему n-арное сложение лучше бинарного: https://habrahabr.ru/post/150043/#simplification

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/