Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений
В данній роботі розглядаються методи оптимізації деяких алгоритмів розв`язання систем лінейних діофантових рівнянь за допомогою булевих перетворень. Наведені оптимізації використовуються при реалізації алгоритмів на програмній мові та зменшують у загальному випадку час роботи алгоритму на порядок...
Gespeichert in:
| Datum: | 2004 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут програмних систем НАН України
2004
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/2284 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений / М.В.Лопатина // Проблеми програмування. — 2004. — N 2,3. — С. 118-121. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-2284 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-22842025-02-09T14:26:30Z Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений Лопатина, М.В. Формальные методы в программировании В данній роботі розглядаються методи оптимізації деяких алгоритмів розв`язання систем лінейних діофантових рівнянь за допомогою булевих перетворень. Наведені оптимізації використовуються при реалізації алгоритмів на програмній мові та зменшують у загальному випадку час роботи алгоритму на порядок порівняно з іншими реалізаціями. The given work presents methods of optimization of the algorithms for resolving the systems of linear Diophantine equations via boolean operations. These optimizations are applied through implementation of these algorithms into program code and reduce average time of algorithms’ work in 10 times comparing to the existing implementations of these algorithms. 2004 Article Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений / М.В.Лопатина // Проблеми програмування. — 2004. — N 2,3. — С. 118-121. — Бібліогр.: 4 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/2284 51.681.3 ru application/pdf Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Формальные методы в программировании Формальные методы в программировании |
| spellingShingle |
Формальные методы в программировании Формальные методы в программировании Лопатина, М.В. Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| description |
В данній роботі розглядаються методи оптимізації деяких алгоритмів розв`язання систем лінейних діофантових рівнянь за
допомогою булевих перетворень. Наведені оптимізації використовуються при реалізації алгоритмів на програмній мові та
зменшують у загальному випадку час роботи алгоритму на порядок порівняно з іншими реалізаціями. |
| format |
Article |
| author |
Лопатина, М.В. |
| author_facet |
Лопатина, М.В. |
| author_sort |
Лопатина, М.В. |
| title |
Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| title_short |
Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| title_full |
Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| title_fullStr |
Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| title_full_unstemmed |
Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| title_sort |
булева оптимизация алгоритмов решения систем линейных диофантовых уравнений |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2004 |
| topic_facet |
Формальные методы в программировании |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/2284 |
| citation_txt |
Булева оптимизация алгоритмов решения систем линейных диофантовых уравнений / М.В.Лопатина // Проблеми програмування. — 2004. — N 2,3. — С. 118-121. — Бібліогр.: 4 назв. — рос. |
| work_keys_str_mv |
AT lopatinamv bulevaoptimizaciâalgoritmovrešeniâsistemlinejnyhdiofantovyhuravnenij |
| first_indexed |
2025-11-26T20:47:05Z |
| last_indexed |
2025-11-26T20:47:05Z |
| _version_ |
1849887333706366976 |
| fulltext |
БУЛЕВА ОПТИМИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ СИСТЕМ
ЛИНЕЙНЫХ ДИОФАНТОВЫХ УРАВНЕНИЙ
Лопатина М.В.
Институт Кибернетики НАН Украины,
03187, Киев, просп. Глушкова, 40, тел. 253-02-69, marichkay@mail.ru
Анотація
В данній роботі розглядаються методи оптимізації деяких алгоритмів розв`язання систем лінейних діофантових рівнянь за
допомогою булевих перетворень. Наведені оптимізації використовуються при реалізації алгоритмів на програмній мові та
зменшують у загальному випадку час роботи алгоритму на порядок порівняно з іншими реалізаціями.
Abstract
The given work presents methods of optimization of the algorithms for resolving the systems of linear Diophantine equations via
boolean operations. These optimizations are applied through implementation of these algorithms into program code and reduce average time
of algorithms’ work in 10 times comparing to the existing implementations of these algorithms.
Введение
Системы линейных диофантовых уравнений и методы их решения играют важную роль во многих
разделах современной науки о вычислениях, поскольку многие задачи из этих разделов сводятся к решению
линейных констрейнтов или проверки совместности (выполнимости) таких систем над множеством целых или
натуральных чисел или над конечными целочисленными областями - такие констрейнты называются
диофантовыми.
Среди разделов, которые активно используют диофантовые констрейнты, следует выделить сети Петри.
В сетях Петри системы линейных диофантовых уравнений используются для решения уравнения состояния и
получения S- и T-инвариант, которые являются материалом для анализа статических свойств модели. Кроме
того, решение диофантовых констрейнтов на множестве {0,1} позволяет определить множества мест в сети
Петри, являющихся дедлоком или ловушкой.
Поскольку в подобных задачах количество неизвестных в констрейнте может быть достаточно велико, в
данной статье представлены некоторые методы оптимизации по скорости известных автоматизированных
алгоритмов нахождения минимального порождающего множества решении для диофантовых констрейнтов с
помощью булевых преобразований.
Необходимые сведения
Системой линейных диофантовых уравнений (СЛДУ) называется система вида:
=++
=++
=++
=
pqpq
qq
qq
bxaxa
bxaxa
bxaxa
S
...
...
...
121
22121
11111
LLLLL
(1)
где Zbaij ∈, (кольцо целых чисел), Nx j ∈ (множество натуральных чисел) и qjpi ,,2,1,,,2,1 KK == .
Вектора )1,0,,0,0(,),0,0,,1,0(),0,0,0,1( 21 KKKK === qeee - единичные вектора из множества qN ,
называются векторами канонического базиса множества qN . Вектор ),,( 1 qccc K= , где
qiNci ,,2,1, K=∈ , называется решение системы (1), если выполняется формула:
iqiqi bxaxapi ≡+∈∀ K11],1[
где ≡ означает отношение тождества. СЛДУ называется системой линейных однородных диофантовых
уравнений (СЛОДУ), если ( ],1[ pi ∈∀ ) 0=ib . Заметим, что СЛОДУ всегда имеет решение вида )0,,0,0( K ,
которое называется нулевым или тривиальным. Всякое решение СЛОДУ отличное от нулевого, называется
нетривиальным. СЛОДУ называется совместной, если она имеет хотя бы одно нетривиальное решение. Введем
на множестве qN отношение порядка ≤ : если q
qq Nyyyxxx ∈== ),,(),,,( 11 KK , то yx ≤ тогда и
только тогда, когда для всех ii yxqi ≤= ,,1K . Нетрудно убедится в том что это отношение является
частичным порядком и относительно этого порядка можно говорить о минимальных элементах в множестве
qN ю Известно, что множество всех решений СЛОДУ имеет конечный базис и базис этого множества
составляют минимальные решения СЛОДУ относительно введенного частичного порядка.
TSS алгоритм и его реализация
В работе [1,2] подробно описан алгоритм построения множества '
jM , которое является усеченным
множеством решений или TSS (от английского Truncated Set of Solutions) системы
0)(&...&0)(&0)(' 21 ==== xLxLxLS j или системы вида (1), решение которой сводится к решению
системы 'S .
Однако непосредственное применение такого алгоритма построения TSS порождает избыточные
решения, когда решение '\ jj MMx∈ (где },,{ ''
1
'
lj eeM K= - TSS системы 'S , а jM - множество всех ее
решений ) может быть представлено в виде неотрицательной линейной комбинации других решений множества
'
jM вида:
где
.,,1,,0,, liM'ekNbk jji K=∈′≠∈
Исключение избыточных решений из TSS базируется на следующем утверждении [1]:
Свойство Минимальности Пусть 'S - СЛОДУ и '
pM - ее TSS, состоящее из k элементов. Тогда любой
вектор x их pM' такой, что { } NtkixM'etx pi ∈−=∈>> ,1,2,1,\ K и ,0≠t имеет представление вида:
112211 −−+++= kk ebebebmx K ,
где NbmNm i ∈≠∈ ,0,
Из свойства минимальности вытекает следующая процедура очистки TSS: вектор x удаляется из TSS,
если x больше или его произведение txбольше некоторого из оставшихся векторов TSS. В качестве множителя
t можно взять, в частности, максимальную координату векторов из текущего TSS - после такой чистки
получаем минимальное порождающее множество решений СЛОДУ.
Исходя из алгоритма, для того чтобы выполнить очистку TSS необходимо сравнить каждое решение с
кажным, причем очистку необходимо выполнять после каждой итерации (построения TSS с учетом
следующего уравнения системы). Причем количество решений в TSS в общем случае может расти
экспоненциально в зависимости от количества переменных в системе.
Далее предлагается идея и особенности реализации выполнения операции сравнения векторов TSS,
оптимизированной по памяти и времени.
Идея
Каждому вектору решения ),( 1 qxxx K= ставится в соответствие двоичный вектор ),( ''
1
'
qxxx K= ,
где q - количество неизвестных, построенный по следующему правилу:
>
=
=
0,1
0,0'
i
i
i x
x
x , где qi K,2,1=
Далее сравнения двух векторов решений выполняется не по исходным векторам значений, а по их двоичным
представлениям относительно отношения частичного порядка на множестве qN :
- если соответствующие двоичные вектора являются сравнимыми между собой, это значит, что одно из
исходных решений x или его произведение tx больше другого решения – а значит, является избыточным.
- если соответствующие двоичные вектора не являются сравнимыми, это значит, что и исходные решения не
являются сравнимыми и не попадают под правило очистки.
Пример 1
Рассмотрим, как выполняется сравнение двух векторов решений.
Пусть есть два вектора решений 1x и 2x , 4=q , поставим им в соответствие двоичные вектора по указанному
правилу:
)1,1,0,1()15,5,0,2(
)1,0,0,1()10,0,0,9(
'
22
'
11
=⇒=
=⇒=
xx
xx
,''
1 1' ll ebebkx =+= K
Очевидно, что вектор '
1x и вектор '
2x являются сравнимыми и '
1
'
2 xx > . Это значит, что произведение
2tx больше решения 1x . В качестве t можно выбрать максимальную координату вектора 1x , тогда
122 )10,0,0,9()150,50,0,20(10 xxtx =>=⋅=
От сюда следует, что решение 2x является избыточным.
Реализация
Основной целью при реализации представленного алгоритма сравнения векторов решений, является
оптимизация этой операции по времени. Исходя из этого предлагается:
Структура данных:
Для хранения двоичного представления вектора решения ),( ''
1
'
qxxx K= - массив ),( ''''
1
''
kxxx K= ,
каждый элемент которого будет представлять десятичное значение двоичной последовательности
определенной длины двоичного вектора 'x .
При программировании элементом массива будет являтся пременная, некоторого стандартного типа (в
С++ это может быть, например, тип “byte”, “short int”, “long”), который определяет количество бит которые
будут резервироваться в памяти под переменную этого типа - 8, 16, 32, а значит дину двочной
последовательности, которая может буть представлена десятичным числом в переменной соответствующего
типа, то есть
),( ''
1
''
liij xxDECIMALx ++= K ,
где l
l
q
kkj ;1
1
;,,1 +
−== K - количество бит выделяемых под переменную типа выбранного для
реализации; DECIMAL - функция перевода двоичного значения в десятичное; ''
1, lii xx ++ K - j -тая
последовательность l элементов двоичного представления вектора решения 'x .
Полученный массив ''x будет занимать в памяти в общем случае в l раз меньше места, чем при хранении в
массиве двоичного представления поэлементно. К тому же, чем больше l , тем меньше времени занимает
операция сравнения векторов.
Операция сравнения
Сравнение векторов программируется с использование логическую операцию “И”, которая является
базовой машинной операцией и выполняется за один такт над переменными стандартных типов, где операция
“И” над векторами это:
∧
∧
=∧
''
2
''
1
''
21
''
11
''
2
''
1
kk xx
xx
xx LLL
Отсюда сравнение двух веторов решения сводится к проверке условия:
)()( ''
2
''
1
''
2
''
1 xxxx ∧==∨
- если условия выполняется, то вектора являются сравнимыми и результирующий вектор ''
2
''
1 xx ∧ указывает на
меньший из них, то есть соответствующий большему вектор решений является избыточным;
- иначе вектора являются несравнимыми и соответствующие вектора решений не попадают под правило
очистки.
Пример 2
Пусть двоичное представление двух исходных векторов решений 1x и 2x будет следующим:
);1,0,1,1,0,1,0,1,0,0,1,1,0,1,0,1();1,0,1,1,0,0,0,1,0,0,1,0,0,1,0,0( '
2
'
1 == xx
Разобьем двоичное представление на последовательности по 8 значений и вычислим десятичное значение
последовательности.
)173,172()1,0,1,1,0,1,0,1,0,0,1,1,0,1,0,1(
)141,36()1,0,1,1,0,0,0,1,0,0,1,0,0,1,0,0(
''
2
173222221722222
'
2
''
1
14122223622
'
1
753207532
732052
=⇔=
=⇔=
=++++=+++=
=+++==+=
xx
xx
4342143421
434214434421
Операция сравнения заключается в проверке условия
)()( ''
2
''
1
''
2
''
1 xxxx ∧=∨
В нашем случае )141,36()173,172()141,36()( ''
2
''
1 =∧=∧ xx , что говорит о том что вектора ''
1x и
''
2x сравнимые и ''
2
''
1 xx < , тогда вектор решений 2x является избыточным.
Алгоритм построения базиса на множестве {0,1}
В работе [1] представленн алгоритм решения СЛОДУ на множестве {0,1}, котрый ищет базис решений
выполняя перебор всех )12( −q возможных значений вектора решения, где q - количество переменных в
системе. Данный алгоритм является особенно эфективным для некоторых видов систем, применение TSS
алгоритма для которых дает сложность экспотенциальную по числу переменных в системе. Критеческой по
времени операцие опять является операция отбрасования избыточных векторов – сравнение каждого нового
решения со всеми решениями уже присутствующими в базисе.
Реализация
1. Двоичному представлению вектора решения ставится в соответствие массив, каждый элемент которого
будет представлять десятичное значение двоичной последовательности определенной длины
двоичного вектора, как это описано в реализации алгоритма TSS. Это даст выигрыш при
многочисленных операциях сравнения векторов.
2. Отдельно запоминается первое минимальное решение базиса – поскольку значения перебираются в
порядке возрастания, то первое найденное решение и будет минимальным решением. Далее каждое
следущее решение прежде чем сравниватся с базисом, сравнивается с минимальным решением.
- если решение сравнимо с минимальным, значит оно является избыточным,
- иначе необходимо выполнять сравнение со всем базисом.
Эксперименты
Существует несколько реализаций TSS алгоритма. В таблице ниже приведены временные результаты
поиска TSS для некоторых систем оптимизированной версии алгоритма и другой реализации [3]. Вкачестве
свободных членов выбраны числа стоящие в последнем столбце.
Время выполнения, млсек. СЛНДУ Число
решений Pеализация [3] Оптимизированная
реализация
1 2 -3 -2 -4
2 -1 -3 2 5
1 0 0
10 -7 -8 3 -11
12 -9 -7 3 -13
10 10 1
-10 0 20 -1 -21
9 1 -17 2 19
0 0 0
1 -3 9 -1 81
-9 27 81 -9 1
1 -3 9 1 -81
0 107 10
-10 7 3 -6 90
10 9 8 -15 2
-7 -5 -3 -2 89
0 109 10
-5 -2 1 4 1
9 62 -5 -3 101
56 -34 -11 67 98
2 40 4
2 -3 -5 -1 -2 4
5 10 -3 -7 2 1
3 0 4 -2 -3 -1
0 29 3
-12 2 2 2 0 3 3
6 -1 -5 0 0 0 0
-6 1 1 1 1 1 1
1 8 1
0 0 0 0 -3 1 1 1
0 0 -5 1 1 1 1 1
-7 1 1 1 1 1 1 1
5460 2149 210
Заключение
В данной стать были приведены методы оптимизацированной реализации алгоритмов решения систем
линейных диофантовых уравнений для получения усеченного множества решений TSS и для решения систем
на множестве {0,1}. Проведенные эксперементы показали, что оптимизированная реализация работает на
порядок быстрее чем другие существующие реализации, что являятся очень важным параметром поскольку
сложность алгоритма растет экспотенциально взависимости от числа неизвестных присутствующих в исходной
системе уравнений.
Список Литературы
1. Крывый C.Л. Об алгоритмах решения систем линейных диофантовых констрейнтов в области {0,1}. Кибернетика и сист. анализ. –
2003. – N 5. – С.
2. Крывый C.Л. О некоторых методах и критериях совместности систем линейных диофантовых уравнений в области натуральных
чисел. Кибернетика и сист. анализ. – 1999. – N 4. – С. 12 – 36
3. Крывый С.Л., Матвеева Л.Е. Формальные методы анализа свойств систем. Кибернетика и сист. анализ. – 2003. – N 2. – С. 15 – 36
4. Murata T. Petri Nets: Properties, Analysis and Applications. In “Proceedings of the IEEE”, 1989, vol. 77, N.4, P. 541-580
|