Cтраница 2
Пусть Р - алгебра ( L, Д V) удовлетворяет условиям теоремы. Ограничивая Р - операции Д и J на двухэлементных подмножествах ( в привычных инфиксных обозначениях: Д х, у х Д у, J х, у ] х V /) мы легко получаем из условия ( а) коммутативность и ассоциативность построенных бинарных операций. Кроме того, они удовлетворяют законам поглощения и, следовательно, идемпотентны. Значит, отношение порядка о) ( д:, у): Д х, у х ], как в теореме 3, определяет на - L структуру решетки, в которой порядковые операции inf и sup совпадают с бинарными операциями Д и V соответственно. [16]
Упорядоченное множество Е называется структурой, если каждое его конечное подмножество S С Е обладает верхней гранью и нижней гранью. Достаточно потребовать, чтобы это имело место для каждого двухэлементного подмножества. [17]
Sub sd, r sdl, r 4, Alt sdl Alt r, s r - 1 и существуют s - элементные подалгебры алгебры sd ( если sd sd, это всегда так), то любое s - элементное подмножество множества п есть подалгебра алгебры sd, любые такие подалгебры изоморфны, и либо группы автоморфизмов подобных алгебр суть полные симметрические группы перестановок соответствующих подмножеств, либо эти группы автоморфизмов суть знакопеременные группы перестановок на соответствующих множествах. Попарный изоморфизм двухэлементных подалгебр алгебры sd имеет место и в случае, когда г 3, однако ограничения перестановок из Alt 3 на двухэлементные подмножества суть тождественные отображения последних. [18]
Поэтому далее в этой главе рассмотрим реализацию шагов 3 и 9 алгоритма 1 в случае, когда множество с41 совпадает с множеством HP нормальных функций выбора. При этом решение задачи Q, HP, 93 У совпадает с множеством QR недоминируемых по бинарному отношению R элементов. Отношение R однозначно определяется значениями CR на всех двухэлементных подмножествах Q, и задача построения QR является математической задачей выбора. [19]
Для приближенного решения задачи о сумме элементов подмножества имеется и другой алгоритм, который также не лишен жадности. Этот алгоритм выдает тем лучший результат, чем дольше он работает, и если его можно прогнать N 1 раз, то выданный им результат будет оптимальным. Причина этого в том, что на каждом проходе он вовлекает в рассмотрение новые случаи. На первом проходе алгоритм начинает с пустого множества и добавляет в него элементы в убывающем порядке до тех пор, пока не будет достигнут предел или не будут опробованы все элементы входного списка. На втором проходе алгоритм начинает со всевозможных одноэлементных подмножеств и добавляет к ним элементы списка. На третьем проходе изучаются все двухэлементные подмножества. Число проходов ограничено только временем, отведенным на работу алгоритма. Если при списке из 10 элементов удается выполнить 11 проходов, то оптимальное решение будет найдено. Для списка из 10 элементов на первом проходе имеется единственное пустое подмножество, на втором проходе есть 10 одноэлементных подмножеств, на третьем имеется 45 двухэлементных подмножеств. Больше всего начальных подмножеств встречается на шестом проходе - это 252 пя-тиэлементных подмножества. Поэтому хотя сам процесс и выглядит простым, он все равно требует значительного времени. [20]
Для приближенного решения задачи о сумме элементов подмножества имеется и другой алгоритм, который также не лишен жадности. Этот алгоритм выдает тем лучший результат, чем дольше он работает, и если его можно прогнать N 1 раз, то выданный им результат будет оптимальным. Причина этого в том, что на каждом проходе он вовлекает в рассмотрение новые случаи. На первом проходе алгоритм начинает с пустого множества и добавляет в него элементы в убывающем порядке до тех пор, пока не будет достигнут предел или не будут опробованы все элементы входного списка. На втором проходе алгоритм начинает со всевозможных одноэлементных подмножеств и добавляет к ним элементы списка. На третьем проходе изучаются все двухэлементные подмножества. Число проходов ограничено только временем, отведенным на работу алгоритма. Если при списке из 10 элементов удается выполнить 11 проходов, то оптимальное решение будет найдено. Для списка из 10 элементов на первом проходе имеется единственное пустое подмножество, на втором проходе есть 10 одноэлементных подмножеств, на третьем имеется 45 двухэлементных подмножеств. Больше всего начальных подмножеств встречается на шестом проходе - это 252 пя-тиэлементных подмножества. Поэтому хотя сам процесс и выглядит простым, он все равно требует значительного времени. [21]