|
81 Ф(Р)<Ф(р2) Р(р,)сР(р2). (2-36) Тогда элементы множества R(pi) не могут быть максимальными. Таким образом, метод определения максимального элемента для монотонно-рекурсивных функционалов сводится к следующему: 1. Рассматривается некоторое ограниченное число допустимых последовательностей таких, что объединение их родовых множеств и тех из рассматриваемых последовательностей, которые являются полными допустимыми, в совокупности дает все множество полных допустимых последовательностей. 2. На основе обобщенного принципа оптимальности исключается часть родовых множеств; из рассматриваемых полных допустимых последовательностей оставляются только те, которые дают набольшее значение функционалу; исключаются из рассмотрения последовательности, для которых родовое множество пусто. 3. Выбирается некоторая допустимая последовательность из числа рассмотренныхпоследовательностей, для которой родовое множество не пусто и не исключалось. Рассматривается некоторое ограниченное число допустимых последовательностей, являющихся продолжением выбранной последовательности и таких, что объединение их родовых множеств и тех из них, которые являются полными, в совокупности дают родовое множество выбранной последовательности. 4. Для множества, состоящего из вновь образованных в п.З. допустимых последовательностей и неисключенных и непродолженных ранее допустимых последовательностей, производятся операции, указанные в п.2. Далее пп.2, 3, 4 циклически повторяются. Если на каком-то этапе процесса решения не останется ни одной допустимой последовательности с непустым или неисключенным родовым множеством, то процесс решения завершен и в качестве решения берется одна из рассмотренных полных |
Множеством продолжений Р(р) будет совокупность всех конечных отрезков элементов р-родового множества, сопряженных с р. Обобщенный принцип оптимальности состоит в утверждении. Пусть заданы монотонно-рекурсовный функционал Ф и две допустимые последовательностир\ и рг, причем Ф(р{) < Ф(рг) P(Pi) С Р(Рг) <2'59) Тогда элементы множества R(pi) не могут быть максимальными. Таким образом, метод, определения максимального элемента для монотонно-рекурсивных функционалов сводится к следующему: 1. Рассматривается некоторое ограниченное число допустимых последовательностей таких, что объединение их родовых множеств и тех из рассматриваемых последовательностей, которые являются полными допустимыми, в совокупности дает все множество полных допустимых последовательностей. 2. На основе обобщенного принципа оптимальности исключается часть родовых множеств; из рассматриваемых полных допустимых последовательностей оставляются только те, которые дают набольшее значение функционалу; исключаются из рассмотрения последовательности, для которых родовое множество пусто. 3. Выбирается некоторая допустимая последовательность из числа рассмотренных, для которой родовое множество не пусто и не исключалось. Рассматривается некоторое ограниченное число допустимых последовательностей, являющихся продолжением выбранной последовательности и таких, что объединение их родовых множеств и тех из них, которые являются полными, в совокупности дают родовое множество выбранной последовательности. 4. Для множества, состоящего из вновь образованных в п.З. допустимых последовательностей и неисключенных и непродолженных ранее допустимых последовательностей, производятся операции, указанные в п.2 . Далее пп.2, 3, 4 циклически повторяются. Если на каком-то этапе процесса решения не останется ни одной допустимой последовательности с непустым или неисключенным родовым множеством, то процесс решения завершен и в качестве решения берется одна из рассмотренных полных допустимых последовательностей с небольшим значением функционала. На каждом этапе процесса решения требуется помнить множество полных последовательностей, остающихся для дальнейшего продолжения. Решением задачи является последовательность x={xj : j=l..N). Решение является допустимой, если Vi Gi(x) ,Х{,..., xn) начальный отрезок длины п. Хпдопустимый начальный отрезок, если V/ = 1..т £г.(Х ) = 2 &,-(*,•) ^ g°i (2-60) 7=1 Пусть задан начальный отрезок Хп. Значения функций Gi(Xn) i=l..m являются параметрами начального отрезка, а (т+ 1 )-мерный вектор с компонентами G[(Xn) параметрами решения задачи корректировки планграфика. Пусть даны Х1п и Х2п . Х]п мажорирует Х2п (Х\>-Х2п), если выполнены ь неравенства 1 2 *Gi(Xn) Gi(Xn)<0, i=l..m (причем хотя бы одно из них строгое) В процессе итераций допустимые начальные отрезки упорядочиваются так, что Go(Xn) S G0 (X2n) < Gi(^n) £ ..., n=l..N (2.61) тогда первый по порядку допустимый начальный отрезок длины N является искомым решением задачи корректировки. Пусть Wnмножество всех допустимых отрезков длины п. Пусть W°n, W°n подмножества W°n, такие, что 1. УУ» е 0", 3 Jf„ е => Y, |