Дослідження алгоритму розміщення методом попарної перестановки

Мета: вивчити алгоритм розміщення методом попарної перестановки і набути навичок його використання.

2.1 Теоретичні відомості

Послідовні алгоритми основані на послідовному закріпленні заданого набору конструктивних елементів на комутаційній платі, відносно раніше встановлених, для отримання оптимального розміщення в сусідніх позиціях. Як закріплені на платі елементи вибирають роз'єми, що розставляють по краях плати або в місцях, що максимально відповідають вимогам технічного завдання на проектування. При цьому всі контакти роз'ємів буде рівномірно розподілено по стовпцям і рядкам координатної сітки. На кожному l-ому кроці (l = 1,2,…,n) для установлення на комутаційну плату вибирають елемент ri l із числа ще не розміщених, що має максимальний ступінь зв'язності з раніше закріпленими елементами r_n^l-1. У більшості алгоритмів, що використовують, оцінювання ступеня зв'язності проводять за однією з таких формул:

(3.1)

де c_ij – коефіцієнт зваженої зв'язності елементів i і j;

Ф – множина індексів елементів, закріплених на попередніх (l-1) - кроках;

n – загальна кількість розміщених елементів.

(2.2)

де c_ij – коефіцієнт зваженої зв'язності елементів i і j;

Ф – множина індексів елементів, закріплених на попередніх (l-1) - кроках;

n – загальна кількість розміщених елементів.

Якщо встановлювальні розміри всіх розташованих на платі елементів однакові, то обраний на поточному кроці елемент r_i^l буде закріплено у тій позиції t_j^l із числа незайнятих, для якої значення цільової функції F_j^l з врахуванням раніше розміщених елементів r_j^l-1 є мінімальним. Якщо критерієм оптимальності є мінімум сумарної зваженої довжини з'єднань, то:

(2.3)

де d_ij – відстань між l-ою позицією установлення елемента r_i^l і позицією розміщеного раніше елемента r_j^l-1;

c_ij – множина позицій, що зайняті елементами (l-1)-го кроку алгоритму.

Процес розміщення буде закінчено після виконання n кроків алгоритму.

Алгоритми, що використовують послідовний процес розміщення елементів, є самими швидкодійними у наш час. Однак за якістю розміщення послідовні алгоритми поступаються ітераційним. Тому їх використовують для початкового розміщення елементів на платі.

2.2 Порядок виконання роботи

Розміщення за методом попарної перестановки елементів проводиться таким чином.

1. Відповідно до поданої схеми визначити елементи схеми, що є роз'ємами або служать для під'єднання інших блоків і розмістити їх на одній із сторін плати.

2. Розмістити елементи на схемі місць так, щоб вони знаходились максимально близько до елементів, з якими мають максимальну кількість зв'язків. Для першочергового розміщення необхідно використовувати елементи, що мають максимальну кількість з'єднань з установленими і мінімальну із неустановленими. Вибраний елемент буде розміщено на вільному місці в монтажному просторі, яке відповідає мінімуму суми відстаней цієї вершини від всіх закріплених вершин з якими вона зв'язана. Встановлена таким чином вершина є закріпленою. Наступну незакріплену вершину потрібно вибрати аналогічно, поки всі вершини графа не будуть закріплені в монтажному просторі.

3. Відповідно до схеми створити матриці зв'язків C і довжин D.

4. Для оцінювання ефективності розміщення необхідно використати сумарну довжину провідників, яку обчислено як половина суми добутків кожного елементу матриці С на відповідний елемент матриці D.

5. Порівняти значення критеріїв якості початкової і оптимізованої схеми, зробити висновки.

2.3 Зміст звіту

1. Мета та цілі роботи.

2. Розрахункова частина. (Основні розрахункові формули та розрахунок).

3. Програма, написана мовою програмування (C++, C# , Pascal), що виконує задачу поставлену у лабораторній роботі.

4. Висновки.

2.4 Контрольні запитання

1. Принципи роботи алгоритму розміщення.

2. До якої групи алгоритмів відноситься метод попарної перестановки?

3. Які критерії використовуються для оцінювання якості розміщення елементів?

4. Наведіть черговість розміщення елементів у монтажному просторі.

5. Які елементи мають пріоритет при розміщенні?

6. Як розміщуються елементи на кожному кроці алгоритму?

7. Поясніть перший крок роботи алгоритму розміщення.

2.5 Варіанти завдань

№	Схема місць	Схема з'єднань
1	2	3
1