Задачи поиска на линейно-упорядоченных множествах данных

Задача поиска, в которой отношение поиска является отношением линейного предпорядка, наверное, одна из самых распространенных и вместе с тем самых простых задач поиска. Простейший пример: отдел кадров предприятия желает получить список всех сотрудников, получающих более 10000 рублей в год. В геометрической интерпретации эта задача называется одномерной задачей о доминировании [64, 86].

Эта задача имеет полное и окончательное решение, которое мы здесь приведем. Этот результат был анонсирован в [20] и опубликован в [21]. Кстати, в этих работах впервые было введено понятие информационных графов, т. е. данная задача была пробным камнем для используемого здесь аппарата.

Если X — некоторое множество, то под отношением линейного I

предпорядка на X х X будем понимать бинарное отношение, для любых х, у, z ? X удовлетворяющее условиям

I

• рефлексивности х У х;

i i I

транзитивности (х У у) & (у У г)У z)

i I

• связности (х У у) V (у У х).

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

i

порядка, а именно, рассмотрим следующий тип: Sun = (Х,х,у),

I

где X — некоторое множество, У — некоторое отношение линейного предпорядка на X х X.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >