|
Вычислительные методы в дискретной математике
Медиана для нечётного числа отношений линейного порядка и её использование в задачах группового выбора
В. Н. Нефедов Московский авиационный институт, г. Москва, Россия
Аннотация:
Ищется медиана для нечётного числа отношений линейного порядка, заданных на конечном множестве $A $, также являющаяся линейным порядком на $A $. К подобной задаче приходим при исследовании некоторых задач группового выбора. В рассматриваемом случае бинарное отношение $\tilde{\rho}$, имеющее минимальное суммарное расстояние (по Хеммингу) до заданного набора бинарных отношений, является медианой для этих отношений, и притом единственной. Однако эта медиана не всегда является линейным порядком (или даже квазипорядком) и в этих случаях не может быть взята в качестве решения поставленной задачи. Тем не менее бинарное отношение $\tilde{\rho}$ обязательно принадлежит множеству $LA[n]$ (линейных асимметричных бинарных отношений на $A $), которому, в частности, принадлежат и все линейные порядки на $A $. Исследуются некоторые свойства бинарных отношений из $LA[n]$. Вводятся понятия «почти оптимального» и $\Delta$-оптимального отношений, являющихся линейными порядками и одновременно точными решениями поставленной задачи. Приводятся алгоритмы их нахождения, основанные на полученных утверждениях относительно бинарных отношений из $LA[n]$ и имеющие полиномиальную вычислительную сложность. Рассматривается отношение эквивалентности на множестве $LA[n]$, позволяющее разбивать это множество на классы эквивалентности, количество которых $K_n$ намного меньше числа элементов в $LA[n]$. Например, $|LA[5]|=1024$, $K_5=12$. Таким образом, каждое бинарное отношение из $LA[n]$ эквивалентно в точности одному из $K_n$ представителей классов эквивалентности, а следовательно, обладает его основными свойствами. Но тогда исследование широкого класса задач может быть сведено к рассмотрению сравнительно небольшого их набора. Процесс нахождения указанного набора представителей классов эквивалентности иллюстрируется для $n=2, 3, 4, 5$. Приводится также метод решения поставленной задачи, использующий представление бинарных отношений в виде графов (метод выделения минимальных множеств представителей контуров в медиане $\tilde{\rho}$), имеющий экспоненциальную вычислительную сложность.
Ключевые слова:
медиана отношений, отношение линейного порядка, линейные отношения, асимметричные отношения, расстояние Хемминга, классы эквивалентности, задача группового выбора.
Образец цитирования:
В. Н. Нефедов, “Медиана для нечётного числа отношений линейного порядка и её использование в задачах группового выбора”, ПДМ, 2022, № 57, 98–127
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm779 https://www.mathnet.ru/rus/pdm/y2022/i3/p98
|
Статистика просмотров: |
Страница аннотации: | 68 | PDF полного текста: | 29 | Список литературы: | 18 |
|