Упрощение - граф
Cтраница 3
Если коэффициенты передачи ветвей исходного графа в свою очередь могут быть представлены графами, то эти специальные подпрограммы сами содержат программу команд и новые подпрограммы. Программа команд, очевидно, и в этом случае будет той же, поскольку задача по-прежнему состоит в упрощении графа. [31]
Направленные графы, которые, как было установлено, получаются сравнительно простыми формальными приемами для любой физической системы, заданной в виде схемы замещения, лепко могут быть заложены в память цифровой автоматической вычислительной машины. Вершины графа, перенумерованные в определенном порядке, будут представлены ячейками оамяти машины, а коэффициенты передачи ветвей графа - содержимым этих ячеек. С другой стороны, упрощение графа сводится главным образом к вычислению конечных коэффициентов передачи между некоторыми вершинами его, и мы можем запрограммировать эти вычисления на цифровой машине. [32]
Этим более сложным элементарным графам соответствуют решающие блоки, включающие несколько усилителей, интеграторов и функциональных преобразователей, кроме описанных выше простейших решающих элементов. Тем не менее новые элементарные структуры соединяются столь же просто, как и графы четырехполюсников, как было показано в гл. Если нет необходимости удерживать все переменные, то эти графы могут быть свернуты в соответствии с описанными ранее методами упрощения графов. Однако в процессе указанных упрощений должны быть сохранены вершины на концах всех ветвей с нелинейными коэффициентами передачи. [33]
Рассмотренное нами исследование обратной связи с помощью направленных графов не вносит элементов существенной новизны в сложившую. Метод графов интересен прежде всего с точки зрения возможности простой и изящной интерпретации классических результатов. Конечные графы позволяют непосредственно вскрыть некоторые связи и являются простым и легко обозримым графическим языком в сравнении с аналитическими выражениями Боде, полученными через определители и миноры. В поставленной задаче упрощение графа естественным образом приводит к конечным графам, при наличии которых формулирование теорем в некотором роде уже не столь необходимо. Направленные графы во многих задачах позволяют обнаружить обратные связи с помощью контуров графа и применить классические теоремы теории цепей, тогда как при любом другом подходе к задаче столь же легко выявить обратные связи не представляется возможным. [34]
Алгебра линейных графов позволяет различными путями упрощать задачи. При этом выражение искомой зависимой переменной записывается в функции независимых переменных на основе выявления и нумерации всех петель и разомкнутых путей графа. В ряде случаев прямому решению следует предпочесть метод упрощения графа сведением его к нескольким существенным элементам. [35]
В этом случае необходимо записать уравнения относительно переменных, определенных на п зажимах схемы. Нормализующими множителями оказываются при этом входные проводимости или входные сопротивления л-полюсника, а коэффициенты передачи ветвей графа суть передаточные функции системы, деленные на нормализующие множители тех вершин графа, в которые заходят данные ветви. Граф соответствует свернутым уравнениям и может быть получен путем упрощения детализированного графа ( такого, например, как показанный на рис. 3 - 1, в) в соответствии с изложенными ранее правилами. Элементарные контуры, которые могут появиться в процессе упрощения, необходимо устранить, сохранив в конечном графе только нормализованные коэффициенты передачи. [36]
 |
Простейшие преобразования. [37] |
Этот метод родствен методу последовательного исключения из уравнения нежелательных неизвестных. Переменную можно исключить, устранив из графа вершину, соответствующую этой переменной. Продолжая упрощения достаточно далеко, можно прийти к решению графа относительно некоторой одной переменной. Именно эту конечную цель мы имеет в виду, излагая здесь различные методы упрощения графов. На практике, однако, техника упрощения будет использоваться нами исключительно с целью преобразования графа к виду, позволяющему вскрыть нужные связи, тогда как полное решение мы будем получать по правилу Мейсона. [38]
Доказана полнота и состоятельность процедуры вывода на графе связей. Вышеприведенный алгоритм является недетерминированным. Для реализации его на детерминированной машине он нуждается в детерминированной процедуре выбора резольвируемой связи. В данном вопросе возможно использование нескольких основных методик, например, выбор связи, активация которой приведет к уменьшению количества дизъюнктов в графе, количества связей или количества вхождений предикатов в дизъюнкты. Также к упрощению графа приводит слияние одинаковых предикатов из дизъюнктов-родителей. Еще одним фактором, влияющим на выбор связи, является единственность связи для предиката, что приводит, как сказано ранее, к удалению дизъюнкта, содержащего этот предикат после резольвирования. В случае, когда упрощения графа добиться не удается, следует выбрать связь, резольвирование которой приведет к минимальному усложнению графа связей. [39]
Доказана полнота и состоятельность процедуры вывода на графе связей. Вышеприведенный алгоритм является недетерминированным. Для реализации его на детерминированной машине он нуждается в детерминированной процедуре выбора резольвируемой связи. В данном вопросе возможно использование нескольких основных методик, например, выбор связи, активация которой приведет к уменьшению количества дизъюнктов в графе, количества связей или количества вхождений предикатов в дизъюнкты. Также к упрощению графа приводит слияние одинаковых предикатов из дизъюнктов-родителей. Еще одним фактором, влияющим на выбор связи, является единственность связи для предиката, что приводит, как сказано ранее, к удалению дизъюнкта, содержащего этот предикат после резольвирования. В случае, когда упрощения графа добиться не удается, следует выбрать связь, резольвирование которой приведет к минимальному усложнению графа связей. [40]
Мы можем резольвировать любую пару дизъюнктов, соединенных ребром, так как все ребра соединяют контрарные пары. Резольвента всегда наследует связи, соединяющие литеры-вершины дизъюнктов, инцидентных резольвированной связи. Использованная единожды связь удаляется из графа, чем достигается ограничение излишней резолюции между данной парой дизъюнктов. Множество дизъюнктов, соответствующее графу связей, невыполнимо, если мы можем вывести пустой дизъюнкт из графа связей. Связи графа могут быть выделены сверху вниз, снизу вверх или комбинацией обоих методов. Поскольку все пространство поиска проблемы известно, то на каждом шаге мы можем использовать эвристическую информацию, чтобы выделить лучших кандидатов на ре-зольвирование. Для повышения эффективности вывода используются различные стратегии упрощения графа связей, такие как удаление чистых дизъюнктов, тавтологий и поглощенных дизъюнктов. [41]
Страницы: 1 2 3