Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление

^ Лекция 7 Методы на топологических моделях.
Методы на топологических моделях. Представление графов в ЭВМ. Матрицы смежности, изоморфности, достижимости и контрдостижимости, списочные формы. Методы на графах. Методы поиска путей, выделения контуров, поиск касающихся контуров Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление.
^ Задачки анализа топологии
Под топологическим анализом понимается выявление структурных параметров и особенностей модели на основании исследования моделей первого ранга неопределенности Ms(1), т.е. на основании инфы о связи переменных графа.

К главным Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление задачкам анализа топологии, относятся задачки поиска путей, выделения контуров, декомпозиции на подсистемы.

Методы для такового анализа на основании представлений моделей в форме графов либо матричной форме не один раз приводились в литературе. Классические постановки касаются Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление, в главном, линейных систем, составленных из однонаправленных частей.

Методы топологического анализа имеют большущее значение для исследования СС НСУ при помощи ЭВМ, потому что неувязка увеличения эффективности по быстродействию и Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление точности имеющихся способов моделирования может быть решена за счет более полного учета топологических особенностей модели.
^ Представление инфы о топологии моделей
Представление топологии модели может быть в списочной и матричной форме. При организации программных средств Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление почаще употребляется списочная форма. При огромных размерностях одноуровневых очень разряженных моделей она имеет достоинства по требуемой памяти и скорости работы алгоритмов топологического анализа. Но для очень связанных систем маленькой размерности Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление либо иерархических систем эффективнее испробовать методы, основанные на матричных формах, к примеру на матрицах смежности.

В качестве иллюстрации на рис. 23. приведена диаграмма графа модели необычного аттрактора Лоренца. Эта форма представления позволяет эффективнее Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление решать задачки выделения путей и ко­нтуров, связности, структурной маневренности и многие другие, чем в форме НФК и частично СНДУ.

Модель системы представляется нацеленным графом ^ H= с обилием переменных Х=x1, .... , xn, N - общее огромное Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление количество вершин, и обилием дуг G - упорядоченных пар номеров смежных вершин (i,j), G=(i,j)1, ... (i,j)n. Полное количество таких пар обозначено в приме­рах как Q Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление.

Невзирая на всю компактность и удобство таковой записи, на практике почаще употребляют матрицу смежности R = rij, показывающую наличие дуги меж i-ой и j-ой верхушками.



^ Набросок 15 Модель необычного аттрактора в форме нацеленного Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление графа



Набросок 16 Модель системы в форме графа

Другим методом представления топологии является матрица изоморфности D, в строчках которой представлены номера входящих (с плюсом) и выходящих (с минусом) дуг.

Для приведенного на рис. 24 примера матрицы смежности Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление и изоморфности имеют вид:



Избыточность хранимой инфы в матрице смежности (нулевые значения) компенсируют­ся простотой вычислительных алгоритмов и скоростью получения требуемой ин­формации из матрицы. Не считая того, наличие только 2-ух Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление значений 0 либо 1, дает возможность использовать для ее представления битовые поля, что дает значительную экономию памяти, и при размерах системы порядка 100 частей не уступает по затратам ресурсов на хранение матрицы изоморфности, при существенно более Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление обычных алгоритмов обработки инфы. Внедрение матриц смежности, инцидентностей, достижимостей и др. имеет огромное применение для алгоритмов топологи­ческого анализа СС НСУ.

Направленные графы (структурные схемы) обычно обширно применяются при описании Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление линейных систем и систем с одновходовыми нелинейностями. Но появляются некие затруднения при описании нелинейных систем, где нелиней­ные функции могут зависеть от нескольких переменных, к примеру при описании операций умножения и деления Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление.
^ Переборные способы Поиск контуров и путей по матрице смежности
Более обычным методом идентификации путей и контуров являются матричные методы структурного анализа. Они строятся на базе поочередного возведения в надлежащие степени матрицы смежности.

Единица в матрице Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление смежности S гласит о наличии пути меж i й и j-й верхушками длиной 1. Наличие 1 в (i, j)-й позиции в матрицы значит путь длиной 2 меж этими верхушками, и т.д.. Таким Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление макаром, существование ненулевого значения на главной диагонали значит наличие пути из дан­ной верхушки в данную верхушку, длинна которого равна степени матрицы. Значение матрицы смежности в раз­личных степенях для Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление графа, представленного на рис. 25 показаны ниже:



Наличие 1 в главной диагонали показывает на то, что четыре переменные сис­темы входят в контуры длиной 2. Это позволяет найти верхушки, вхо­дящие в контуры, его длину, но не Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление определенный вид. Потому требуется уточняющий переборный метод на отобранных верхушках нелинейного системного гибридного графа, определя­ющего определенный вид контура известной длины. На выходе этого метода формируется дополняемый перечень из номеров вершин, входящих Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление в каждый контур. С учетом различной длины контуров его удобнее представлять в памяти ПЭВМ динамическим перечнем

.

4-ая степень матрицы смежности содержит информацию об еще одном контуре длиной 4. Но не считая Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление этого повторяется информация о кон­турах длиной 2.



Набросок 17 Диаграмма графа одноуровневой модели СУ



^ Набросок 18 Диаграмма графа иерархической модели СУ

Отмеченные особенности этого способа, повторение ин­формации о контурах в матрицах более высочайшего порядка, кратного длине контура; трудности Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление в обработки контуров схожей длины, требуют внедрения, в дополнению к рассматриваемому способу переборного метода, уточняющего и отбрасывающего повторяющую информацию.

Более значимым недочетом данного способа является его низкое быстродействие в следствие огромного Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление количества возведений матрицы смежности в надлежащие степени и огромные издержки памяти ЭВМ для хранения инфы.
^ Измененный метод поиска контуров и путей по матрице смежности
Недочеты метода поиска путей и контуров Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление на основании представления топологии модели в форме матриц смежности, отмеченные выше, могут быть возмещены, если использовать логические операции заместо математических и побитовое представление матрицы смежности. Резвый рост нужной памяти и временных издержек на работу Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление метода с ростом размерности систем в предлагаемом методе компенсируются иерархическим представлением топологии модели а так же иерархическим нравом построения алгоритмов топологического анализа.

Реализация метода в данном случае употребляет не умножение, а логическую операцию Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление И (в матрице находятся только значения 0 и 1), выполняемую одной машинной командой.

Как отмечалось ранее, составной нрав представляемых моделей просит учета наличия связей меж входами и выходами снутри подсистем. С этой целью водится Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление матрица существования связи:

(3.1)

Пример, иллюстрирую­щий данную особенность показан на рис. 26. При формировании матрицы смежности информация о внутренних контурах подсистемы не учитывается, учитывается только информация матрицы J (3.1) существования связи Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление меж входами и выходами подсистемы. Возве­дение в надлежащие степени матрицы смежности S позволяет выделить для данной системы 3 контура.



Логическая сумма, - операции Либо - позволяет найти все возмож­ные связи меж верхушками.

(3.2)

где n - размерность Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление системы и, не считая того, определяет длину макси­мально вероятного пути. Данную сумму именуют матрицей достижимости.

Транспонированная матрица достижимости

, (3.3)

именуемой матрицей контрдостижимостей.

Ниже приведены значения матриц достижимости и контрдостижимос­ти для системы Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление представленной на рис. 26.


.

Если в матрице достижимости бросить только входные и выходные верхушки подсистемы данного уровня иерархии, то получится матрица связей J (3.1), которая должна быть передана в вышестоящую по уровню Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление систему для составления подобных функций структур­ного анализа и учета этой инфы на стадии моделирования.

Блок схема, реализующая предлагаемый метод, показана на рис. 27. Блок 1 делает преобразование из внутренней формы представления нелинейного системного гибридного графа Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление в матрицу смежности размером N * N. Блоки 3 и 4 задают исходные значения матриц контуров С и достижимости R. Блоки 4,5,15 организуют основной цикл. Блок 6 вычисляет i-ю степень матрицы смежности, перемножение производится логической операцией Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление “И”. Блок 7 делает скопление инфы о всех вероятных путях в матрице достижимости, суммирование делается ло­гической операцией “Либо”. Блоки 8,9,14 организуют цикл проверки вершин на принадлежность к контурам. В этом цикле перебираются элементы глав Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление­ной диагонали матрицы . Если верхушка j относится к контуру, длиной i (блок 10), то в блоке 11 переборными способами этот контур выделяется. Выделенный контур, в блоке 12, сравнивается с уже существующими, хра­нящимися Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление в перечне контуров С. Если контур новый, то он добавляется к списку (блок 13). После окончания основного цикла, рассчитывается матри­ца контрдостижимости Q (блок 16) и матрица связей в системе (подсистеме) J (блок 17), после Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление этого метод завершает свою работу. Выходными параметрами, возвращаемыми в вызвавшую программку, являются матрицы R,Q, J, C.




Набросок 19 Блок-схема и пример работы программки выделения контуров
^ Поиск контуров и путей по матрице изоморфности

6

. 5. Диаграмма графа Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление


Набросок 20Диаграмма графа

Матрица изоморфности D

-1

7







-2

1

6




-3

2







3

5

-4




4

-8







8

-5

-6

-9

9

-7








Метод идентификации контуров последующий:

Просмотреть строчки матрицы. Для i-й строчки просмотреть элементы до обнаружения отрицательного элемента Di j <0. Уяснить номер строчки и значение элемента Di j Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление.

Отыскать строчки в матрице содержащие элемента D k l == - Di j. Для каждой отысканной строчки выполнить пп. 1, до того времени пока в отысканной последовательности повторно не крутится уже обнаруженная дуга, либо программке Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление не получится найти новейшую дугу, выходящую из этой верхушки.

Пример для графа, представленного на рис. 28.

  1. В 0-й строке отыскал D[0][0]= -1 ;

  2. Отыскал D[1][1]= 1 ;

  3. В 1-й строке отыскал новый отрицательный элемент D Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление[1][0] = -2 ;

  4. Отыскал D[2][1]= 2 ;

  5. В 2-й строке отыскал новый отрицательный элемент D[2][0] = -3 ;

  6. Отыскал D[3][0] = 3 ;

  7. В 3-й строке отыскал новый отрицательный элемент D[3][2] = -4 ;

  8. Отыскал D[4][0]= 4 ;

  9. В 4-й строке отыскал новые отрицательные элементы D[4][1] = -5, D[4][1] = -6, D[4][1] = -9. Нужно Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление разветвить поиск ;

  10. Отыскал D[3][1]= 5 ;

  11. В 3-й строке отыскал отрицательный элемент D[3][2] = -4. Этот элемент уже был в цепочки поиска. Поиск по этой ветки прекращен. Возвращаемся в пп.9 ;

  12. Отыскал D[1][2]= 6 ;

  13. В 1-й строке Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление отыскал отрицательный элемент D[1][0] = -2. Этот элемент уже был в цепочки поиска. Поиск по этой ветки прекращен. Возвращаемся в пп.9 ;

  14. Отыскал D[6][0]= 9 ;

  15. В 6-й строке отыскал новый отрицательный элемент D[6][1] = -7 ;

  16. Отыскал D[0][1]= 7 ;

  17. В 0-й строке отыскал Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление D[0][0]= -1. Этот элемент уже был в цепочки поиска. Поиск по этой ветки прекращен.

  18. Новых отрицательных частей в матрице не осталось поиск прекращен.

После окончания поиска имеем:

-1

-2

-3

-4

-8




-5

-4

















































-6

-2

















































-9

-7

-1

По данным этого Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление перечня составляем контура.

Обычно в литературе указывается на высшую эффективность данного метода. Он вправду смотрится до боли просто и наглядно. Но при его реализации придется организовывать разветвление работы метода. Это можно сделать или через рекурсию Лекция 7 Алгоритмы на топологических моделях - Курс лекций Составитель Соркина В. Е. Оглавление, или организовать запоминание дерева перебора и незавершенные точки перебора. Что приводит к значимым затратам ресурсов ЭВМ, не учитывающихся большинством создателей анализирующих эффективность данного метода.


lekciya-51-individ-i-lichnost-lekciya-psihicheskie-yavleniya-i-zhiznennie-processi.html
lekciya-52-topograficheskaya-semka.html
lekciya-541-velikie-geograficheskie-otkritiya-uchebno-metodicheskij-kompleks-disciplini-istoriya-srednih-vekov-po.html