ВУЗ:
Составители:
Рубрика:
90
выражений
ССФ. Постановка проблемы генерации оптимальных по
сложности выражений ССФ приближена к классической проблеме
оптимальной свертки или факторизации произвольных алгебраических
выражений [82], которая, как известно, принадлежит к NP-трудным
задачам. В этой связи компактные формулы ССФ получаются
непосредственно, минуя трудоемкое формирование развернутого
выражения и не менее сложную последующую его свертку. При этом в
случае свертки выражений ССФ имеется возможность резко повысить как
эффективность генерации, так и качество генерируемых формул.
Общий алгоритм формирования оптимальных выражений
определителей для схем с двухполюсными элементами обсуждался в
подразделе 1.4. Такие схемы изоморфны частному виду унисторного графа
– ненаправленному графу [52]. Однако для схем с УИ, отображаемых
унисторным графом в общем случае, задача формирования оптимальных
выражений до сих пор не имеет удовлетворительного решения. В числе
причин этого можно назвать избыточность унисторного графа при
отображении ИТУН, а также недостаточную эффективность его
обобщений на другие типы УИ [58]. Генерацию выражений ССФ,
свободных от взаимно уничтожающихся слагаемых, можно обеспечить
локализацией подвыражений с параметрами УИ путем первоочередного
выделения параметров двухполюсных элементов. Цель этого подраздела –
развитие метода обобщенного унисторного графа для эффективной
генерации ССФ активных ЛЭЦ в произвольном элементном базисе.
Затраты при непосредственной реализации метода обобщенного
унисторного графа пропорциональны 2
n
, где
n
– число нерегулярных УИ
(то есть УИ, отличных от ИТУН). Однако можно поступить иначе,
использовав обобщенный унисторный граф в сочетании с МСО, основу
которого составляет формула для выделения параметра χ произвольного
УИ (1.3.9).
По существу именно НУИ отображается на обобщенном унисторном
графе «унисторо-подобными» дугами (
k
-, β-,
z
-унисторами) [58]. Проводя
аналогию с НУИ, операции взятия производных по этим дугам можно
сопоставить присвоение им статуса неудаляемых. Это означает, что вес
одной
из
дуг
,
отображающих
некоторый
нерегулярный
УИ
,
обязательно
должен
присутствовать
в
выражении
определителя
соответствующего
графа. Дуги унисторо-подобных элементов назовем неудаляемыми дугами
и будем изображать зачерненной стрелкой, чтобы отличать от обычных
унисторных дуг. Отображение НУИ с помощью неудаляемых дуг на
унисторном графе показано на рис. 1.11.1.
Страницы
- « первая
- ‹ предыдущая
- …
- 88
- 89
- 90
- 91
- 92
- …
- следующая ›
- последняя »
