Лабораторна робота № 14 евристики.

Завдання: розробити алгоритм і написати програму для завдання Аладдіна:

скільки цінних речей (заданих масою і ціною) може поміститися в рюкзак (заданий об'єм) Аладдіна.

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

Розглянемо евристику на прикладі завдання, для оптимальної архівації файлів на гнучких дискетах (тобто на мінімально можливій кількості останніх).

ДАНО: ємкість однієї дискети Е в кілобайтах і перелік з F файлів, заданих їх номерами I і їх довжинами D(I) в кілобайтах.

ПОТРІБНИЙ: перелік дискет у вигляді їх номерів {J}, в якому для кожної дискети вказана кількість записуваних на неї файлів K(J), перераховані (у вигляді їх номерів) записувані на неї файли

{D(I)} і залишок вільного місця в кілобайтах OST(J).

МЕТОД РІШЕННЯ - евристика Грехема: черговий файл з впорядкованого по убуванню довжин списку файлів поміщається на ту дискету, на якій в результаті цього залишається найменше вільне місце.

ПРЕДСТАВЛЕННЯ РЕЗУЛЬТАТІВ: оптимальний розподіл файлів по дискетах, що вимагає найменшої кількості останніх, представляється алгоритм у вигляді таблиці, в рядки якої, що відповідають відповідним дискетам, вписані номери файлів, які слід записати на цю дискету. У першій колонці цієї таблиці можна було б записувати номери дискет, а в останній - залишок вільного місця, але для змістовної простоти алгоритм ці стовпці виділені у відповідні окремі списки.

Декомпозиція завдання:

Крок 0. Початок.

Крок 1. Настройка АЛГ.

Крок 2. Введення і запам'ятовування номерів і довжин файлів.

Крок 3. Сортування файлів по збуванню їх довжин.

Крок 4. Розподіл файлів по дискетах.

Крок 5. Виведення результатів.

Крок 6. Кінець.

Декомпозиція кроків:

Крок 1. Настройка алгоритму:

1.1. ввести ємкість дискети в кілобайтах: input e

1.2. ввести кількість файлів: input f

1.3. резервувати пам'ять:

df(f, f) - масив "дискета-файли", що містить перелік файлів, записуваних на кожну дискету.

Тут і далі об'єм резервованої пам'яті визначається гіршим випадком, коли на одну дискету поміщається тільки один файл;

n(f) - список номерів файлів, що архівуються;

d(f) - список довжин файлів, що архівуються;

до(f) - список кількості файлів на кожній дискеті;

ost(f) - список залишків вільного місця на кожній дискеті.

Крок 2. Введення і запам'ятовування номерів і довжин файлів:

for i = 1 to f do

n(i) = i and ost(i) = e and k(i) = 0

input d(i) (довжина i-го файлу)

Mf: if d(i) > e then

print < Дуже довгий файл!>

input d(i) и goto Mf fi od.

Крок 3. Сортування файлів по убуванню їх довжин

for UKZ = 1 to f do

IND = UKZ

for i = UKZ + 1 to f do

if d(i) > d(IND) then IND = i fi od

if IND <> UKZ then

a = d(UKZ): d(UKZ) = d(IND): d(IND) = a

a = n(UKZ): n(UKZ) = n(IND): n(IND) = a fi

od.

Крок 4. Розподіл файлів по дискетах:

[перебір файлів]

for i = 1 to f do

[ підготовка алгоритму МІНІМУМ для пошуку дискети,

розміщення на якій i-го файлу дасть найменший залишок вільного місця]

min = e (min - найменше вільне місце)

q = 1 (q - дискета з найменшим залишком)

[перебір дискет]

for j = 1 to f do

z = ost(j) - d(i) (поточний залишок, тобто вільне місце на j-й диске-

ті при записі на неї i-го файлу)

if z >= 0 AND z < min then

q = j and min = z fi

[інакше - до наступної дискети] od.

[проглядання дискет завершене, тому запис чергового проміжного результата]

k(q) = k(q) + 1 (інкремент числа файлів на q-й дискеті)

p = k(q) (службова змінна для передачі індексу)

df(q,p) = n(i) (запис на q-у дискету i-го файлу)

ost(q) = min (запис на q-у дискету нового значення залишку)

[до наступного файлу] od.

Крок 5. Виведення результатів.