у, что відповідає умові задачі. Для вирази (х 1 х 2 ) = х 3 такими наборами будут 000, 010, 100, 111.
Если n = 3, дерево має 2 3 = 8 листів. Тоб число варіантів експоненційно поклади від n (2 n = exp (n ln2). p> не нашкірна перебірній алгоритм є експоненційнім (алгоритм поиска максимального елемента в масіві - лінійній).
Із збільшенням розмірності задачі будь-який поліноміальній алгоритм становится ефектівнішім за експоненційній.
2.2 Поиск у глибінь и у ширину
Є Дві основні стратегії поиска потрібної вершини на дереві:
1) поиск на у ширину;
2) поиск на у глибино (перебір з поверненості, бектрекінг).
Процедура поиска у ширину передбачає аналіз на шкірному кроці нащадків усіх вершин (паралельна перевірка всех можливіть альтернатив).
Процедура поиска в глибінь передбачає першочергових аналіз нащадків тихий вершин, что були проаналізовані останнімі. Всі альтернативи аналізуються послідовно; аналіз деякої альтернативи завершується позбав тоді, коли встановлюється, приводити вона до успіху чи ні. Если ж альтернатива зумовлює Невдача, відбувається повернення и Розгляд других альтернатив.
На рис.2 показана послідовність перегляду вершин при поиска в ширину, на рис.3 - поиска в глибино.
Рис.2. Процедура поиска в ширину
В
Рис.3. Процедура поиска у глибінь
Поиск в глибінь (Більш Поширеними) дозволяє зекономити пам'ять, оскількі при его реалізації НЕ нужно запам'ятовувати все дерево, а позбав вершини, что мают відношення до поточної альтернативи.
2.3. Простір завдань и простір станів
При плануванні в просторі станів завданні вважається Деяк набор станів (СИТУАЦІЙ). Відомі Дії, Які может Здійснювати система та Які візначають Перехід з одного стану в Інший.
Графом станів задачі назівається орієнтований граф, вершини Якого відповідають можливіть станам предметної области, а дуги - методам переходу від стану до стану.
Дуги могут мати Мітки, Які інтерпретуються як ВАРТІСТЬ або довжина відповідного переходу. Тоді Вирішення задачі являє собою поиск на шляху від початкових стану до цільового; при цьом Типового Вимогами є Оптимізація даного решение (поиска найкоротшого шляху).
Класичний приклад планування в просторі станів - завдання комівояжера.
Планування в просторі завдань передбачає декомпозіцію початкової задачі на підзадачі, пока не буде досягнутості зведення до завдань, для якіх Вже Готові алгоритми решение. Таку декомпозіцію можна уявіті у вігляді І/АБО графа.
Існують такоже комбінації планування у просторі завдань істанів.
2.4 автоматні способ задання алгоритму
У комп'ютері вхідна послідовність бітів перетворюється у віхідну помощью логічніх схем. Логічні схеми поділяються на комбінаційні схеми и схеми з пам'яттю (скінченні автоматиз).
У комбінаційніх схемі значення вихідних змінніх залежався позбав від стану вхідніх и НЕ залежався від потокового стану схеми. Будь-яка комбінаційна схема реалізує булеву (0/1) функцію від своих вхідніх змінніх.
Скінченій автомат є перетворювач, вихід Якого поклади від входу, альо ї від потокового стану автомата. При цьом кількість вхідніх и вихідних змінніх, їх значень є скінченою. Поточний стан автомата - в пам'яті. p> Найуніверсальнішою моделлю комп'ютерних обчислень є машина Тьюринга.
Автомати мают пам'ять у вігляді стрічкі и Пристрій для читання з неї. Стрічка Розбита на КВАДРАТ з символами. Автомат Розглядає символи по черзі, Виконує обчислення и розв'язує задачі.
Формально скінченій автомат опісується так:
FA = 0 , F>
де Q = (q 1 , q 2 , ..., q n ) - скінченна множини станів Керування; A = (a 1 , a 2 , .., a m ) - вхідній алфавіт; b: Q * A в†’ Q - функція переходів; q 0 - початковий стан; - множини заключний станів Керування.
Приклад. Потрібно побудуваті скінченій автомат Який допускає Тільки послідовності 0/1, при цьом в послідовності розпізнавання кількість одиниць винна буті хлопцем, а нулів - непарний.
Згідно з умів задачі А складатіметься з сімволів 0, 1, #, де # позначатіме довільній символ, відмінний від 0 и 1. Тоб, А = <0, 1, #>. p> множини станів віберемо так:
Q = (q 1 , q 2 , ..., q 5 ),
де q 0 - початковий стан;
q 1 - стан помилки;
q 2 - кількість нулів непарна, а одиниць - Парна;
q 3 - кількість нулів и одиниць непарна;
q 4 - кількість нулів и одиниць парна;
q
