Переборный алгоритм

Cтраница 1

Переборные алгоритмы реализуют такую последовательность процедур: генерирование очередного варианта - оценка качества варианта - принятие решения. Суть метода заключается в построении морфологической таблицы, строки которой содержат варианты исполнения объекта конструирования, а число столбцов равно числу элементов, составляющих объект. [1]

Классификация алгоритмов структурного синтеза. [2]

Переборные алгоритмы характеризуются возможностями оценки только вариантов готовых законченных структур. Такие структуры либо создаются заранее и хранятся в базе данных, либо генерируются по тем или иным правилам из заданного набора элементов. Полный перебор вариантов возможен лишь в простейших случаях. Переборные алгоритмы включают в себя части: 1) выбора или генерации очередного варианта; 2) оценки варианта; 3) принятия решения. [3]

Такой чисто переборный алгоритм может быть улучшен применительно к различным конкретным вариантам задач поиска путей синтеза. Например, если необходимо найти диаграмму синтеза заданного соединения ие некоторого допустимого набора исходных веществ при дополнительном условии минимальности числа стадий синтеза, можно использовать прием; встречных потоков, предназначенный для нахождения кратчайшего в -, лабиринте пути, соединяющего две заданные точки. В данном случае имеется в виду, что в р-сети, с одной стороны, из точки, соответствующей за-данному соединению С, а с другой стороны, из всех точек, соответствующих допустимым исходным соединениям синтеза, одновременно запускаются: два встречных потока: на первом шагу, начиная от точки С, выполняется: операция обратное движение на один шаг одновременно по всем подходящим стрелкам и в то же время из всех точек, соответствующих исходным соединениям, осуществляется вполне аналогичная операция прямое движение на один шаг, причем это делается одновременно по всем стрелкам, отходящим от этих точек. На последующих шагах соответствующие операции выполняются от всех точек, достигнутых на предыдущем этапе. [4]

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

Применение переборного алгоритма здесь оправдано тем, что связность гиперсетей для практических целей небольшая. [6]

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

С учетом случая неполных уравнений необходимо внести уточнения в описанный ранее переборный алгоритм выявления изменяющихся связей. В первую очередь следует выяснить, имеются ли, сколько и какие элиминируемые и вводимые атомы. [8]

Это и не удивительно, так как ИГ U соответствует переборному алгоритму поиска. [9]

Как отмечалось, для п Ю350 можно положить / 2 - 3 - 5 - 7 - 11 г 13 - 17 - 19; в общем случае t ищется перебором, при котором простота получающихся евклидовых простых чисел проверяется наиболее примитивным переборным алгоритмом. [10]

Известно, что для этой задачи, так же как и для задачи поиска минимальной по числу элементов схемы, существует тривиальный переборный алгоритм, практически не реализуемый уже при небольших значениях числа переменных булевой функции. [11]

Вопрос о В-сложности для задачи интервального поиска полностью аналогичен ситуации с включающим поиском и задачей о доминировании, так как для любой ЗИП существует запрос, в ответ на который надо выдать всю библиотеку задачи, и, значит, при наличии в базовом множестве характеристических функций записей переборный алгоритм будем В-оптимальным. [12]

Оценка варианта структуры, сгенерированной или выбранной из базы данных, выполняется с помощью процедуры параметрического синтеза и анализа. Использование полных математических моделей и процедур параметрической оптимизации, как правило, характеризуется высокой трудоемкостью, что не позволяет в процессе перебора просмотреть достаточное количество вариантов структур. Поэтому переборные алгоритмы применяют только в тех случаях, когда для оценки удается применить упрощенные математические модели и некоторые косвенные критерии предпочтения вариантов, отличающиеся простотой вычисления. Лишь по отношению к небольшому числу отобранных перспективных вариантов следует применять анализ но полным математическим моделям и оптимизацию параметров. [13]

Второй вариант вхождения ( обведенный в правой части уравнения ( 456) штриховыми линиями) приводит после отбрасывания в обеих частях О-атома к рассмотрению уравнения ( 45), к которому не применима ни одна из операций А - F. При попытке применения F на базе полученной по В разнице: / G - О / G - С оказывается, что ни одна из этих связей не локализуется точно. Поэтому переходим к применению переборного алгоритма, начиная удаление по одной С / - 0-связн в правой части. Этот вариант отличается от предыдущего, но равноценен ему с точки зрения минимальности структурных изменений. [14]

Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с п вершинами. Содержательно вершины графа являются городами, которые должен посетить коммивояжер, а веса ребер отражают расстояния ( длины) или стоимости проезда. Эта задача является JVP-трудной, и точный переборный алгоритм ее решения имеет факториальную сложность. [15]

Страницы: 1 2