Embedded Files
Чи доводилося вам виконувати пошук варіантів виходу з лабіринту від його входу? Як у таких випадках ви діяли?
Пошук із поверненням (від англ. backtracking) — це загальний метод (або стратегія пошуку) розв’язування задачі, коли доводиться неодноразово повертатися до стану об’єкта (об’єктів), зафіксованого на попередньому кроці.
Пошук із поверненням (від англ. backtracking) — це загальний метод (або стратегія пошуку) розв’язування задачі, коли доводиться неодноразово повертатися до стану об’єкта (об’єктів), зафіксованого на попередньому кроці.
Класичним прикладом пошуку із поверненням є пошук у лабіринті всіх шляхів від входу до виходу з нього. Перелік усіх шляхів у лабіринті називають множиною всіх можливих рішень.
Прикладом пошуку з поверненням є також гра в шахи, коли для пошуку оптимального чергового ходу доводиться неодноразово повертатися до поточного стану білих і чорних
фігур.
Пошук із поверненням може використовуватися для різних структур даних для розв’язування задач, у яких потрібно перерахувати всі можливі варіанти, наприклад, доставки вантажу з одної країни в іншу, або знайти способи отримання кредиту для будівництва готелю, або дати відповідь, чи існує такий спосіб вкладу, який задовольняє власні потреби клієнта тощо.
Алгоритм розв’язування задач методом пошуку з поверненням зводиться до послідовного розширення часткового рішення. Якщо на черговому кроці таке розширення виконати не вдається, то здійснюється повернення на попередній крок і продовжується пошук.
Алгоритм розв’язування задач методом пошуку з поверненням дозволяє знайти всі розв’язки для поставленого завдання, якщо вони існують. Для прискорення методу намагаються так організувати обчислення, щоб якомога швидше можна було виявити варіанти, які не задовольняють умову.
Приклад. У багатьох джерелах як класичний приклад алгоритму пошуку з поверненням описується задача про 8 ферзів, яку можна сформулювати так.
Необхідно на шаховій дошці розмістити 8 ферзів так, щоб жодний із них не був під боєм іншого.
1. Спочатку ставиться на дошку один ферзь.
2. Далі ставляться інші так, щоб його не били вже поставлені ферзі.
3. Якщо на черговому кроці так поставити фігуру не можна, повертаються на крок назад і намагаються поставити раніше встановленого ферзя на інше місце.
За допомогою методу з поверненням можна отримати всі перестановки і комбінації даної множини.
Тернарний пошук в інформатиці застосовується для пошуку максимумів або мінімумів функції, яка на деякому відрізку спочатку постійно зростає, потім постійно спадає або спочатку спадає потім зростає.
Алгоритм тернарного пошуку можна реалізувати для пошуку заданого елемента в упорядкованому масиві, поділивши його на три приблизно рівні частини.
Елемент із заданим значенням можна порівняти з останнім елементом першої частини.
Якщо значення збігаються, то пошук завершується, якщо менше, то пошук продовжується в першій частині, інакше — він порівнюється з останнім елементом другої частини.
Далі виконуються дії, аналогічні описаним.
Практичне завдання
Практичне завдання
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Завдання 1. Знайдіть в Інтернеті відомості про 5 найвищих вершин в Україні. Розробіть програму визначення наявності у цьому переліку назви вершини, яка вводиться з клавіатури.
Алгоритм розв'язання задачі:
Програма визначає масив з назвами найвищих вершин України.
Програма отримує від користувача назву вершини (введену з клавіатури).
За допомогою циклу for перебираються всі елементи у масиві mas і кожний порівнюється з введеною користувачем вершиною. Якщо назва вершини збігається з введеною користувачем, то встановлюється значення змінної found на True і виходимо з циклу за допомогою break.
Якщо жодної відповідності не встановлено, то значення змінної found встановлюється False.
Після цього виводимо результат на екран з використанням умовного оператора.
Задача 2. Дано масив цілих чисел: 13, 7, 6, 7, 9, 7, 6, 5. Розробіть програму обчислення кількості числа, значення якого вводиться з клавіатури.
Задача 3. Дано масив цілих чисел: 6, 8, 13, 17, 19, 30,13, 8. Розробіть програму визначення всіх позицій, на яких знаходиться число, значення якого вводиться з клавіатури.
Задача 4. Розробіть програму створення масиву, що містить 10 випадкових чисел у діапазоні від 3 до 9, і визначення, чи є у ньому число 6.
Задача 5. Методом тернарного пошуку у масиві чисел : -2, 0, 3, 5, 7, 9, 11, 15, 18 знайти: 1) число 5 та вивести індекс цього числа у масиві;
2) число 25 та вивести негативний результат.
Page updated
Google Sites
Report abuse