Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 20
Текст из файла (страница 20)
4А. Темы для дальнейшего изучения 1. Рассмотрите построение не дерева, а графа достижимости. Если вершина х порождает последующую вершину я с 1с[г] = 1с[у] для некоторой неграничной вершины у, просто введите помеченную соответствующим образом дугу из х и у. Заметим, что путь из корня в вершину перестает быть единственным. Опишите алгоритм построения графа достижимости, покажите, что он сходится, н исследуйте его свойства, сравнивая с алгоритмом построения дерева достижимости. 2. Дерево достижимости нельзя использовать для решения проблемы достижимости вследствие потери информации, порождаемой символом се.
Он вводится, когда мы приходим к маркировке и' и на пути от корня к )с' имеется такая маркировка 1л, что р,' > 1с. В этом ыг г случае можно получить все маркировки вида р + п(1~' — р). Исследуйте возможность использования выражения а+ Ь ° п, вместо ы, для того чтобы представить значения компонент.
Если вы сможете определить дерево достижнмости, в котором все векторы маркировок представляются выражениями, тогда решение задачи достижимости определяется просто решением системы уравнений. 3. Обобщите определение сохранения, разрешая отрицательные веса. Что можно было бы считать разумной интерпретацией отрицательного веса? Является ли разрешимой задача определения сохранения сети Петри.
если разрешены отрицательные весаэ 4. Разработайте с помощью матричного подхода к анализу алгоритм определения ограниченности сети Петри (61). 5. Основная проблема матричного анализа — отсутствие информации о последовательности и существование недействительных решений. Однако задача достнжимости является самой существенной для сетей Петри, поэтому важно показать, что она разрешима, даже если решения вычислительно дороги. Если задача разрешима, можно будет искать более эффективные методы решения, но сначала необходимо показать, что метод решения существует.
Для обоснования этого обозначим через Х сумму вектора запуска ~ по всем компонентам. Иначе говоря, если ! == (Л. !м ° 1 ). то Хг = Г~+ )а+ ... + ~ ..((алев, если существует последовательность о, переводящая сеть Петри из маркировки ц в маркировку р', тогда уравнение (4-!) имеет решение, являкхцееся вектором запуска 1(о) для а. Последовательность о можно определить из вектора запуска Да) простым перебором всех возможных последовательностей длины Х яки стараясь, чтобы каждая из них 1) была действительной и 2) приводила от р к р'. Для сети Петри с т переходами возможно самое большое вРУ последовательностей длины Хг.
На самом деле это число можно сократить. Поскольку нам известно, сколько раз запускается переход 1, (),), сколько раз запускается 1, Щ и т. д, то необходимо проверять не более чем Х!! жпможных упорядочений из ~, запусков перехода !ь ~, запусков перехода !з и т. д.
Это, казалось бы, обеспечивает процедуру решения задачи опре. деления„является ли р' достижимой из р. Сначала решаем матричное уравнение р' = р + ! ° Р. Если решения не существует, р' недостижима из и. Если решение ) существует, проверяем все Х ! вспможных упорядочений переходов. Если какая-нибудь из этих последовательностей действительна, то р' достижима нз р, и мы имеем последовательность переходов, переводящую из р в р'.
Имеется только одно препятстн!е. Решение ! может быть не однозначным, а (бесконечным) множеством векторов запусков, представленным множеством выражений (как показано выше для примера анализа сети Петри на рис. 4.27). Лля определения возможности доказательства достижимости в этом случае необходимы исследонания В простейшем случае может оказаться, что или все решения представляются выражением вектора запуска, соответствующим действительным решениям, или ии одно.
В этом случае мы просто выбираем любое решение и выполняем описанную процедуру проверки всех возможных упорядочений. Белее вероятно, однако, что некоторые решения будут работать, тогда как другие — нет. Так как мы не можем испытат все решения (из, возможно, бесконечного множества их), необходимы исследования, для того чтобы можно было определить, какие решения необходимо проверять. ГЛАВА 5 СээОЖНОСТЬ И РАЗРЕШИМОСТЬ В четвертой главе было представлено множество задач теории сетей Петри. Этн задачи касаются различных свойств сгрунтуры и поведения сетей Петри.
Были представлены и два метода решения: подход дерева достижимости и подход матричных уравнений. Эти методы позволяют определить свойства безопасности, ограниченности, сохранения и поирываемости для сетей Петри. Кроме того, установлены необходимые условия для достижимости. Однано этн методы анализа недостаточны для решения некоторых других задач, в частности антивности, достижнмости и эквивалентности. В этой глане мы изучим эти задачи с целью или найти нх решения, илп по нрайней мере узнать больше о свойствах сетей Петри. $Л. Саоднмость задач анализа Мы будем использовать фундаментальное понятие оюдимости [(46).
Решение задачи подразумевает сведение ее к другой задаче, способ решения которой уже известен. В предыдущей главе, например, задача определения того, является ли сеть Петри сохраняющей, сводилась к решению системы линейных уравнений. Задача решения системы линейных уравнений в свою очередь сводится к определенной последовательности арифметических операций (сложение, вычитание, умножение, деление и сравнение). Таким образом, поскольку арифметические операции выполнить можно, сохранение может быть определено. Другой пример связан с задачей равенства и задачей подмножества для множеств достижимости.
Определение 5.1. Задача роаенспгва. Выполняется ли для двух данных маркированных сетей Петри Сг —— (Р„Т„1„0,) с маркировкой р, и С = (Р„Т„1„0,) с маркировкой р, равенство )г(Сь Рь) = Ю(С., Р)р Определение 5.2. Задача подмножества. Выполняется ли для двух данных маркированных сетей Петри С, = (Ро Ть 1ы Ог) с маркировкой р, н С, = (Р„Т„1„0 ) с маркировкой и соотношение Л(С„Р,) = ЦС„Р,)." Эти задачи могут оказаться очень важными для определения, является ли сеть Петри оптимизируемой или сравнимы ли сети двух систем. Заметим, что если можно найти решение задачи подмножества, то задача равенства также решается. Если необходимо Слозснооть и разреыимость определить, выполняется ли К(Со 1з,) =- ??(С„ра), мы сначала применим алгоритм решения задачи подмножества для определения, выполняется ли ??(Со (з,) .
К(Ся, 1сз), а затем применим тот же алгоритм для определения, выполняется ли гг(С„рз) ш ??(Со р,). ??(Сь )з,) =- Р(С„ре) тогда и только тогда, когда К(С„ р,) ш тг(Сз, рз) и ЦС„рД ш ??(Со рз). Таким образом, задачу равенства можно сеести к задаче подмножества. При рассмотрении задач анализа и сводимости важно принимать во внимание следующие два соображения. Во-первых, пытаясь найти решение, необходимо учитывать в<выожность того, что задача яе имеет метода решения, т. е.
неразрешима. Во-вторых, если метод решения существует, мы должны оценить его стоимость: как много времени и памяти требуется для решения? Для того чтобы применение сетей Петри расширялось, задачи анализа должны решаться, а алгоритмы, осуществляющие решение, должны быть не слишком дброги в смысле времени и памяти ЭВМ. Сводимость играет большую раль для обеих из указанных проблем. Сводимость задач обычно используется для того, чтобы показать, разрешима ли задача или неразрешима. Наш подход к теории разреишмости [69, 200) о"нован главным образом на работах Тьюринга и его модели вычислений — машине Тьюринга.
Значение машины Тьюринга состоит в том, что она служит разумным представлением вычислительной машины, и можно показатьп, что не существует алгоритма, который бы решал определенные проблемы машины Тьюринга, в частности проблему остановки. На основе этого был найден ряд неразрешимых задач. И важностьэтой теории— в том, что невозможно создать программу для ЭВМ, которая бы решала эти задачи.
Следовательно, для целей практического анализа необходимо избежать этих неразрешимых задач, иначе вопросы анализа ие получат ответа. (Здесь важно подчеркнуть, что неразрешимые задачи порождают вопросы, на которые не просто пет ответа, по его и не зсозгетп бмсль. Вопросы, на которые нет ответа, еще могут его получить; это значит, что ответ еще никто ие нашел, ио он существует.
Известным примером является болыцая теорема Ферма: имеет ли решение уравнение х" + у" = г' для п ) 2 в классе целых чисел х„у, г? Этот вопрос не получил ответа,но он его имеет. Ответом служит либо"да". либо "нет". Одним способом получения ответа на вопрос является поиск чисел х, у,г и п, удовлетворяюп1их условиям теоремы. Другим будет доказательство (логический вывод) того, что таких х, у, г и п не существует.
Никто еще не сделал этого. Однако предположим, что задача неразрешима. Тогда невозможно было бы определить, существуют ли х,у,г и и, решающие уравнение. Это означало бы, что мы не могли логически вывестп их несуществование из аксиом математики и не могли получить х,у, И для аекогорых задач, разуыеетея. — Прим. иерее. Глава 5 г и л, которые были бы решением уравнения. Но если мы не можем получить х, у, г и п, тогда они не должны существовать. Если же они существуют, мы можем найти их с помощью ЭВМ. Но если х, у, г и п не существуют, ответом на вопрос будет «нет», и, следовательно, мы разрешили его. Это противоречит нашему предположению о том, что вопрос неразрешим, следовательно, он разрешим.) Теперь допустим, что задача А сводима к задаче В: конкретную задачу А можно перевести в конкретную задачу В.
Если задача В разрешима, то разрешима и задача А, а алгоритм решения задачи В можно применить к решению задачи А. Конкретную задачу А можно решить, преобразуя ее в конкретную задачу В и применяя к ней алгоритм решения задачи В. Таким образом, если задача А сводится к задаче В и задача В разрешима, то разрешима и задача А Обратное также верно: если задача А сводится к задаче В и задача А неразрешима, то неразрешима и задача В; если бы задача В была разрешима,то описанная выше процедура была бы методом решения задачи А, что противоречит ее неразрешимости.
Этн два факта положены в основу большинства методов определения разрешимости. Для того чтобы показать, что задача разрешима, сводят ее к задаче, известной как разрешимая; а для того чтобы показать, что задача неразрешима, сводят к ней задачу, которая известна как неразрешимая. Мы также будем широко использовать этот подход для сокращения объема работы, которую нам необходимо выполнить. Например, вследствие того, что задача равенства для множеств достижимости сводится к задаче подмножества, мы хотим найти либо !) процедуру решения задачи подмножества, либо 2) доказательство того, что задача равенства неразрешима.
Если мы смсокем выполнить 1), то будем иметь метод решения обеих задач, если выполним 2), будем знать, что обе задачи неразрешимы. В некоторых случаях мы сможем достичь даже большего. Две задачи называются эквивалентными, если они взаимно сводимы. Другими словами, задача А эквивалентна задаче В, если задача А сводится к задаче В, а задача В сводится к задаче А.
В этом случае или обе задачи разрешимы, или обе неразрешимы, и мы можем рассматривать .нюбую из них. 13аметим, что в общем случае эгон неверно Например, если бы мы показали, что з дача подмножества для множествдостнжимости неразрешима, это не сказало бы нам ничего о разрешимости или неразрешимости задачи равенства.) Второе соображение по исследованию задач анализа заключается в том, что если метод решения существует, то он должен быть разумно эффективным. Это означает, что количества времени и памяти, требуемые алгоритмом для решения конкретной задачи, не должны быть чрезмерными. Исследование стоимости выполнения алгоритма — это часть теории слояеносни.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
