1.1.Пошук рішень в одному просторі
Методи пошуку рішень в одному просторі зазвичай діляться на:
пошук в просторі станів;
пошук методом редукції;
евристичний пошук;
пошук методом "генерація-перевірка".
ПОШУК В ПРОСТОРІ СТАНІВ.
Завдання пошуку в просторі станів зазвичай формулюється в теоретико-графовій інтерпретації.
Нехай задана трійка (S0, F, SТ), де S0 - множина початкових станів (умови завдання), F - множина операторів завдання, що відображають одні стану в інші, СТ - множина кінцевих (цільових) станів (рішень задачі).
Мета: визначити таку послідовність операторів, яка перетворює початкові стану в кінцеві.
Процес рішення у вигляді графа G = (Х, Y), де X = {х0, х1, ...} - множина (в загальному випадку нескінченна) вершин графа, станів, а Y - множина, що містить пари вершин (хi, хj ), (хi, хj)? X. Якщо кожна пара (хi, хj) невпорядкована, то її називають ребром, а граф - неорієнтованим. Якщо для кожної пари (Xi, Xj) задано порядок (напрямок), то пару (хi, хj) називають дугою (орієнтованим ребром), а граф називають орієнтованим (спрямованим). Вершини пари (хi, хj) називають кінцевими точками ребра (дуги). Пошук в просторі станів зазвичай представляють у вигляді орієнтованого графа. Наявність пари (хi, хj) свідчить про існування деякого оператора f (f ? F), що перетворює стан, відповідний вершині хi, у стан хj. Для деякої вершини хi виділяємо множину усіх спрямованих пар (хi, хj)? Y, тобто множину дуг, що виходять з вершини хi, (батьківської вершини), і множина вершин (званих дочірніми вершинами), в які ці дуги приводять. Множина дуг, що виходять з вершини хi, відповідає множині операторів, які можуть бути застосовані до стану, відповідному вершині хi.
У множині вершин X виділяють підмножину вершин Х0 належить Х, що відповідає множині початкових станів (So), і підмножина вершин Хт? X, що відповідає множині кінцевих (цільових) станів (СТ). Множина Хт може бути задано як явно, так і неявно, тобто через властивості, якими повинні володіти кінцеві стани.
Граф С може бути заданий явно і неявно. Неявне завдання графа G полягає у визначенні множини Х0? Х (відповідної множини початкових станів) і множини операторів, які, при застосуванні їх до деякої вершини графа, дають всі її дочірні вершини.
Отже, граф G задає простір станів, тобто простір, в якому здійснюється пошук рішення. Побудова простору здійснюється за допомогою наступного процесу. Береться якась вершина х0? Х, до неї застосовуються всі можливі оператори, які породжують всі дочірні вершини. Цей процес називають процесом розкриття вершин. Якщо отримана цільова вершина, то вона не розкривається. Процес побудови простору станів закінчується, коли всі нерозкриті вершини є цільовими, або термінальними (тобто вершинами, до яких не можна застосувати жодних операторів). У зв'язку з тим, що простір станів може містити безліч вершин, на практиці процес породження простору обмежують або часом, або об'ємом пам'яті.
На практиці потрібно забезпечити повноту пошуку, тобто організувати пошук так, щоб всі цільові вершини були знайдені, якщо вони існують. Надійним способом забезпечення повноти є повний перебір всіх вершин. Для завдання процесу перебору необхідно визначити. порядок, в якому будуть перебиратися вершини графа. Зазвичай виділяють два основних способи пошуку:
пошук в глибину (спочатку розкривається та вершина, яка була побудована останньою). Рисунок 1.а.
пошук в ширину. (вершини розкриваються в тому ж порядку, в якому вони породжуються.) Рисунок 1.б.
Рис 1.Простір станів, побудований пошуком в глибину (а) і пошуком в ширину (б)
Цільові вершини помічені чорними квадратами, а термінальні - білими квадратами. При використанні кожного із способів можуть бути знайдені всі рішення. При переборі всього простору обидва методи будуть аналізувати однакову кількість вершин, однак метод пошуку в ширину вимагатиме значно більше пам'яті, так як він запам'ятовує всі шляхи пошуку (а не один, як при пошуку в глибину).
ПОШУК МЕТОДОМ РЕДУКЦІЇ.
При пошуку методом редукції рішення завдання зводиться до вирішення сукупності підзадач, що його утворюють. Цей процес повторюється для кожної підзадачі до тих пір, поки кожна з отриманого набору підзадач, що утворюють рішення вихідної завдання, не буде мати очевидне рішення. Процес рішення задачі розбиттям її на підзадачі можна представити у вигляді спеціального спрямованого графа G,так званого І / АБО-графа; Кожній вершині цього графа ставиться у відповідність опис деякої задачі (підзадачі). У графі виділяють два типи вершин: кон'юнктивні вершини і диз'юнктивні вершини.
Рішення завдання при пошуку методом редукції (при пошуку в І / АБО-графі) зводиться до знаходження в І / АБО-графі розв'язуваного графа.
Мета процесу пошуку в І / АБО-графі - показати, що початкова вершина розв'язувана, тобто для цієї вершини існує розв'язувальний граф. Визначення розв'язуваної вершини в І / АБО-графі можна сформулювати рекурсивно наступним чином:
Кінцеві (цільові) вершини розв'язувані, оскільки їх рішення відоме по вихідному припущенню.
Вершина АБО розв'язувана тоді й тільки тоді, коли розв'язувана принаймні одна з її дочірніх вершин.
Вершина І розв'язувана тоді і тільки тоді, коли розв'язувані усі її дочірні вершини.
Рис.2. Графічне представлення розбиття завдання на підзадачі.
Розв'язуваний граф визначається як підграф з розв'язуваних вершин, який показує, що початкова вершина розв'язувана На рис 2 розв'язувані вершини затемнені, а нерозв'язувані залишені білими.
Рис.3. Приклад І / АБО графа
Для графа І / АБО, так само як для пошуку в просторі станів, можна визначити пошук в глибину і пошук в ширину як у прямому, так і в зворотному напрямку. На рис. 4 наведено приклад пошуку в ширину (рис 4.а) і пошуку в глибину (рис 4.б). На малюнку вершини пронумеровані в тому порядку, в якому вони розкривалися, кінцеві вершини позначені квадратами, розв'язувані вершини затемнені, дуги розв'язуваного графа виділені подвійними лініями.
Рис. 4.Приклад розбиття задачі на підзадачі при пошуку в ширину (а) і при пошуку в глибину (б).
ЕВРИСТИЧНИЙ ПОШУК
При збільшенні простору пошуку методи сліпого пошуку вимагають надмірних витрат часу та (або) пам'яті. Це привело до створення евристичних методів пошуку, тобто методів, які використовують деяку інформацію про предметну область для розгляду не всього простору пошуку, а таких шляхів в ньому, які з найбільшою ймовірністю призводять до мети.
ПОШУК МЕТОДОМ "ГЕНЕРАЦІЯ-ПЕРЕВІРКА"
Процес пошуку може бути сформульований в термінах "генерація-перевірка". Для здійснення процесу пошуку необхідно генерувати чергове можливе рішення (стан або підзадачі) і перевірити, чи не є воно результуючим.