Cтраница 2
Отметим, что построение для данного конкретного прио-ритето-порождающего функционала F ( n) функционала приоритета, который не был бы автоограниченным, требует определенной изобретательности. В то же время все известные функционалы приоритета ( см. § 1 данной главы) являются автоограниченными. [16]
Пусть V 1, 2, 3, 4); ti l, i 1, 4, w 10, w3Z 3, w3i - 1, а все остальные Wi, равны нулю. Следовательно, в рассматриваемом случае функционала приоритета со ( л) не существует. [17]
Из теоремы 6.3 следует, что D-алгоритм позволяет получать оптимальную перестановку при любом автоограниченном функционале приоритета и любом последовательно-параллельном графе G. Вместе с тем нетрудно привести примеры, в которых граф G не является последовательно-параллельным, но при данном конкретном функционале приоритета / - алгоритм переводит его в цепь. Накладывая определенные ограничения на пару функционал приоритета - граф G, можно описывать более широкие ( по сравнению с последовательно-параллельными графами) классы разрешимых ситуаций. Рассмотрим один из таких классов. [18]
В этом случае функционал F ( n) называется приоритето-порождающим на множестве &, а функционал ш ( я) - его функционалом приоритета. [19]
Из теоремы 6.3 следует, что D-алгоритм позволяет получать оптимальную перестановку при любом автоограниченном функционале приоритета и любом последовательно-параллельном графе G. Вместе с тем нетрудно привести примеры, в которых граф G не является последовательно-параллельным, но при данном конкретном функционале приоритета / - алгоритм переводит его в цепь. Накладывая определенные ограничения на пару функционал приоритета - граф G, можно описывать более широкие ( по сравнению с последовательно-параллельными графами) классы разрешимых ситуаций. Рассмотрим один из таких классов. [20]