I,j,k: integer;

X: Item;

begin

for i :=2 to n do begin

x := a[i]; j := 1;

while x.key > a[j].key do inc(j);

if j < i then {є дірка!} begin

for k := i downto j+1 do

a[k] := a[k-1];

a[k-1] := x;

end;

end;

end

Аналіз. Кількість перевірок на i-му кроці дорівнює щонайбільше i-1, щонайменше 1, тому в середньому - i/2. Тому у середньому загальна кількість перевірок

При цьому Кількість пересилань M дорівнює щонайбільше i, щонайменше 0 на i-му кроці, тобто i/2 у середньому. Тому

Той факт, що Mmin = 0, означає, що якщо масив з самого початку був відсортованим, то пересилань взагалі не відбувається, що свідчить про сталість методу. Поліпшення методу можливе за рахунок впровадження на першій стадії (пошук дірки) двійкового пошуку, бо частину масиву, де відбувається пошук, уже відсортовано.

Тоді на i-му кроці кількість перевірок становитиме log2, а загалом Кількість обмінів не змінюється, тому модифікація є незначною: обмін займає звичайно більше часу, особливо, якщо частина a[i].rest є значною.

22. Навести визначення та властивості евристичних алгоритмів.

Евристичний алгоритм, чи евристика, визначається як алгоритм із наступними властивостями:

1. Він звичайно знаходить гарні, хоча не обов'язково оптимальні

рішення.

2. Його можна швидше і простіше реалізувати, ніж будь-який відомий

точний алгоритм (той, що гарантує оптимальне рішення).

Поняття «гарний» і «звичайно» у властивості 1 міняються від задачі до задачі. Наприклад, якщо для рішення задачі усі відомі точні алгоритми вимагають декількох років машинного часу, то ми можемо охоче прийняти будь-яке нетривіальне наближене рішення, що може бути отримане за розумний час. З іншого боку, маючи швидке, близьке до оптимального рішення, ми можемо прагнути все-таки до точного рішення.

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

1. Ті, які легко задовольнити.

2. Ті, які не так легко задовольнити.

Чи

Ті, які повинні бути задоволені.

Ті, стосовно яких ми могли б піти на компроміс.

Тоді ціль побудови алгоритму — створити алгоритм, що гарантує виконання вимог 1-го класу, але не обов'язково 2-го. Це не означає, що для задоволення вимог 2-го класу не робиться ніяких спроб, це просто означає, що не може бути дано ніяких гарантій, що вони будуть задоволені.

Часто дуже гарні алгоритми повинні розглядатися як евристичні. Наприклад, припустимо, що ми побудували швидкий алгоритм, що, здається, працює на всіх тестових задачах, але ми не можемо довести, що алгоритм правильний. Поки не дане таке доведення, алгоритм варто розглядати як евристику.

23. Навести опис евристичних алгоритмів для рішення задачі про упакування.

Для рішення щєї задачі існує кілька простих евристичних алгоритмів. Кожний з них може бути описаний у декількох рядках. Розглянемо чотири таких алгоритми:

Н1 (перше розміщення, що потрапилося, для заданого списку, First Fit, FF). Нехай L — деякий порядок предметів. Перший предмет з L кладемо в шухляду Ві Другий предмет з L кладемо в B1, якщо він туди міститься. У противному випадку кладемо його в наступну шухляду В2. Узагалі черговий предмет з L кладемо в шухляду Ві, куди цей предмет поміститься, причому індекс і шухляди найменший серед усіх можливих. Якщо предмет не міститься ні в одну з k частково заповнених шухляд, кладемо його в шухляду Bk+1. Цей основний крок повторюється, поки список L не буде вичерпаний.

Н2 (перше розміщення, що трапилося, с убуванням, First Fit Decreasing, FFD). Цей алгоритм відрізняється від алгоритму FF тим, що список L

упорядкований від великих предметів до меншого.

НЗ (краще розміщення для заданого списку, Best Fit, BF). Нехай L — заданий порядок завдань. Основний крок той же, що й у FF, але черговий предмет кладеться в ту шухляду, де залишається найменший невикористаний простір. Таким чином, якщо черговий предмет має розмір 3 і є чотири частково заповнених шухляди розміру 6, у яких залишилося 2, 3, 4 і 5 одиниць незаповненого простору, тоді предмет кладеться в другу шухляду, і той стає цілком заповненим.

Н4 (краще розміщення с убуванням, Best Fit Decreasing, BFD). Цей алгоритм такої ж, як і BF, але L упорядкований від великих предметів до меншого.