Поиск заданного количества решений системы размытых ограничений

Поиск заданного количества решений системы размытых ограничений

Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы ра...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2018
Автори: Шлезингер, М.И., Флах, Б., Водолазский, Е.В.
Формат: Стаття
Мова:Russian
Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2018
Назва видання:Кибернетика и системный анализ
Теми:
Системний аналіз
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/144833
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-144833
record_format dspace
spelling irk-123456789-1448332019-01-06T01:23:21Z Поиск заданного количества решений системы размытых ограничений Шлезингер, М.И. Флах, Б. Водолазский, Е.В. Системний аналіз Исследована минимаксная модификация задачи распознавания совместимости системы ограничений, когда для каждого решения определена не бинарная допустимость, а ее количественная характеристика. Описанный в статье алгоритм находит за полиномиальное время требуемое количество наилучших решений системы размытых ограничений, если эти ограничения инвариантны относительно некоторого мажоритарного оператора. Существенно, что для реализации алгоритма не требуется знания этого оператора, более того, не требуется гарантировать его существование. Для любой системы размытых ограничений алгоритм либо находит заданное количество наиболее допустимых решений, либо выдает отказ от решения задачи. Последнее возможно, только если для решаемой системы ограничений такой оператор отсутствует. Досліджено мінімаксну модифікацію задачі розпізнавання несуперечності системи обмежень, коли для кожного розв’язку визначено не бінарну допустимість, а її кількісну характеристику. Описаний в статті алгоритм знаходить за поліноміальний час задану кількість найкращих розв’язків системи розмитих обмежень, якщо ці обмеження інваріантні відносно деякого мажоритарного оператора. Важливо, що для реалізації алгоритму не потрібно знання цього оператора, більш того, не потрібно гарантувати його існування. Для довільної системи розмитих обмежень алгоритм або знаходить задану кількість найбільш допустимих розв’язків, або дає відмову від розв’язку задачи. Останнє можливо, тільки якщо для розв’язаної системи обмежень такого оператора не існує. 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. 2018 Article Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/144833 519.157 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
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 2018
topic_facet Системний аналіз
url http://dspace.nbuv.gov.ua/handle/123456789/144833
citation_txt Поиск заданного количества решений системы размытых ограничений / М.И. Шлезингер, Б. Флах, Е.В. Водолазский // Кибернетика и системный анализ. — 2018. — Т. 54, № 1. — С. 67–83. — Бібліогр.: 22 назв. — рос.
series Кибернетика и системный анализ
work_keys_str_mv AT šlezingermi poiskzadannogokoličestvarešenijsistemyrazmytyhograničenij
AT flahb poiskzadannogokoličestvarešenijsistemyrazmytyhograničenij
AT vodolazskijev poiskzadannogokoličestvarešenijsistemyrazmytyhograničenij
first_indexed 2023-05-20T17:20:35Z
last_indexed 2023-05-20T17:20:35Z
_version_ 1796153078821421056

Схожі ресурси