Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Побудова алгоритмів ефективних за часовою складністю. Задача квадратичного призначення
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2012
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритми та методи обчислень
Група:
КІ
Частина тексту файла (без зображень, графіків і формул):
М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
Висновок:
Я ознайомився з способом зменшення часової складності за допомогою Евристичного алгоритму,який дозволяє розв’язувати задачі за сприятливий час але не дозволяє отримати точного результату.
19.11.2012 14:31
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора