ти альтернативні шляхи пошуку. Дві основні стратегії перебору альтернатив, а саме пошук в глибину і пошук в ширину. p align="justify"> Пошук у ширину
На противагу пошуку в глибину стратегія пошуку в ширину передбачає перехід в першу чергу до вершин, найближчий до стартовою вершині. У результаті процес пошуку має тенденцію розвиватися більше в ширину, ніж у глибину, що ілюструє
Пошук у ширину програмується не так легко, як пошук в глибину. Причина полягають у тому, що нам доводиться зберігати всі безліч альтернативних вершин-кандидатів, а не тільки одну вершину, як при пошуку в глибину. Більше того, якщо ми бажаємо отримати за допомогою процесу пошуку вирішальний шлях, то одного безлічі вершин недостатньо. Тому ми будемо зберігати не безліч вершин-кандидатів, а безліч шляхів-кандидатів. Таким чином, мета
в ширину (Шляхи, Рішення)
істинна тільки тоді, коли існує шлях з безлічі кандидатів Шляху, який може бути продовжений аж до цільової вершини. Цей продовжений шлях і є Рішення. br/>В
5. Явна уявлення посилань. Представлення функціями. Приклади
Явна уявлення посилань
Символи об'єктного мови, такі як Жак_2, Марі_4 і Кніга_22, введені для того, щоб уникнути двозначності посилань на цілком певних людей і книгу. Фраза В«Жак посилає книгу МаріВ» вказує певне В«поштове подіяВ» (або В«дія відправленняВ»), на яке бажано мати можливість посилатися надалі. Отже, доведеться дати йому ім'я індивідуума Посилка_8 і вказати, що воно - частина безлічі подій з ім'ям сукупності посилки. Переклад фрази на бінарні предикати виглядає так:
Відправник (Посилка_8, Жак_2)
Одержувач (Посилка_8, Марі_4)
Об'єкт (Посилка_8, Кніга_22)
Елем (Посилка_8, посилки)
предикатні ім'я Елем означає В«є елемент такого-безлічіВ»
Представлення функціями
Відносини між значенням Посилка_8 і аргументами тернарного предиката Посилка можна виразити також функціями на безлічі поштових посилок (однієї змінної). Функція називається також функціональною формою. Фраза В«Жак посилає книгу МаріВ» виражається в термінах функцій наступною формою:
Рівно (відправник (Посилка_8), Жак_2)
Рівно (одержувач (Посилка_8), Марі_4)
Рівно (об'єкт (Посилка_8), Кніга_22)
Елем (Посилка_8, посилки).
Предикат Так само представляє відношення рівності. Це вираз використовують певні на безлічі В«посилокВ» функції, значення яких представляють конкретизації, що стосуються Посилкі_8. p align="justify"> Приклади
Розглянемо фрази тієї ж синтаксичної форми, що й В«Жак посилає книгу МаріВ», але з кванторами
По-російськи: Жак посилає щось кожному (всім одне і те ж),
Логічно: Посилка (Жак_2, х, у).
По-російськи: Жак посилає щось кожному (але не обов'язково всім одне і те ж)
Логічно-1: Посилка (Жак_2, х, у),
Логічно-2: Посилка (Відправник (посилка, Жак_2) Одержувач (посилка, х) Об'єкт (посилка, у)),
Логічно-3: (Відправник z (Жак_2) Одержувач (z, x) Об'єкт (z, y) Ем (z, посилки)).
Три уявлення фрази В«Жак посилає щось кожномуВ» відповідає трьом уявленням фрази В«Жак посилає книгу МаріВ».
6. Основні стратегії вирішення завдань. Стратегія пошуку в глибину
Основні стратегії вирішення завдань
Загальна схема для представлення завдань називається простором станів. Простір станів - це граф, вершини якого відповідають ситуацій, що зустрічаються в задачі ("проблемні ситуації"), а рішення задачі зводиться до пошуку шляху в цьому графі. Процес рішення задачі включає в себе пошук у графі, при цьому, як правило, виникає проблема, як обробляти альтернативні шляхи пошуку. Дві основні стратегії перебору альтернатив, а саме пошук в глибину і пошук в ширину. p align="justify"> Стратегія пошуку в глибину
Для того, щоб знайти вирішальний шлях Реш із заданої вершини В в деяку цільову вершину, необхідно:
якщо В - це цільова вершина, то покласти Реш = [В], або
якщо для вихідної вершини В існує вершина-наступник В1, така, що можна провести шлях Реш1 з ​​В1 в цільову вершину, то покласти Реш = [В | Peш1]. Рис. 11.4
На Пролог це правило транслюється так:
вирішити (В, [В]): -
мета (В).
