Поиск заданного количества решений системы размытых ограничений
Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы ра...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2018 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/144833 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862540801513357312 |
|---|---|
| author | Шлезингер, М.И. Флах, Б. Водолазский, Е.В. |
| author_facet | Шлезингер, М.И. Флах, Б. Водолазский, Е.В. |
| citation_txt | Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы размытых ограничений, если эти ограничения инвариантны относительно некоторого мажоритарного оператора. Существенно, что для реализации алгоритма не требуется знания этого оператора, более того, не требуется гарантировать его существование. Для любой системы размытых ограничений алгоритм либо находит заданное количество наиболее допустимых решений, либо выдает отказ от решения задачи. Последнее возможно, только если для решаемой системы ограничений такой оператор отсутствует.
Досліджено мінімаксну модифікацію задачі розпізнавання несуперечності системи обмежень, коли для кожного розв’язку визначено не бінарну допустимість, а її кількісну характеристику. Описаний в статті алгоритм знаходить за поліноміальний час задану кількість найкращих розв’язків системи розмитих обмежень, якщо ці обмеження інваріантні відносно деякого мажоритарного оператора. Важливо, що для реалізації алгоритму не потрібно знання цього оператора, більш того, не потрібно гарантувати його існування. Для довільної системи розмитих обмежень алгоритм або знаходить задану кількість найбільш допустимих розв’язків, або дає відмову від розв’язку задачи. Останнє можливо, тільки якщо для розв’язаної системи обмежень такого оператора не існує.
A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is essential that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists.
|
| first_indexed | 2025-11-24T16:08:15Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-144833 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-11-24T16:08:15Z |
| publishDate | 2018 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шлезингер, М.И. Флах, Б. Водолазский, Е.В. 2019-01-05T15:26:01Z 2019-01-05T15:26:01Z 2018 Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/144833 519.157 Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы размытых ограничений, если эти ограничения инвариантны относительно некоторого мажоритарного оператора. Существенно, что для реализации алгоритма не требуется знания этого оператора, более того, не требуется гарантировать его существование. Для любой системы размытых ограничений алгоритм либо находит заданное количество наиболее допустимых решений, либо выдает отказ от решения задачи. Последнее возможно, только если для решаемой системы ограничений такой оператор отсутствует. Досліджено мінімаксну модифікацію задачі розпізнавання несуперечності системи обмежень, коли для кожного розв’язку визначено не бінарну допустимість, а її кількісну характеристику. Описаний в статті алгоритм знаходить за поліноміальний час задану кількість найкращих розв’язків системи розмитих обмежень, якщо ці обмеження інваріантні відносно деякого мажоритарного оператора. Важливо, що для реалізації алгоритму не потрібно знання цього оператора, більш того, не потрібно гарантувати його існування. Для довільної системи розмитих обмежень алгоритм або знаходить задану кількість найбільш допустимих розв’язків, або дає відмову від розв’язку задачи. Останнє можливо, тільки якщо для розв’язаної системи обмежень такого оператора не існує. A minimax modification of a fuzzy constraint satisfaction problem is considered, where constraints determine not whether a given solution is feasible but the numerical value of satisfiability. The algorithm is proposed that finds a given number of solutions with the highest value of satisfiability in polynomial time for a subclass of problems with constraints invariant to some majority operator. It is essential that knowing the operator itself is not required. Moreover, it is not necessary to guarantee its existence. For any system of fuzzy constraints, the algorithm either finds a given number of best solutions or declines the problem. The latter is only possible when no such operator exists. Работа выполнена в рамках проекта № 7/2/267-39/17 «Создание интеллектуальных технологий на основе методов и средств образного мышления» (Отделение информатики НАН Украины) и при поддержке гранта № 16-05872S «Probabilistic graphical models and deep learning» (Грантовая агентура Чешской Республики). ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системний аналіз Поиск заданного количества решений системы размытых ограничений Пошук заданої кількості розв’язків системи розмитих обмежень Finding a given number of solutions to a system of fuzzy constraints Article published earlier |
| spellingShingle | Поиск заданного количества решений системы размытых ограничений Шлезингер, М.И. Флах, Б. Водолазский, Е.В. Системний аналіз |
| title | Поиск заданного количества решений системы размытых ограничений |
| title_alt | Пошук заданої кількості розв’язків системи розмитих обмежень Finding a given number of solutions to a system of fuzzy constraints |
| title_full | Поиск заданного количества решений системы размытых ограничений |
| title_fullStr | Поиск заданного количества решений системы размытых ограничений |
| title_full_unstemmed | Поиск заданного количества решений системы размытых ограничений |
| title_short | Поиск заданного количества решений системы размытых ограничений |
| title_sort | поиск заданного количества решений системы размытых ограничений |
| topic | Системний аналіз |
| topic_facet | Системний аналіз |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/144833 |
| work_keys_str_mv | AT šlezingermi poiskzadannogokoličestvarešeniisistemyrazmytyhograničenii AT flahb poiskzadannogokoličestvarešeniisistemyrazmytyhograničenii AT vodolazskiiev poiskzadannogokoličestvarešeniisistemyrazmytyhograničenii AT šlezingermi pošukzadanoíkílʹkostírozvâzkívsistemirozmitihobmeženʹ AT flahb pošukzadanoíkílʹkostírozvâzkívsistemirozmitihobmeženʹ AT vodolazskiiev pošukzadanoíkílʹkostírozvâzkívsistemirozmitihobmeženʹ AT šlezingermi findingagivennumberofsolutionstoasystemoffuzzyconstraints AT flahb findingagivennumberofsolutionstoasystemoffuzzyconstraints AT vodolazskiiev findingagivennumberofsolutionstoasystemoffuzzyconstraints |