а. Для оцінки логічної складності алгоритмів пропонується використовувати кількісну міру у вигляді повної ентропії (алгоритмічної заходи кількості інформації за Колмогорова) двійковій послідовності В
Ia (k, s) = n * H (k, s),
де H (k, s) = - ((k/n) log (k/n) + (s1/n) log (s1/n) + (s0/n) log (s0/n))
або Н (к, s) = - ((k/n) log (k/n) +2 (s/n) log (s/n));
В
n - загальне число виходів безумовних і умовних операторів змістовного алгоритму (граф-схеми),
до - число виходів безумовних операторів,
s1, - число В«одиничнихВ» виходів умовних операторів,
S0 - число В«нульовихВ» виходів умовних операторів,
s - число умовних операторів (s = s1 = s0).
Ia (k, s) =-n ((k/n) log (k/n)) біт - частка логічної сложності1 алгоритму по безумовним операторам;
Ij (k, s) =-n (2 (s/n) log (s/n)) біт-частка логічної складності алгоритму по умовних операторам.
Ця формула представляє собою абсолютну логічну складність алгоритму, виміряну в двійкових одиницях (бітах).
Обчислимо ці значення для нашого алгоритму:
n = 13; k = 5; s = s1 = s0 = 4;
k/n = 0.39; s/n = 0.31;
(k/n) log (k/n) = -0.53; (s/n) log (s/n) = -0.52;
Н (к, s) = - (-0.53 +2 (-0.52)) = 1.57; I (k, s) = 13 * 1.57 = 20.41 біт. br/>
Враховуючи той факт, що кількість інформації, витрачається при реалізації алгоритму рішення за методом повного перебору, становить близько 28.6, ми можемо сміливо стверджувати, що даний алгоритм досить ефективний. Безсумнівно, це не означає, що реалізована з цього алгоритмом програма ідеальна. Наприклад, її можна було оптимізувати, скоротивши кількість стовпців у масиві geometry на 8, так як останні вісім елементів ніде не використовуються. Однак, це алгоритмічна міра і багато чого ще залежить від реалізації алгоритму в програмному продукті.
У моїй задачі потрібно вивести всі можливі рішення, але незважаючи на те, що їх не так багато, як очікувалося (мабуть через того, що в умові завдання повороти фігур не передбачені), все-таки це займе багато місця. Так як тест програми полягає у виведенні меншого кількості результатів, то я наведу кілька прикладів виведення для області 6х10 і5х12. p> 6х10:
1) p> 1 1 1 2 2 3 4 4 5 5
6 6 1 2 3 3 3 4 4 5
7 6 1 2 2 3 8 8 4 5
7 6 6 9 9 9 10 8 8 5
7 7 9 9 10 10 10 8 11 11
7 12 12 12 12 12 10 11 11 11
2)
9 4 4 7 7 7 7 11 11 11
9 9 4 4 7 2 2 2 11 11
5 9 10 4 3 2 8 2 6 6
5 9 10 3 3 3 8 8 6 1
5 10 10 10 3 8 8 6 6 1
5 5 12 12 12 12 12 1 1 1
3)
11 11 12 10 9 9 9 1 1 січня
11 11 12 10 10 10 9 9 6 січня
7 11 12 10 4 4 6 6 6 1
7 7 12 4 4 8 6 3 2 2
7 5 12 4 8 8 3 3 3 2
7 5 5 5 5 8 8 3 2 2
5х12:
В
1)
7 7 7 7 8 8 10 9 9 9 5 травня
2 7 2 8 8 1 10 10 10 9 9 травня
2 2 2 3 8 1 10 4 4 6 5 червня
11 11 3 3 3 1 1 1 квітня 4 5 червня
11 11 11 3 12 12 12 12 грудня 6 квітня 6
2)
9 5 5 10 10 10 4 4 6 6 8 8
9 9 5 7 10 4 4 3 2 2 6 8
1 9 5 7 10 4 3 3 3 2 6 8
1 вересня 5 липня 7 11 11 3 2 2 6 8
1 1 1 7 11 11 11 12 12 12 12 грудня
В
3)
7 7 7 7 9 10 10 10 8 1 1 1
5 7 4 4 9 9 10 8 8 2 1 лютому
5 4 4 11 11 9 10 3 8 8 2 1
5 4 11 11 11 9 3 3 3 2 2 6
5 5 12 12 12 12 12 3 6 6 6 6 br/>
Як можна помітити, кожна цифра в області означає номер фігури, яка поставлена ​​на цю клітку. Т. е. якщо індекс i фігури в масиві = 7, то клітини, зайняті цією фігурою відзначаються цією цифрою. <В В
v Висновок
Отже, ми завершили розробку курсовій роботи, а саме її головної мети - створення програмного продукту, що знаходить рішення головоломки В«Y-пентаминоВ». Підводячи підсумки, можемо зробити кілька важливих висновків. p> 1. Застосування методу проб і помилок, замість звичайного повного перебору, дозволяє істотно скоротити час виконання програми, а також обсяг затрачуваної пам'яті. Це було з'ясовано при аналізі складності алгоритму по алгоритмічної мірою А.Колмогорова. Обчислення показали, що кількість інформації алгоритму за методом проб і помилок, значно менше, ніж у алгоритму прямого перебору.
2. Важливою характеристичної особливістю розробки програми для вирішення головоломок є те, що практично неможливо скоротити число переборів за рахунок розгляду окремих випадків, не мають місця бути в тому чи іншому випадку. У задачі пентамино була тільки можливість запобігти розгляд замкнутих областей дошки, площа яких менше або більше п'яти (в такі області фігуру вже ставити не можна, тому переглядати її в програмі немає сенсу - потрібно шукати інше рішення). Однак навіть у цьому випадку існують такі варіанти, при яких обмеження процесу розстановки цією умовою веде д...
