ОБЩИЕ СВЕДЕНИЯ О ЗАДАЧЕ РАЗМЕЩЕНИЯ
ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РАЗМЕЩЕНИЯ КОНСТРУКТИВНЫХ ЭЛЕМЕНТОВ РЭС Цель работы – исследовать эффективность алгоритмов размещения элементов РЭС в коммутационном пространстве, освоить особенности алго-ритмизации и программирования задачи размещения на ПЭВМ, приобрести навыки построения математических моделей монтажного пространства и схем соединения модулей, реализации и исследования их при решении задачи размещения с применением САПР.
ОСНОВНЫЕ МЕТОДЫ ОЦЕНКИ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РАЗМЕЩЕНИЯ
При разработке алгоритмов и программ следует стремиться к наиболее полному удовлетворению требований, предъявляемых к ним: минимальная продолжительность решения, максимальный объем задач при заданной емкости оперативной емкости ЭВМ, максимальная точность решения, высокая надёжность, эффективность, завершённость, понятность и т.д. Перечисленные показатели определяют качество программного обеспече-ния САПР. Причём на этапе разработки алгоритмов достаточно учесть такие показатели, как точность, временная и емкостная сложность, а при разработке программ или их сравнении следует учитывать и остальные показатели [1 – 4]. Объективная оценка эффективности алгоритмов размещения должна опираться на анализ точности решений и времени их получения в зависимости от основных параметров задачи. Для оценки качества решения рекомендуются два подхода [1]: 1 применение тест – задач; 2 статистическая обработка результатов. Первый способ заключается в том, что каким-либо образом находят точное (глобально – оптимальное) решение Fopt некоторого варианта W задачи Z. Затем этот вариант W решают с помощью алгоритмов А1, А2,…, Аn и анализируют, насколько i–й (i =`1, n) результат отличается от Fopt. Например, алгоритмы размещения равногабаритных элементов по критерию минимума суммарной длины соединений могут сравниваться по результатам решения тест-задачи Штейнберга. В ней предлагается на 36 заданных позиций разместить 34 элемента, матрица связности для которых также известна. Тот алгоритм, который даст размещение с меньшей суммарной длиной соединений, и будет считаться лучшим. При рассмотрении этих результатов надо учитывать, что машинное время в значительной мере зависит от характеристик ЭВМ и тщательности про-граммирования. Кроме того, сопоставление алгоритмов на одном или несколь-ких примерах не может дать достоверной информации об эффективности алгоритма. Второй– статистический способ оценки качества решения состоит в том, что формируется m вариантов задачи Z. Решив эти варианты с помощью алго-ритмов А1, А2, …, Аn, получают n результатов Ri (i=1, n`), которые оценивается рядом показателей P = {P1, P2, …, Pn} и выполняют их статистическую обработку и сравнение. Такой подход позволяет получить наиболее объективные резуль-таты для оценки качества приближенных алгоритмов. Другими словами, для оценки алгоритма размещения надо решить этим алгоритмом m задач и определить среднюю суммарную длину соединений, полученных размещений. Затем это же множество задач m решить другим алгоритмом и выполнить такую же оценку. Лучшим будет тот из алгоритмов, который даст меньшую среднюю суммарную длину соединений.
ОБЩИЕ СВЕДЕНИЯ О ЗАДАЧЕ РАЗМЕЩЕНИЯ
После распределения конструктивных элементов РЭС по коммутационным пространствам различного уровня иерархии, для каждой полученной в результате компоновки сборочной единицы производят размещение включенных в ее состав элементов предыдущего уровня, т.е. выбирают такое их взаимное расположение, при котором наилучшим образом учитываются предъявляемые к аппаратуре требования [1 – 3, 7 11]. Исходными данными для решения задачи размещения являются: - данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления соответствующей сбороч-ной единицы в аппаратуре; - количество и геометрические размеры конструктивных элементов, подле-жащих размещению; - схема соединений, а также ряд ограничений на взаимное расположение отдельных элементов, учитывающих особенности разрабатываемой кон-струкции. Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества L, и обеспечиваются наиболее благоприятные условия для последующего электрического монтажа. В том случае, если в качестве критерия размещения используют минимум суммарной взвешенной длины соединений, необходимо сформировать матрицу расстояний размещённых элементов P = || pij ||n*m. Здесь Pij = |xi - xj| + |yi - yj|, а xi, xj и yi, yj – координаты позиций, в которые размещены соответственно i–й и j–й модули. Тогда суммарная взвешенная длина соединений будет равна
где rij – элемент матрицы связности R, а pij – элемент матрицы размещения P. Математически задача формулируется следующим образом [1 - 5]. Электри-ческая схема представляется в виде мультиграфа, а моделью монтажного про-странства служит графовая решётка. Требуется вершины мультиграфа размес-тить в узлы графовой решётки таким образом, чтобы суммарная длина ребер размещенного мультиграфа была минимальна. Задача размещения является комбинаторной, т.е. может быть решена толь-ко полным перебором (для размещения n элементов на n позиций существует n! вариантов размещения). Для решения задач размещения разработано большое количество различных алгоритмов [1 – 4]. В данной работе рассмотрим эвристи-ческие алгоритмы
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (348)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |