v Введення
Широке поширення ідей структурного програмування в останні 20-30 років справила великий вплив на теорію і практику програмування і призвело до перегляду ролі типу і структури даних при розробці відповідних алгоритмів і програм. У зв'язку з цим в останні десятиліття при виробництві складних програмних систем потрібна підготовка висококваліфікованих фахівців, які досконало володіють сучасною теорією побудови систем обробки даних. У цій теорії важливе місце займають методи організації і обробки даних. Рішення будь-якої задачі зводиться до обробці безлічі даних, які являють собою абстракцію деякого фрагмента реального світу.
Для вирішення конкретного завдання, з одного боку, необхідно вибрати відповідний рівень абстрагування, тобто визначити безліч даних, представляють реальну ситуацію, що відноситься до задачі. З іншого боку, належить вибрати спосіб представлення цих даних з урахуванням можливостей комп'ютера і мови програмування.
Таким чином, для створення програмного продукту, реалізує алгоритм вирішення задачі даної курсової роботи, нам необхідно володіти знаннями теорії структур, методів представлення даних на логічному (Абстрактному) і фізичному (машинному) рівнях, а також ефективних алгоритмів обробки різних структур даних.
Також для того, що б створити дійсно ефективно працюючу програму, яка дає потрібний результат за потрібний час слід провести аналіз складності алгоритму по одному з відомих методів. Це дозволить уникнути створення програмного продукту, що не відповідає обов'язковим вимогам по ефективності програм.
Метою цієї курсової роботи є створення програмної реалізації алгоритму, який знаходить рішення геометричній головоломки: Y-пентаміно. Гра "пентамін" - це дуже захоплююче і корисне заняття, розвиваюче безліч здібностей. Фігурки являють собою все односвязного комбінації з п'яти квадратиків. Всього в одному наборі 12 фігур. Фігурки можна виготовити з паперу, картону, пластиліну, дерева, глини, або з пластмаси, загалом, з чого завгодно. Далі, беремо ці фігурки і починаємо збирати прямокутну область, розміром 6х10 квадратиків. Ця задача досить складна для обчислень вручну, але ЕОМ справляється з нею набагато швидше. Основні етапи створення програми, включаючи процес розробки алгоритму, вибору мови програмування, аналіз складності алгоритму і програми, наведені нижче.
Головною складністю, яка виникає при розробці алгоритму рішення, є застосування рекурсії, точніше рекурсивного методу проб і помилок, з використанням алгоритму з поверненнями. Теоретичні відомості про ці методах наведені в наступному розділі.
Програмний продукт, і сама курсова робота в цілому можуть бути застосовані як у наукових цілях, при аналізі швидкодії систем штучного інтелекту, так і в ширших цілях, наприклад, як програма-помічник, вбудована в основну середу-гру В«пентаміноВ». Програми такого роду допомагають знайти вирішення головоломок, якщо користувач не може зробити цього самостійно.
v Теоретичні відомості, що стосуються методу
При рішенні задачі, поставленої в курсовій роботі, слід застосувати два основні алгоритмів перебору: алгоритм з поверненнями назад (backtracking) і метод проб і помилок.
- Алгоритм з поверненнями назад:
Метод перебору з поверненнями дозволяє вирішувати практично незліченна безліч завдань, для багатьох з яких не відомі інші алгоритми. Незважаючи на таке велике різноманіття переборних завдань, в основі їх рішення є щось загальне, що дозволяє застосувати даний метод. Таким чином перебір можна вважати практично універсальним методом переборних вирішення завдань. Наведемо загальну схему цього методу:
Рішення задачі методом перебору з поверненням будується конструктивно послідовним розширенням часткового вирішення. Якщо на конкретному кроці таке розширення провести не вдається, то відбувається повернення до більш короткому часткового вирішення, і спроби його розширити тривають.
{пошук одного рішення}
procedure backtracking (k: integer); {k - номер ходу}
begin
{ініціалізація вибору варіанта}
repeat
{вибір варінт}
if {варіант підходить} then
begin
{запис варіанта}
if {рішення не знайдено} then
begin
backtracking (k +1); {рекурсивний виклик}
if {рішення не знайдено} then
{стирання варіанти}
end
else
{висновок рішення}
end;
until {варіантів немає} or {рішення знайдено}
< p> end;
begin
{запис першого варіанту}
backtracking (1);
< p> end.
До достоїнств схеми слід віднести спільність, простоту і логічність. Але вона має і недоліки. По-перше, треба самому робити запис першого варіанту, непогано б, щоб це робила сама процедура. Також в ній використовує цикл repeat: можна допустити помилку в формуванні умови виходу з циклу, особливо, якщо не знаєш закони де Моргана, до того ж іноді простіше використовувати цикл for, а якщо варіантів мало, можна обійтися взагалі без циклів. Спробуємо усунути вище наведені недоліки. Для розробки загальної схеми перебору з поверненнями скористаємося процедурою із задачі про лабіринті, просто слід її узагальнити:
{пошук одного рішення}
procedure backtracking (k: integer); {k - номер ходу}
begin
{запис варіанта}
if {рішення знайдено} then
{висновок рішення}
else
{перебір всіх варіантів }
if {варіант підходить} then
backtracking (k +1); {рекурсивний виклик}
{стирання варіанта}
end;
begin
backtracking (1);
end.
Зрозуміло дана схема також не ідеальна, але вона усуває зазначені вище недоліки. Також можна відповідно зробити схеми для інших класів переборних завдань. Спочатку схема для пошуку всіх рішень:
{пошук всіх рішень}
procedure backtracking (k: integer ); {k - номер ходу}
begin
{запис варіанта}
if {рішення знайдено} then
{запис вирішення}
else
{перебір всіх варіантів}
if {варіант підходить} then
backtracking (k +1); {рекурсивний виклик}
{стирання варіанти}
end;
Замість запису рішення його можна виводити у вихідний файл, або обробляти іншим чином в залежності від умови задачі. Цю схему можна змінити, що знаходилися не всі рішення, а тільки одне оптимальне. Під оптимальністю рішення зазвичай розуміють, що для даного рішення деяка функція приймає або максимальне, або мінімальне значення.
Розглянемо докладніше алгоритм перебору з поверненням на прикладі відомої задачі про вісім ферзів.
Скількома способами можна розставити 8 ферзів на шаховій дошці так, щоб вони не били один одного? Легенда приписує формулювання і рішення цієї задачі "королю математиків" Гауссу. Він перший зумів відшукати всі 92 рішення.
Рішення. Відповідно до описаної раніше загальної схемою алгоритму перебору з поверненням запропоновану задачу можна було б вирішувати за наведеним нижче алгоритмом "Все розстановки". По ньому ферзі розставляються послідовно на вертикалях з номерами від нуля і далі. У процесі виконання приписи можливі зняття ферзів з дошки (повернення).
Алгоритм "Всі розстановки "
1. Вважаємо D = Г†, j = 0 ( D - безліч рішень, j - поточний стовпець для чергового ферзя).
2. Намагаємося в стовпці j просунути вниз по вертикалі або новий (якщо стовпець j порожній), або вже наявний там ферзь на найближчу допустиму рядок. Якщо це зробити не вдалося, то переходимо до пункту 4.
3. j В¬ j <...
