Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Интересное:
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Дисциплины:
2019-12-27 | 153 |
5.00
из
|
Заказать работу |
|
|
Недостатки волнового алгоритма трассировки соединений:
•А | ||||
•В | ||||
•А | ||||
•В | ||||
1) Большие затраты времени (невысокое быстродействие).
2) Большие затраты памяти - на каждую ячейку требуется n = ]log2(L+2)[ бит, где L - максимально возможный путь (максимальное число, которое можно получить, распространяя волну), еще два состояния - свободно/занято.
•А | ||||
•В | ||||
•А | ||||
•В | ||||
Методы повышения быстродействия:
1. Целенаправленно выбирать из двух контактов место испускания волны так, чтобы фронт волны был меньше. Так, если у нас один контакт в углу монтажного поля, а второй - в середине, то целесообразно испускать волну из первого.
2. Испускать волну из двух контактов одновременно (встречная волна)
3. Метод рамки - соединяемые контакты ограничиваются рамкой, на 15-20% превышающей минимальный прямоугольник. Волна за эту рамку не распространяется. Если путь не был найден, то рамка либо увеличивается, либо убирается совсем.
1 | А | ® | 1. Метод путевых координат. Путевая координата - указание, откуда пришла волна (сверху(¯) /слева(®) /справа()/снизу()). n = ⌈log2(4+2)⌉ = 3. Для разрешения конфликтов первой фазы надо указать приоритеты направлений. | ||||||
2 | ¯ | ¯ | ¯ | ¯ | ¯ | ||||
3 | ¯ | ¯ | ¯ | ||||||
4 | ¯ | ¯ | ¯ | В | |||||
5 | ¯ | ¯ | ¯ | | ® | ||||
6 | ¯ | ¯ | ¯ | ® | ® | ® | ® | ||
7 | ¯ | ||||||||
8 | ¯ |
1 | 3 | 2 | 1 | А | 1 | 2. Использования веса по модулю 3 (Pi-1 ≠ Pi ≠ Pi+1). Веса равны 1, 2, 3. (0 ® ячейка не занята)
n = ⌈log2(3+2)⌉ = 3. Здесь, как и в предыдущем методе, надо указать приоритеты направлений. Ищем маршрут 1®3®2®1®3®2®… | ||||
2 | 1 | 3 | 2 | 1 | 1 | |||||
3 | 2 | 1 | 3 | |||||||
4 | 3 | 2 | 1 | В | ||||||
5 | 1 | 3 | 2 | 3 | 1 | |||||
6 | 2 | 1 | 3 | 1 | 2 | 3 | 1 | |||
7 | 3 | |||||||||
8 | 1 |
1 | 2 | 1 | 1 | А | 1 | 3. Метод Акерса (самый эффективный). Веса назначаются фронтам в соответствии со следующей последовательностью: 1122112211... n = ⌈log2(2+2)⌉ = 2. У каждого элемента обязательно различаются соседи слева и справа (1 и 2 или 2 и 1). Построение трассы сводится к выделению искомой последовательности, опять же, необходима система приоритетов. Ищем маршрут 1®1®2®2®1®1®… | |||
2 | 2 | 2 | 1 | 1 | 1 | ||||
3 | 1 | 2 | 2 | ||||||
4 | 1 | 1 | 2 | В | |||||
5 | 2 | 1 | 1 | 1 | 1 | ||||
6 | 2 | 2 | 1 | 2 | 2 | 1 | 1 | ||
7 | 1 | ||||||||
8 | 1 |
Методы снижения затрат памяти:
Алгоритм трассировки соединений по магистралям.
В данном алгоритме можно отказаться от использования дискретного представления поля.
Из двух контактов выпускаются два луча, которые будем называть магистралями. Эти магистрали - M1A и M1B - магистрали первого уровня. Если они пересекаются, то трасса найдена. Если нет, то на данных магистралях находятся базовые точки и уже из них выпускаются магистрали второго уровня и так далее, пока не будет найдено пересечение либо не будет превышен предел на уровень магистрали.
После нахождения пересечения магистралей выбирается пересечение по отрезку наименьшей длины до точки испускания. Так, если в точке P пересекаются магистрали 1-го и 2-го уровней, а в точке Q - пересекаются две магистрали второго уровня, то для проведения трассы следует выбрать точку P.
|
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
1 | А | |||||||
2 | ||||||||
3 | ||||||||
4 | В | |||||||
5 | ||||||||
6 | ||||||||
7 | ||||||||
8 |
Пример:
Из пересечений выбираем то, которое соединяет А и В (полное наименьшее по длине).
|
|
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!