Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 21
Текст из файла (страница 21)
Теория сложности имеет дело П То есть то, что можно работать с любой задачей. — Прим. нерво. Смозмнасть и разрешимость !!7 с количествами времени и памяти, необходимыми для решения задачи. Очевидно, что количества времени н памяти не постоянны, а изменяются в зависимости от размерности решаемой задачи. Для сетей Петри временные и емкостные затраты будут, по-видимому, функцией от числа пспиций и переходов. Другими факторами, влиякицими на время и память, будут число фишек в начальной маркировке и число входов и выходов для каждого перехода н позиции (число дуг в графе). Требуемые время и память будут изменяться от одной задачи к другой.
Поэтому оценки сложности алгоритма могут быть даны для наилучшего случая (нижняя граница) или наихудшего случая (верхияя граница). Поскольку не известно, относится данный пример задачи к наилучшему или наихудшему случаю, обычно принимается наихудший случай, и сложность алгоритма — это временные и емкостные затраты в худшем случае как функция от размерности задачи. Анализ сложности касается главным образом сложности задачи, а не конкретных деталей реализации какого-либо частного алгоритма. Поэтому в теории сложности игнорируются константы.
Сложность задачи размерности и определяют порядком пт или 2", или и 1од п, допуская меньшие члены и постоянные сомножителя. Особенно важны два общих класса алгоритмов: имеющих полиномиальную сложность (и, пе, и 1оя и, пе и т. д.) и имеющих неполиномиальную сложность (в частности, экспоненциальиую, 2", и факториальную, п1). Анализ сложности обычно применяют к конкретным алгоритмам, но его можно применить также и к общим задачам.
В этом случае определяется нижняя оценка сложности из всех алгоритмов, решающих задачу. Это обеспечивает значение сложноспц не зависящее от алгоритма, и, кроме того, может оказаться полезным в доказательстве того, что данный алгоритм оптимален (с точностью до константы), и в определении случаев, когда дальнейшая работа может привести к лучшему алгоритму решения задачи. Например, хорошо известно, что сортировка и чисел имеет сложность и 1од и. Следовательно, алгоритмы сложности и!оя и нельзя значительно улучшить (в асимптотически худшем случае). При определении сложности может быть полезно сведение одной задачи к другой.
Если задачу А можно свести к задаче В и В имеет сложность (а(п), то сложность А — это, самое большее, сложность В плюс стоимость преобразования из А в В (помня, что в результате перевода размерность задачи может измениться.) Сложность преобразования является, как правило, константой или линейной функцией и поэтому часто игнорируется. Следовательно, сведение задачи А к задаче В дает илн верхнюю границу сложности А (если известна сложность В), или нижнюю границу сложности В (если известна сложность А).
Используя снова в качестве примера задачи равенства и подмножества, получаем, что объем вычисле- Гласа с ВЗ ний, необходимый для решения задачи равенства, не больше чем удвоенный объем вычислений для задачи подмножества. Поскольку здесь участвует постоянный сомножитель, сложность задачи подмножества должна совпадать со сложностью задачи равенства. Эти два свойства задач анализа сетей Петри — разрешимость и сложность — имеют первостепенную важность для использования сетей Петри. В этой главе представляются некоторые известные результаты. Один из используемых методов — сведение одной задачи анализа Петри к другой. 5Л. Зпдачн дпстнжнмастн Задача достижимости — одна из самых важных задач анализа сетей Петри.
Она досих пор еще ив решена для различных вариаций ее определения. Были поставлены следующие четыре задачи достижимости для сети Петри С вЂ” (Р, Т, 1, 0) с начальной маркировкой р. Определение 5.3. Задача достижимосоги. Выполняется ли дли данной р'г р' ЕЯ (С, р)? Определение 5.4. Задача достижимости подмаркиоовки. Для подмножества Р'ш Р и маркировки р' существует ли р" 6 (?(С, р), такая, что р"(рд = р' (дд для всех о; б Р'? Определение 5.5.
Задача достижимости нуля. Выполняется ли Р' е (?(С, Р), где Р'(Р;) = О длЯ всех Рг Е Р? (О Е Р(С, Р)?). Определение 5.5. Задача достижимости муля в одной лозиг(ии. Для данной позиции рг Е Р существует ли р' Е Н(С, р) с р'(рг) =- О? Задача достижимости подмаркировки ограничивает задачу достижимости до рассмотрения только подмножества пожций, не принимая во внимание маркировки других позиций. Задача достижимости нуля выясняет, является ли достижимой частная маркировка с нулем фишек во всех позициях. Задача достижимости нуля в одной позиции выясняет, возможно ли удалить все фишки из данной позиции. Хотя эти четыре задачи различны, все опи эквивалентны.
Определенные взаимосвязи очевидны сразу. Задача достижимости нуля сводится к задаче достижимости; просто в задаче достижимости устанавливается р' = О. Аналогично задача достижимости сводится к задаче достижимостн подмаркнровки путем установки Р' = Р. Задача достнжимости нуля в одной позиции сводится к задаче достижимости подмаркировки установкой Р' = (рг) и р' = О.
Сложнее показать, что задача достижимости подмаркировки сводится к задаче достижимости нуля н что задача достижимости нуля Сложность и разрешимость сводится к задаче достижимости нуля в одной позиции. Все множество взаимосвязей представлено иа рис. 5.1. Сначала покажем, что задача достижимости подмаркировки сводится к задаче достнжимостн нуля. Пусть даны сеть Петри С, = = (Р» Т» 1» От) с начальной маркировкой рм подмножество Р'та : — Р, и маркировка р'. Мы хотим узнать, существует ли р" ~ Я(С» р,) с р'(РД = р"(РД для всех р, Е Р'.
Наш подход Задает дасжижижос пи дичи двсжижииости нуля адочк досжвжимости яоожс,таирвдпи Задача двстижимости «уля Й вдпод пввииж Рис. 5.1. Сводимость задач доститкииости. Дуга от одной задачи к другой означает, что первая сводится ко второй. заключается в построении новой сети Петри С, = (Рз, Т„Хз, 0,) с начальной маркировкой р„такой, что маркировка р" б й(С» рД с р (Рт) = р (ЛД для всех Р; Е Р' существует тогда и только тогда, когда 0 6 Й(Са рз).
Построение С, из С, осуществляется исключительно просто. Начнем с С, совпадающей с С,. Для того чтобы позволить всякой позиции р; вне Р' стать пустой, введем переход г; с входом (рт) и пустым выходом. Этот переход можно запускать всякий раз, когда в Р; имеются фишки, чтобы изъять их, что позволяет достичь нулевой маркировки и тем самым игнорировать такие позиции. Относительно р; в Р' необходимо иметь уверенность, что в Р, точно Р'(Р;) фишек.
Дла этого постРоим новые позиции Рт длЯ каждой Р; Е Р' с начальной маркировкой р'(Р,) фишек и переход З, с входом (р» Р;) и пустым выходом. Если в рт точно р'(РД фишек, то этот переход можно запустить точно р'(РД раз, сокращая Маркировки рт и р,' до нуля. Если число фишек в р; отлично от )ь'(р;), то переход гт можно запустить только минимальное из двух маркировок число раз, и поэтому либо в р» либо в р, останутся фишки, препятствующие достижению нулевой маркировки.
Рис. 5.2. Сеть Петри, служащая для доказательства сводимости задачи достижимости подмаркировки к задаче достижимости нули. Подмножество поаицнй»о' будет иметь маркировку р' в первоначальной сети тогда и только тогда, когда в модифицированной показанным здесь способом сети будет достижима нулевая маркировка. Два типа вводимых переходов иллюстрируются на рис, 5.2. Формально определим Ся следующим образом: Р. = Р,() (Р.'!Р,Е Р'!. та=т,() ! дР;ЕРт), Хз (6) = /1 (Уг) для 11 Е Тъ Уа( г,) = (Р.! дли Р к Р = (р„р'! для р, ЕР', О (Ч = О (~т) для 1уЕТг» Оз((;) = [ ! дли Р,ЕРм с начальной маркировкой: Р»з(Р») = Рг(Р»)' Рь ЕРм Ря(Р,) = Р (Р|)» РгЕР'.
Теорема 5.1. Задача достижимости подмаркировки сводится к задаче достижимости нуля. Сложность и розрешшвость Докозаглельства. Покажем, что для сети Петри С„построенной из С, вышеописанным способом, О Е )с(С „пз) тогда и только тогда, когда р" Е И(С» р,) с (!"(р;) = р'(р;) для всех р; Е Р'. Для того чтобы показать, что О Е П(С» рэ) тогда и только тогда, когда существует р" Е Й(С» р,) с р."(Р;) = р'(р;) для р! Е Р', допустим сначала, что р" присутствует в )с(С» !»).
Тогда в С также можно достичь маркировки р" в позициях р; Е Р, запуском только переходов из Т» Сейчас для каждой позиции Р, Е Р' можно запустить (,' точно р'(р;) раз, сокращая маркировку и Р» н л до нуля. Затем можно запустить |,' для каждой Р; Е Р' столько раз, сколько необходимо для приведения маркировки этих позиций к нулю, поэтому О 6 Р(Сз рэ). 'Теперь предположим, что О 6 Х((С» р,); тогда су!цествует по следовательность запусков переходов и, переводящая р в О. Эта последовательность будет содержать точно р'(р!) запусков Р! для р; Е Р' (для удаления фишек из р ) н некоторое число запусков г для и; Е Р'. Заметим, что запуски этих переходов только удаляют фишки из С» и поскольку б(р.', г!) определено там, где определено б(р, (т) для р' ъ р (лишние фишки не могут повредить запуску переходов), последовательность о после удаления из нее всех запусков 1с останется действительной и будет приводить к маркировке н" с точно !!'(р;) фишками в р,- для р; Е Р'.
Таким образом, если О Е )с(С» р,), то р" Е )с(С» р,,) с и"(р!) = р,'(р!) для Рь Е Р'. Наша следующая задача — показать, что задача достижимости нуля сводится к задаче достижямостн нуля в одной пспнции. Доказательство этого утверждения также ссновано на вспомогательном построении. Пусть дана сеть Петри С, = (Р» Т» У» О,) с начальной маркировкой р» мы хотим определить, выполняется ли О Е Е гг(С» !!,). Построим из С, новую сеть Петри С, с дополнительной позицией з(Р, = Р, Ь (з)), такой, что маркировка р' Е К(С» р~) с р'(з) = О существует тогда и только тогда, когда О Е й(С„р,). Построение С определяет з так, что всякий раз число фишек в з равно сумме числа фишек в позициях С» Следовательно, если !!'(з) = О, то в позициях С, нет фишек, и наоборот.
Определим начальную маркировку р,, следующим образом: Рз(Р!) = Р1(Р!) Дли Рг ЕРм Н.(з) = М, Р (Р,). г Е "г Далее для каждого перехода г! Е Т, в С, будет тот же переход, но с добавленными дугами к позиции з. Определим (~ =,'~ (ф~(р,, о(г!)) — !г (р;г(ч)). гчЕгв !22 Глава Б Тогда дх — это разность числа фишек после запуска перехода Хх и числа фишек до запуска Хь Теперь, если с(х ~ О, то б~ фишек должно быть добавлено в позицию з, поэтому введем с(х дуг из Хх в в, если дх( О, то удалим — в(х фишек из в введением — бе дуг из эвХл Если дх ) О, то ф(в, Х(Хх)) = О, ф~(в, 0(Хх)) = б;. Если с(; «= О, то ~ф(к, Х(Х;)) = — дь фф(в, 0(Х,)) = О. Если с( ~ = О, то ф(э, Х(Х;)) = О, ф(з, 0(Хх)) = О. При таком построении любая последовательность запуснов переходов, приводящая С~ к маркировке О. приведет С, к маркировке р,' с р, (з) = О (а также и'(р,) = О), и наоборот.
Теорема 5.2. Задача достижимости нуля сводится к задаче достижимости нуля в одной позиции. Доказательство. Формальное доказательство, основанное на описанной конструкции, оставляем читателю. (1 На основе этих двух теорем и очевидных выводов можно заключить следующее: Теорема 5.3. Следукхцне задачи достижимости эквивалентны: 1. Задача достижимости.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
