к. Для того, щоб побудувати необхідний план, ми повинні відшукати послідовність ходів, що реалізовує задану трансформацію. p align="justify"> Це завдання можна уявляти собі як завдання вибору серед безлічі можливих альтернатив. У вихідній ситуації альтернатива всього одна: поставити кубик С на стіл. Після того як кубик З поставлений на стіл, ми маємо три альтернативи:
поставити А на стіл або
поставити А на С, або
поставити С на А. (Мал.)
Ясно, що альтернативу "поставити С на стіл" не мало сенсу розглядати всерйоз, так як цей процес не впливає на ситуацію.
Як показує розглянутий приклад, з завданнями такого роду пов'язано два типи понять:
(1) Проблемні ситуації.
(2) Фіксований ходи або дії, що перетворюють одні проблемні ситуації в інші.
Проблемні ситуації разом з можливими ходами утворюють спрямований граф, званий простором станів.
В
3. Перетворення унарних предикатів в бінарні. Приклади. Перетворення m-арних предикатів у твір бінарних.
Перетворення унарних предикатів в бінарні
Унарний предикат перевіряє деякий властивість одного аргументу. Типовий приклад - функція, яка використовується в якості критерію пошуку першого простого числа. p align="justify"> Бінарні предикати зазвичай порівнюють деякий властивість двох аргументів. Наприклад, щоб відсортувати елементи по нестандартному критерію, програміст передає алгоритмом просту предикатную функцію. p align="justify"> Унарний предикат складається з предикатного імені і значення свого єдиного аргументу. Отже, його формат такий: Предікатное_імя (значеніе_аргумента). Значення аргументу є конкретизація предикатного імені або змінною. Наприклад, Людина (Сократ) вказує, що ім'я власне В«СократВ» - конкретизація імені сукупності В«людинаВ», а Людина (х) вказує, що х - людина (не що-небудь інше). Фразу В«Сократ - людинаВ» можна представити бінарним предикатом КОНКРІТ (Сократ, людина). p align="justify"> Перетворення m-арних предикатів у твір бінарних
Фразу В«Жак посилає книгу МаріВ» неважко уявити тернарного (тобто з трьома аргументами) предикатом:
Посилка (Жак_2, Марі_4, Кніга_22).
Визначивши нові предикати, можна уявити цю фразу твором (кон'юнкція) бінарних предикатів:
Відправник (Посилка, Жак_2)
Одержувач (Посилка, Марі_4)
Об'єкт (Посилка, Кніга_22).
Дана логічна формула читається так: В«відправник посилки - Жак, одержувач посилки - Марі і об'єкт посилки - книгаВ».
Цей приклад підказує правило перетворення m-арних предикатів (з m аргументами) в еквівалентну твір бінарних предикатів. Всякий m-арний предикат складається з предикатного імені та m значень аргументів:
Предікатное_імя (значення_1, значення_2, ..., значеніе_m).
Наприклад, предикат для опису посилки деякого об'єкта відправником одержувачу може мати наступний формат:
Посилка (відправник, одержувач, об'єкт).
Функція В«відправник посилкиВ» враховується першим аргументом, функція В«одержувач посилкиВ» - другим, функція В«об'єкт посилкиВ» - третім. Спочатку вибраний порядок аргументів для відповідності В«функція - аргументВ» може бути довільним, але повинен зберігатися незмінним. Функціональну організацію m-арного предиката можна представити так:
Предікатное_імя (функція_1, функція_2, ..., функція_т).
При записі m-арного предиката через бінарні предикати використовується спеціальне угоду, що дозволяє зберегти і явно вказати відповідні функціональні відносини. Кожна функція стає ім'ям бінарного предиката, перший аргумент якого є ім'ям вихідного m-арного предиката, а другий - значенням ставиться до цієї функції аргументу. Функціональна організація вихідного m-арного предиката і значення його аргументів представляються твором бінарних предикатів:
Функція_1 (предікатное_імя, значення_1) Функція_m (предікатное_імя, значеніе_m).
4. Основні стратегії вирішення завдань. Пошук у ширину
Основні стратегії вирішення завдань
Загальна схема для представлення завдань називається простором станів. Простір станів - це граф, вершини якого відповідають ситуацій, що зустрічаються в задачі ("проблемні ситуації"), а рішення задачі зводиться до пошуку шляху в цьому графі. Процес рішення задачі включає в себе пошук у графі, при цьому, як правило, виникає проблема, як обробля...
