Алгоритм выделения путей

Алгоритм выделения путей (АВП) в разомкнутом графе выделяет все пути, связывающие заданную пару вершин. [c.52]

АЛГОРИТМ ВЫДЕЛЕНИЯ ПУТЕЙ [c.60]

Пусть в графе имеются входная (Ь,) и выходная (а,) вершины. Алгоритм выделения путей АВП состоит из двух частей. Первая часть (АВП I) будет выделять в графе совокупность вершин 5 (а , Ь,), входящих во все пути, которые связывают вершину 6 с вершиной а,-. Вторая часть (АВП II) на основе совокупности 5 (а,, Ь,) будет уже непосредственно выделять пути, связывающие вершину Ъ[ с вершиной а,-. Начнем с описания первой части. [c.60]

Перейдем теперь к описанию второй части алгоритма выделения путей. [c.68]

Опишем теперь коротко алгоритм выделения путей (АВП). Будем предполагать для определенности, что определяется совокупность 5 ( a , ), т.е. совокупность вершин, входящих в пути, связывающие i с. АВП анализирует каждую вершину графа, начиная с вершины. Переход от одной вершины к другой происходит в соответствие с направлением дуги, связывающей эти вершины. Особо надо остановиться на переходе из разъединительной вершины. Эта вершина имеет несколько выходных дуг, и поэтому из нее можно перейти [c.86]

Комплекс алгоритмов решения сигнальных графов ХТС с использованием универсальной топологической формулы, которая обеспечивает близкий к минимальному объем вычислительных операций ЦВМ, включает следующие алгоритмы 1) алгоритм выделения прямых путей от вершин-источников графа 2) алгоритм выделения элементарных контуров графа 3) алгоритм определения комбинаций некасающихся контуров 4) алгоритм расчета коэффициентов передач для числителя знаменателя (определителя [c.99]

Один из первых алгоритмов выделения комплексов был предложен в работе [1 ]. В его основе лежат операции с матрицей связей А с целью выделения на графе ХТС путей различной длины и построения матрицы комплексов. [c.45]

Для обнаружения важных признаков подлежащие классификации объекты сравнивались с эталонами и прототипами. Такое сравнение проводилось интерактивными методами, иногда с использованием средств графического отображения. Предпринимались попытки определять, например, статистические параметры, такие, как моменты и гистограммы, путем непосредственной обработки образов. Из сказанного выше очевидно, что существует множество алгоритмов выделения признаков в процессе предварительной обработки информации их число непрерывно и быстро растет, поскольку выбор способов решения конкретной задачи в большой степени обусловлен характером самой задачи. Успех всего исследования по проблеме распознавания образов определяется тем, насколько удачно выполнен этап выделения признаков. Общее признание получила точка зрения, согласно которой новых крупных достижений в этой области следует ожидать как раз на стадии выделения признаков при предварительной обработке информации. [c.14]

Процедуры блоков определения Д, А -, С,,, выделения всех путей от входа к выходу и нахождения С по различным каналам в общем алгоритме (см. рис. 3.22) аналогичны соответствующим процедурам левой ветви для сигнальных графов (см. 3.5). [c.238]

База данных — О хранит фактографическую и числовую информацию, поступающую с реальной ГТС, результаты решения математических задач, данные, полученные от ЛПР, а также ретроспективные данные, позволяющие ИАССУ решать задачи прогноза ситуации и состояния ГТС. Поиск решений в ИАССУ обеспечивается блоком анализа ситуаций — .V и блоком вывода управляющих решений — У , которые составляют двухэтапную процедуру смыслового, или логического, вывода, реализуемого в блоке вывода К . На первом этапе на основе данных из БД осуществляется семантический и смысловой анализ нестандартных ситуаций, начиная с нижнего уровня ГТС, где путем анализа БЗ формируется обобщенное описание ситуаций для сложных элементов ГТС к верхнему уровню, на котором проводится смысловой анализ ситуации в ГТС в целом. В результате смыслового анализа ситуаций с использованием предикатно-фреймовой модели, выполненного в блоке .V , ЛПР может получить список возможных неисправностей в ГТС и причин их появления. На втором этапе процедуры вывода, по смысловому описанию ситуации в ГТС в интерактивном режиме с ЛПР выбираются критерии управления сложными элементами, в соответствии с которыми генерируются конкретные управляющие решения. Выделение процедур вывода управляющих решений и анализа ситуаций в самостоятельные блоки дает возможность программно реализовать в ИАССУ различные стратегии вывоДа решения. В результате этого в ИАССУ знания отделяются от способа их переработки, что позволяет качественно изменять и настраивать эвристический алгоритм функционирования ИАССУ при изменении ситуации и условий работы ГТС, а также обеспечить перенастройку семиотической модели ГТС. В результате работы ИАССУ для ЛПР-диспетчера генерируются рекомендации по управлению ГТС и конкретным способам их реализации, которые представлены в виде фраз и текстов на ОЕЯ. Например, при необходимости Для ГТС увеличить подачу газа потребителю ИАССУ может рекомендовать диспетчеру ПО увеличить давление нагнетания КС, а диспетчеру КС —какие обороты ГПА при этом необходимо поддерживать. [c.271]

Анализ корректности вычислений на УВМ, выполняемых в процессе реализации разработанного алгоритма управления, является необходимым этапом разработки АСУ. Этот анализ позволяет не только сформулировать технические требования к разрядности используемой в АСУ УВМ, но также, что более важно, для уже выбранной УВМ разумно организовать процесс вычислений. Проблему достижения необходимой точности вычислений при заданной разрядности УВМ часто удается решить путем выделения участков алгоритмов, которые будут выполняться на УВМ с двойной точностью, или путем подбора подходящего численного метода. [c.205]

С учетом указанных особенностей выделение необходимой информации о состоянии ОК осуществляется путем создания алгоритмов обработки информации о флуктуирующем значении его сопротивления (проводимости), адаптированных к имеющему место в ОК или создаваемому при диагностировании характеру его нагружения. [c.530]

С учетом указанных особенностей выделение необходимой информации о состоянии объекта осуществляется путем создания алгоритмов обработки информации [c.476]

Работа первой части алгоритма состоит в последовательном построении цепей до зацикливания . Каждое зацикливание позволяет выделить новый элементарный контур. После прохождения всех возможных путей все элементарные контуры окажутся выделенными. [c.109]

Для этих алгоритмов характерно следующее применение принципа структурного ограничения информационных ситуаций для уменьшения количества переборов (например, близость режимов во времени для различных классов) выявление и оперирование с той частью двоичного кода, по которой различаются режимы (вычеркивание несущественных разрядов) достижение цели путем подстановки подцелей (в нашем случае выделение первого разряда, затем проверка и т. д.) нечувствительность к утрате подробностей описания объектов (например, переключение внимания алгоритма на отдельные части двоичного кода) возвращение назад пересмотр путей дальнейшего продвижения иное формулирование подцелей в зависимости от полученных результатов. [c.96]

Вторым этапом является синтез молекулы из совокупности фрагментов, определенных на предыдущем этапе. Эта задача чрезвычайно сложна для ЭВМ, так как не поддается пока полной алгоритмизации. Частичная автоматизация достигается использованием правил валентности, которые позволяют уменьшить перебор возможных сочетаний выделенных группировок. Наиболее целесообразным, по нашему мнению, сейчас является режим диалога человека с машиной, при котором химик, основываясь на своих знаниях строения химических соединений, указывает машине порядок соединения группировок в молекулу. Конструирование же пространственной структуры молекулы тогда может быть осуществлено автоматическим путем на основании библиотеки стандартных фрагментов, в которой хранится и информация о геометрии этих фрагментов. Алгоритм программы такого рода описан в работе [4]. [c.349]

В дальнейших исследованиях посвященных эффективному использованию a(N0g)2, выделенного из азотнокислотного раствора, полученного при разложении фосфоритов, было предложено осуществлять обмен ионов кальция на ионы калия на катионите КУ-2. Авторами составлен алгоритм математической модели процесса, который реализован на ЭВМ Проминь-2 , получены численные значения выходных кривых, расчетным путем определены оптимальные режимы получения калийной селитры и предложена новая технологическая схема процесса. [c.145]

Рис. 27. Блок-схема АВГТ1 (первой части алгоритма выделения путей, связывающих две вершины в разомкнутом графе).

Кроме того, для работы алгоритма требуется знание некоторого количества пар вершин ( а ,, ), обладающих тем свойством, что если одновременно разорвать дуги, связывающие вершины a я, то граф станет разомкнутым. В схеме рис.1 можно выделить Ч- пары таких вершин (3,4), (8,9) (11,12), (15,16). Дуги, связывающие вершины a и i ( (/ =1,..., по) будем называть особыми. Метод выделения совокупности особых дуг будет рассмотрен нами ниже. Итак, алгоритм выделения комплексов будет следующим. Вначале в графе разрываются все выде -ленные особые дуги, в результате чего замкнутый граф превратится в разомкнутый. Далее берем первую пару вершин ив разомкнутом графе ищем все пути, идущие из в а<. Совокуп -ность вершин, входящих во все пути обозначим через 8 ( в, ). [c.84]

Алгоритм выделения признаков применяют следующим образом. Выбрав то или иное положение mie и порог интенсивности, берут обучающую выборку молекулярных структур и подразделяют ее на две категории. Соединения, характеризующиеся пиком достаточной интенсивности при этом положении т/е, хранят как один класс образов, называемый первой категорией. Соединения же, для которых в данном положении пик достаточной высоты отсутствует, хранят как второй класс образов, называемый второй категорией. Затем каждый класс образов раздельно предъявляют подпрограмме выделения признаков. Таким путем составляют набор признаков, общий для пиковых соединений, и другой набор, общий для беспиковых соединений. [c.200]

Другой путь повышения адаптивности заключается в двухуровневой организации, охватываюш,ей с единой методологической точки зрения любой структурно-химический объект информационной системы. В этом случае с помощью алгоритмов автоматического индексирования для каждой структурной формулы генерируется вторичная дополнительная запись, приспособленная к массовым структурно-химическим задачам. В гл. IV подобные вторичные записи были названы дополнительными кодами . Таким образом, алгоритмы автоматического индексирования являются средством повышения адаптивности при сохранении универсальности автоматизированных информационных систем. Задача автоматического индексирования структурных формул органических соединений есть частный случай более общей проблемы автоматического индексирования текстов. Касаясь этой общности, Кент [77] отмечал, что и в том и в другом случае цель индексирования заключается в выделении признаков, пригодных для информационного поиска. В связи с этим небезынтересно отметить, что сотрудник фирмы IBM Лун, известный своими работами в области автоматического индексирования текстов, разработал также систему кодировапия ациклических цепей (в частности, структурных формул органических соединений), основанную на учете статистического распределения узлов в структурной формуле. [c.118]

В последние годы при разработке фреймовых ЯПЗ для математической формализации ФР используют A- < i v h [13,15, 82, 83]. Каждому <1 Р соответствует свое -опрсдсяснио> ( выражение ). В основе разработанного формализованного языка представления ФР лежит использование Х-конверсии , основными достоинствами которой являются простота понимания и универсальность. В данной системе поддерживается предикатная трактовка ФР и конкретизируется его понятие. ФР рассматривается как ориентированный граф, в котором помечены вершины и дуги. Одна из вершин выделена для предикатного символа. Остальные вершины предназначены для ар17ментов, находящихся в некотором падежном отношении (метка на дуге) с выделенным предикатом. Каждая вершина имеет область допустимых значений, называемую сортом. Сорта, или типы, переменных используются в МПЗ для повышения эффективности алгоритмов поиска знаний и вывода решений (83[. В исчислении предикатов сорта переменных не рассматриваются, а поэтому исчисление предикатов мол/сно рассматривать как односортную логику. С принципиальной точки зрения, сорта переменных могут быть исключены путем введения соответствующих одноместных предикатов. Однако с введением таких дополнительных предикатов падает эффективность алгоритмов поиска решений и вывода. [c.240]

Обозначим через Ql множество, элементами которого являются все разъединительные вершины, встретившиеся АВП I за шагов. Если разъединительная вершина к Qi, то в этом множестве она останется до тех пор, пока не будут пройдены все ее выходные дуги. Если вершина к внесена в Q , это значит, что существует путь, связывающий вершину с вершиной к. Отсюда ясен смысл построения множества 3. Пусть выделена какая-то совокупность путей, соеди-няющрх с а,. Если бы не было множества Д я выделения каждого следующего пути надо было бы всегда начинать анализ графа с вершины Ь,.. Это не очень экономно, поскольку пришлось бы много раз проходить одни и те же вершины. Наличие множества сделает алгоритм более экономным, так как позволит при выделении очередного пути начинать анализ не с вершины а с разъединительных вершин, запомненных в множестве 2- [c.61]

Алгоритм Форда-Беллмана обычно называют алгоритмом динамического программирования. Время его работы пропорционально кубу количества вершин в фафе - крутятся три вложенных цикла. Он выдаёт минимальную стоимость пути из какой-то выделенной вершины во все остальные. [c.166]

Для информационных запросов, относящихся к выделенным классам, следует использовать автономные специализированные ИПС, работающие со специализированными ИПЯ и алгоритмами. Наряду с этим преимущественно путем автоматического перевода на универсальный ИПЯ содержи-люго памяти специализированных ИПС должен накапливаться информационный массив универсальной ИПС, работающей с алгоритмами универсального типа и эксплуатируемой для немногочисленных за просов, относящихся к невыделенной части множества органических соединений. Такую структуру, образованную комплексом специализированных и универсальной ИПС, с возможной многоступенчатой иерархией, мы предлагаем называть федеративной структурой [20]. В подобных федер5ативных структу-рах, на нагп взгляд, кроется существенный резерв повышения экономической целесообразности информационных систем органической химнн. [c.46]

Могут быть высказаны соображения об усовергаенствовапии описанного алгоритма. В первую очередь желательно устранить те трудности, которые возникают нри выделении изменяющихся кратных связей. Эти трудности могут привести к тому, что для двух реакций с одинаковыми скелетными схемами будут выработаны разные наборы квазиизменяющихся связей, что и вызвало необходимость отказа от автоматического индексирования части реакций. Более простой путь устранения этих трудностей состоит в отказе от индексирования характера изменений кратности связей. Это значит, что при вычислении брутто-формул связей левой и правой частей уравнения не делается различие между связями 8 ах 8 и Зга З), т. е. все связи рассматриваются как имеющие одинаковую кратность, а — = 2 = Тогда алгебраическим вычитанием мы получим только целиком образующиеся и целиком разрывающиеся связи. Поисковые образы, состоящие только из таких связей, будут компактнее, но менее специфичны. Другой нуть устранения трудностей связан с отказом от вычисления и отражения в поисковом образе значения коэффициентов р, т. е. от применения второй части алгоритма. Полученные поисковые образы будут менее химически точными. [c.271]

Справочник химика 21

Химия и химическая технология