УСТРОЙСТВО ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ КООПЕРАТИВНЫХ ИГР Российский патент 2014 года по МПК G06F17/00 

Описание патента на изобретение RU2522693C2

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

Известно устройство для моделирования процесса принятия решений (Патент РФ №2262131, опубл. 10.10.05 г.), содержащее две группы регистров, входы которых являются входами параметров устройства, блок умножения импульсов, четыре блока умножения, компаратор, генератор тактовых импульсов, блок суммирования, два блока вычитания, блок умножения на «0», счетчик, блок деления, интегратор и регистр.

Недостатком наиболее близкого технического решения является отсутствие учета наличия нескольких конфликтующих сторон, принимающих решение совместно путем объединения в различные коалиции, из-за того, что предназначено для одного лица, принимающего решение.

Технический результат - увеличение быстродействия устройства, позволяющего на основе характеристической функции кооперативной игры находить ее решение в виде вектора Шепли быстрее, чем в эквивалентных программных реализациях.

Требуемый технический результат достигается тем, что устройство, содержащее регистр, группу регистров, генератор тактовых импульсов, счетчик, блок умножения импульсов, два блока умножения, два блока вычитания, блок деления, блок интегратора, дополнительно содержит два регистра, блок формирования очередной коалиции, блок установки значения 1 в заданную позицию двоичного представления числа, интегратор, блок уменьшения на «1», три блока вычисления факториала, причем входы группы регистров, первого и второго регистра, являются входами устройства, а выход третьего регистра является выходом устройства, при этом выходы первого регистра соединены с первым входом блока формирования очередной коалиции, а также с первым входом блока установления значения 1 в заданную позицию двоичного представления числа, выходы второго регистра соединены со вторым входом блока формирования очередной коалиции, входом блока уменьшения на «1» и входом первого блока вычисления факториала, выходы генератора тактовых импульсов соединены с входом блока умножения импульсов, счетным входом счетчика, вторым входом интегратора и вторым входом третьего регистра, выходы блока умножения импульсов соединены со вторыми входами первого и второго регистров, третьим входом блока формирования очередной коалиции, четвертым входом группы регистров, а также со вторым входом блока интегратора, выход переполнения счетчика соединен с входом останова генератора тактовых импульсов, выход значения счетчика соединен со вторым входом первого блока вычитания, а также с входом третьего блока вычисления факториала, выход блока уменьшения на «1» соединен с первым входом первого блока вычитания, выход первого блока вычисления факториала соединен со вторым входом блока деления, выходы блока формирования очередной коалиции соединены со вторым входом блока установки значения 1 в заданную позицию двоичного представления числа, а также с третьим адресным входом группы регистров, выход первого блока вычитания соединен с входом второго блока вычисления факториала, выход блока установки значения 1 в заданную позицию двоичного представления числа соединен со вторым адресным входом группы регистров, выход второго блока вычисления факториала соединен с первым входом первого блока умножения, выход третьего блока вычисления факториала соединен со вторым входом первого блока умножения, выход которого соединен с первым входом блока деления, первый и второй выходы группы регистров соединены соответственно с первым и вторым входом второго блока вычитания, выход которого соединен с первым входом первого интегратора, выход блока деления соединен со вторым входом второго блока умножения, выход блока интегратора подключен к первому входу второго блока умножения, выход которого соединен с первым входом интегратора, выход интегратора соединен с первым входом третьего регистра.

На чертеже представлена структурная схема устройства поддержки принятия решений на основе кооперативных игр.

Устройство поддержки принятия решений на основе кооперативных игр включает три регистра 1, 2 и 3, группу регистров 4, генератор тактовых импульсов 5, счетчик 6, блок умножения импульсов 7, два блока умножения 8 и 9, два блока вычитания 10 и 11, блок деления 12, блок интегратора 13, блок формирования очередной коалиции 14, блок установки значения 1 в заданную позицию двоичного представления числа 15, интегратор 16, блок уменьшения на «1» 17, три блока вычисления факториала 18, 19, 20.

Работает устройство поддержки принятия решений на основе кооперативных игр следующим образом.

Предполагается, что задана кооперативная игра (N, ν), где N={0,1, …, n-1} - множество игроков (конфликтующих лиц, принимающих решение), ν:2N→R - характеристическая функция игры, определяющая для каждой коалиции K ее выигрыш ν(K). Имеются ограничения, накладываемые на характеристическую функцию:

1. Персональность. Пустая коалиция имеет нулевой выигрыш:

ν(⌀)=0.

2. Существенность. В результате слияния две непересекающиеся коалиции получат совместный выигрыш больше, чем по отдельности:

K , S N K S = ν ( K S ) > ν ( K ) + ν ( S ) .

Выигрыш, получаемый игроком i∈N в результате совместно принимаемых решений, определяется соответствующей компонентной вектора Шепли φ[ν] по формуле:

( φ [ ν ] ) i = k = 0, n 1 k ! ( n 1 k ) ! n ! K N \ { i } | K | = k ( ν ( K { i } ) ν ( K ) ) ( 1 ) .

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

Отметим ряд особенностей реализации данного алгоритма в виде устройства:

1. Характеристическая функция ν представляется в виде вектора вещественных значений, размера 2n по числу возможных коалиций.

2. Для представления произвольной коалиции K⊆N используется целое беззнаковое число достаточной длины, интерпретируемое в двоичной форме в виде вектора нулей и единиц размера n, причем i-я компонента равна единице тогда и только тогда, когда игрок i входит в коалицию - 1∈K.

3. Компоненты вектора характеристической функции v индексируются с помощью двоичных представлений всех возможных коалиций K⊆N, соответственно принимают в десятичном представлении все значения от 0 до 2n-1.

4. Под знаком внутренней суммы в формуле (1) перебор всех коалиций К⊆N\{i} таких, что |K|=k, осуществляется с помощью обычного комбинаторного принципа генерации всех сочетаний без повторений из n-1 элемента по k.

При запуске от внешнего источника, не показанного на чертеже, генератора тактовых импульсов 5, на входы устройства, выполненные в виде регистра 1, регистра 2 и группы регистров 4, по первому импульсу подаются соответственно значения номера вычисляемой компоненты вектора Шепли i, число игроков n и вектор значений характеристической функции ν. В начальном состоянии счетчик 6 имеет значение 0.

Импульсы генератора тактовых импульсов 5 передаются в блок умножения импульсов 7 и умножаются на значение мощности множества | { K | K N \ { i } & | K | = k } | = C n 1 k с учетом получаемого значения k от счетчика 6, и передаются с целью синхронизации к регистру 1, регистру 2, блоку формирования очередной коалиции 14 и блоку интегратора 13. Импульсы генератора тактовых импульсов 5 также передаются на входы счетчика 6, интегратора 16 и регистра 3.

Для каждого значения k счетчика 6 на входы блока формирования очередной коалиции 14 поступают значения i и n соответственно от регистра 1 и регистра 2. После чего данный блок формирования очередной коалиции 14 в виде двоичного беззнакового целого числа формирует очередную коалицию К⊆N\{i} такую, что |K|=k, и передает ее в блок установки значения 1 в заданную позицию двоичного представления числа 15 и в блок группы регистров 4.

Блок установки значения 1 в заданную позицию двоичного представления числа 15 также от регистра 1 на вход принимает значение i. Он устанавливает значение 1 в позицию i двоичного представления очередной коалиции K, тем самым вычисляя объединение K∪{i}.

Полученные коалиции K и K∪{i} передаются в качестве номеров (адресов) компонент вектора характеристической функции ν на входы группы регистров 4, в результате на входы блока вычитания 11 поступают соответственно значения ν(K∪{i}) и ν(K).

Полученная разность передается на вход блока интегратора 13, который за С n 1 k шагов суммирования в результате перебора всех коалиций К для заданного k вычисляет величину:

K N \ { i } | K | = k ( ν ( K { i } ) ν ( K ) ) .

При каждом такте генератора тактовых импульсов 5 на вход блока уменьшения на «1» 17 передается от регистра 2 величина n, полученное значение n-1 поступает вместе с величиной k счетчика 6 на входы блока вычитания 10. Вычисленное значение n-1-k передается на вход блока вычисления факториала 19. Вместе со значением (n-1-k)! от блока 19 на вход блока умножения 8 передается величина k!, полученная с выхода блока вычисления факториала 20, который от счетчика 6 на вход принимает значение k.

Также при каждом такте генератора тактовых импульсов 5 на вход блока вычисления факториала 18 передается от регистра 2 значение n. Полученное значение n! и выходная величина блока умножения 8 передаются на входы блока деления 12, который вычисляет значение k ! ( n 1 k ) ! n ! .

На входы блока умножения 9 поступают значение блока интегратора 13, накопленное за C n 1 k шагов суммирования, результат работы блока деления 12. Полученное произведение передается в интегратор 16, который за n шагов вычисляет результирующую величину (φ[ν])i и помещает ее в выходной регистр 3.

Работа устройства останавливается, когда величина k счетчика 6 примет все значения от 0 до n-1, после чего сигнал переполнения счетчика 6 подается на вход останова генератора тактовых импульсов 5.

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

Похожие патенты RU2522693C2

название год авторы номер документа
Устройство для вычисления Г-функций 1979
  • Кобчиков Александр Всеволодович
  • Матушанский Григорий Ушерович
SU922759A1
Статистический анализатор 1987
  • Алыпов Юрий Евгеньевич
  • Фатиков Сергей Владимирович
SU1499376A1
Устройство для вычисления начальных моментов 1980
  • Корчагин Владимир Герасимович
  • Кравцов Леонид Яковлевич
  • Лакийчук Дмитрий Евменович
  • Мартыненко Александр Семенович
  • Садомов Юрий Борисович
  • Хохлов Лев Михайлович
SU935971A1
Устройство для вычисления факториала числа 1988
  • Кузьо Мирослав Николаевич
  • Самчинский Анатолий Анатольевич
  • Помыткина Елена Леонидовна
SU1571609A1
Устройство для определения числа сочетаний 1986
  • Лукоянов Владимир Александрович
  • Корев Андрей Юрьевич
SU1396148A1
УСТРОЙСТВО ИЗМЕРЕНИЯ ЧАСТОТЫ И ВРЕМЕННОЙ ЗАДЕРЖКИ РАДИОСИГНАЛА 1992
  • Павлов Р.В.
  • Вишняков В.А.
RU2048683C1
Устройство для формирования случайных процессов с заданным спектром 1981
  • Никонов Александр Михайлович
  • Осипов Михаил Васильевич
SU1027723A1
СПОСОБ ИЗМЕРЕНИЯ ЧАСТОТЫ (ВАРИАНТЫ) И УСТРОЙСТВО ДЛЯ ЕГО РЕАЛИЗАЦИИ (ВАРИАНТЫ) 2008
  • Ермаков Владимир Филиппович
  • Федоров Владимир Степанович
RU2380716C1
Устройство для вычисления тригоно-МЕТРичЕСКиХ фуНКций 1979
  • Ахметов Виктор Ниязович
  • Гусев Алексей Владимирович
  • Циделко Владислав Дмитриевич
SU832555A1
Устройство для определения спектральных коэффициентов разложения случайного процесса по функциям Хаара 1980
  • Докучаев Александр Алексеевич
  • Зенцов Владимир Александрович
  • Свиньин Сергей Федорович
SU935814A1

Реферат патента 2014 года УСТРОЙСТВО ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ НА ОСНОВЕ КООПЕРАТИВНЫХ ИГР

Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных устройствах вычислительной техники для определения наилучшей стратегии управления в условиях неопределенности. Технический результат заключается в увеличении быстродействия устройства, позволяющего на основе характеристической функции кооперативной игры находить ее решение в виде вектора Шепли быстрее, чем в эквивалентных программных реализациях. Требуемый технический результат достигается тем, что устройство, включающее регистр, группу регистров, генератор тактовых импульсов, счетчик, блок умножения импульсов, два блока умножения, два блока вычитания, блок деления, блок интегратора, дополнительно содержит два регистра, блок формирования очередной коалиции, блок установки значения 1 в заданную позицию двоичного представления числа, интегратор, блок уменьшения на «1», три блока вычисления факториала. 1 ил.

Формула изобретения RU 2 522 693 C2

Устройство поддержки принятия решений на основе кооперативных игр, включающее регистр, группу регистров, генератор тактовых импульсов, счетчик, блок умножения импульсов, два блока умножения, два блока вычитания, блок деления, блок интегратора, отличающееся тем, что оно содержит дополнительно два регистра, блок формирования очередной коалиции, блок установки значения 1 в заданную позицию двоичного представления числа, интегратор, блок уменьшения на «1», три блока вычисления факториала, причем входы группы регистров, первого и второго регистра, являются входами устройства, а выход третьего регистра является выходом устройства, при этом выходы первого регистра соединены с первым входом блока формирования очередной коалиции, а также с первым входом блока установления значения 1 в заданную позицию двоичного представления числа, выходы второго регистра соединены со вторым входом блока формирования очередной коалиции, входом блока уменьшения на «1» и входом первого блока вычисления факториала, выходы генератора тактовых импульсов соединены с входом блока умножения импульсов, счетным входом счетчика, вторым входом интегратора и вторым входом третьего регистра, выходы блока умножения импульсов соединены со вторыми входами первого и второго регистров, третьим входом блока формирования очередной коалиции, четвертым входом группы регистров, а также со вторым входом блока интегратора, выход переполнения счетчика соединен с входом останова генератора тактовых импульсов, выход значения счетчика соединен со вторым входом первого блока вычитания, а также с входом третьего блока вычисления факториала, выход блока уменьшения на «1» соединен с первым входом первого блока вычитания, выход первого блока вычисления факториала соединен со вторым входом блока деления, выходы блока формирования очередной коалиции соединены со вторым входом блока установки значения 1 в заданную позицию двоичного представления числа, а также с третьим адресным входом группы регистров, выход первого блока вычитания соединен с входом второго блока вычисления факториала, выход блока установки значения 1 в заданную позицию двоичного представления числа соединен со вторым адресным входом группы регистров, выход второго блока вычисления факториала соединен с первым входом первого блока умножения, выход третьего блока вычисления факториала соединен со вторым входом первого блока умножения, выход которого соединен с первым входом блока деления, первый и второй выходы группы регистров соединены соответственно с первым и вторым входом второго блока вычитания, выход которого соединен с первым входом первого интегратора, выход блока деления соединен со вторым входом второго блока умножения, выход блока интегратора подключен к первому входу второго блока умножения, выход которого соединен с первым входом интегратора, выход интегратора соединен с первым входом третьего регистра.

Документы, цитированные в отчете о поиске Патент 2014 года RU2522693C2

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССА ПРИНЯТИЯ РЕШЕНИЙ 2004
  • Золотых Ю.А.
  • Микитенко И.И.
  • Шпайхер В.Г.
  • Борисов Э.В.
RU2262131C1
УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ПРОЦЕССА ПРИНЯТИЯ РЕШЕНИЙ 2002
  • Борисов Э.В.
  • Воробьев С.Н.
  • Золотых Ю.А.
  • Микитенко И.И.
RU2214624C2
US 7079985 B2, 18.07.2006
Способ приготовления лака 1924
  • Петров Г.С.
SU2011A1
US 6961678 B2, 01.11.2005

RU 2 522 693 C2

Авторы

Влацкая Ирина Валерьевна

Нестеренко Максим Юрьевич

Полежаев Петр Николаевич

Кириллов Алексей Сергеевич

Даты

2014-07-20Публикация

2012-09-03Подача