Мiнiстерство освіти і науки, молоді та спорту України Національний університет «Львівська політехніка» Кафедра СКС Звіт з лабораторної роботи №4 з дисципліни «Алгоритми і методи обчислень» на тему: " Побудова алгоритмів ефективних за часовою складністю. Задача квадратичного призначення". Варіант 12 Задане дискретне робоче поле ДРП і матриця зв'язності R. R x 1 2 3 4 5  1 0 2 4 0 3  2 2 0 3 0 4  3 4 3 0 3 2  4 0 0 3 0 2  5 3 4 2 2 0   ДРП                     Розташувати елементи X1, X2, X3, X4, X5 на ДРП за критерієм мінімальної сумарної довжини з'єднань. Позначимо номера позицій в правому верхньому куті вільних позицій ДРП 1      2      4 5   3     Визначемо матрицю відстаней D: / Підрахуємо мінімальну нижню границю Fmin = r*d r = 0 0 2 2 2 3 3 3 4 4 d = 5 4 4 3 3 2 2 2 2 1 _____________________________ 0+0+8+6+6+6+6+6+8+4 = 50 r – вектор зв'язків між елементами d - вектор відстаней між позиціями елементів Будемо розрізняти три типи елементів : "незакріплені", "закріплегні" в певній позиції та "зафіксовані". 1. Вибираємо елемент Х1 Закріплюємо елемент Х1 в позиції Р1 / / F1(1) – нижня границя для розташування, в якому елемент Х1 закріплений в позиції (1) f н,н – скалярний добуток для незакріплених елементів f 1(1),н - скалярний добуток для закріпленого елемента Х1 в позиції Р1 та незакріплених елементів . (F1(1) > Fmin ), тому переміщуємо елемент Х1 в наступну вільну позицію. Наприклад, в позицію Р2. Закріплюємо елемент Х1 в позиції Р2 X1 позиція 2 / / (F1(2) > Fmin ), тому переміщуємо елемент Х1 в наступну вільну позицію. Наприклад, в позицію Р3. Закріплюємо елемент Х1 в позиції Р3 X1 позиція 3 / / F13 = Fmin => Подальше переміщення елемента Х1 припиняємо. Фіксуємо елемент Х1 в позиції Р3 2. Вибираємо елемент Х2. 2.1 Закріплюємо елемент Х2 в позиції Р1 X2позиція 1 / / (F2(1) > Fmin ), тому переміщуємо елемент Х2 в наступну вільну позицію. Наприклад, в позицію Р2. 2.2 Закріплюємо елемент Х2 в позиції Р2 X2позиція 2 / / (F2(2) > Fmin ), тому переміщуємо елемент Х2 в наступну вільну позицію. Наприклад, в позицію Р4. 2.3 Закріплюємо елемент Х2 в позиції Р4 X2позиція 4 / / (F2(4) > Fmin ), тому переміщуємо елемент Х2 в наступну вільну позицію - Р5. 2.4 Закріплюємо елемент Х2 в позиції Р5 X2позиція 5 / / Обираємо меншу нижню границю - F2(5) Фіксуємо елемент Х2 в позиції Р5 3. Вибираємо елемент Х3. Закріплюємо елемент Х3 в позиції Р1 X3позиція 1 / / (F3(1) > Fmin ), тому переміщуємо елемент Х3 в наступну вільну позицію. Наприклад, в позицію Р2. Закріплюємо елемент Х3 в позиції Р2 X3позиція 2 / / (F3(2) > Fmin ), тому переміщуємо елемент Х3 в наступну вільну позицію - Р4. Закріплюємо елемент Х3 в позиції Р4 X3позиція 4 / / Обираємо меншу нижню границю - F3(4) (FminХ3= 53) Фіксуємо елемент Х3 в позиції Р4 4. Вибираємо елемент Х4. Закріплюємо елемент Х4 в позиції Р1 X4позиція1 / ‘’ / (F4(4) > Fmin ), тому переміщуємо елемент Х4 в наступну вільну позицію - Р4. Закріплюємо елемент Х4 в позиції Р4 X4позиція 4 / / Обираємо меншу нижню границю - F4(1) (FminХ4 = 51) Фіксуємо елемент Х4 в позиції Р1 Залишається тільки позиція Р4, в якій і закріплюємо X5 (FminХ5 = 51) / / Підраховуємо сумарну довжину з'єднань Fсум =3*2+4*1+2*2+2*4+2*3+4*2+3*3+3*2=51 Висновок: Я ознайомився з способом зменшення часової складності за допомогою Евристичного алгоритму,який дозволяє розв’язувати задачі за сприятливий час але не дозволяє отримати точного результату.