Моделі і методи прийняття рішень
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
регляду вершин при пошуку в ширину, на рис.3 пошуку в глибину.
Рис.2. Процедура пошуку в ширину
Рис.3. Процедура пошуку в глибину
Пошук в глибину (більш поширений) дозволяє зекономити память, оскільки при його реалізації не потрібно запамятовувати все дерево, а лише вершини, що мають відношення до поточної альтернативи.
2.3. Простір задач і простір станів
При плануванні в просторі станів заданим вважається деякий набір станів (ситуацій). Відомі дії, які може здійснювати система та які визначають перехід з одного стану в інший.
Графом станів задачі називається орієнтований граф, вершини якого відповідають можливим станам предметної області, а дуги методам переходу від стану до стану.
Дуги можуть мати мітки, які інтерпретуються як вартість або довжина відповідного переходу. Тоді вирішення задачі являє собою пошук шляху від початкового стану до цільового; при цьому типовою вимогою є оптимізація даного рішення (пошуку найкоротшого шляху).
Класичний приклад планування в просторі станів задача комівояжера.
Планування в просторі задач передбачає декомпозицію початкової задачі на підзадачі, поки не буде досягнути зведення до задач, для яких вже готові алгоритми рішення. Таку декомпозицію можна уявити у вигляді І/АБО графа.
Існують також комбінації планування у просторі задач істанів.
2.4 Автоматний спосіб задання алгоритму
В компютері вхідна послідовність бітів перетворюється у вихідну за допомогою логічних схем. Логічні схеми поділяються на комбінаційні схеми і схеми з памяттю (скінченні автомати).
У комбінаційних схемах значення вихідних змінних залежать лише від стану вхідних і не залежать від поточного стану схеми. Будь-яка комбінаційна схема реалізує булеву (0/1) функцію від своїх вхідних змінних.
Скінчений автомат є перетворювачем, вихід якого залежить від входу, але й від поточного стану автомата. При цьому кількість вхідних і вихідних змінних, їх значень є скінченою. Поточний стан автомата в памяті.
Найуніверсальнішою моделлю компютерних обчислень є машина Тьюринга.
Автомати мають память у вигляді стрічки і пристрій для читання з неї. Стрічка розбита на квадрати з символами. Автомат розглядає символи по черзі, виконує обчислення і розвязує задачі.
Формально скінчений автомат описується так:
FA=
де Q=(q1, q2, …, qn) - скінченна множина станів керування; A=(a1, a2, .., am) - вхідний алфавіт; b: Q*A>Q - функція переходів; q0 - початковий стан; - множина заключних станів керування.
Приклад. Потрібно побудувати скінчений автомат який допускає тільки послідовності 0/1, при цьому в послідовності розпізнавання кількість одиниць повинна бути парною, а нулів непарною.
Згідно з умовою задачі А складатиметься з символів 0, 1, #, де # позначатиме довільний символ, відмінний від 0 і 1. Тобто, А=.
Множину станів виберемо так:
Q=(q1, q2, …, q5),
де q0 - початковий стан;
q1 - стан помилки;
q2 - кількість нулів непарна, а одиниць парна;
q3 кількість нулів і одиниць непарна;
q4 кількість нулів і одиниць парна;
q5 кількість нулів парна, а одиниць непарна;
Згідно з умовою задачі F=
Функції переходів визначаються так:
q0#>q1q00>q2q30>q5q1>q1q01>q5q31>q2q2>q1q10>q1q40>q2q3>q1q11>q1q41>q5q4>q1q20>q4q50>q3q5>q1q21>q3q51>q4Автомати зручно задавати таблично:
#01
Рядки таблиці позначаються станами множини Q, а стовпці символами вхідного алфавіту. Символ < позначає заключні допустимі стани. Графічний опис автомата полягає у побудові графа, де вершини qi і qj зєднуються дугою a якщо виконується команда qia>qj. Заключні допустимі вершини позначаються подвійним колом. Рис.2. Графічне задання автомата Спеціальним типом автомата є машина Тьюринга. Універсальна машина Тьюринга може обчислити будь-який інтуїтивний алгоритм. 3. Складність алгоритмів Універсальним обчислювальним пристроєм називатимемо пристрій, на якому можна промоделювати роботу машини Тьюринга. Машини Тьюринга дозволяють обчислювати тільки рекурсивні функції. Частково рекурсивні функції визначена не при всіх значеннях аргумента. Теза Тьюринга: Клас функцій, частково обчислюваних за Тьюрингом, збігається з класом частково рекурсивних функцій. Теза Чорча: клас частково рекурсивних функцій збігається з класом частково обчислюваних функцій. Теза Чорча еквівалентна тезі Тьюринга. Моделі РАМ і РАСП Машина Тьюринга дуже незручна для програмування через послідовний доступ до комірок памяті (стрічка), неструктурованість записів на стрічці (потрібно використовувати розподільники), відсутні основні арифметичні операції та ін. Модель РАМ довільний доступ до памяті, одна стрічка для читання, друга для запису. РАСП програма перебуває в регістрах і може сама себе змінювати. Під складністю алгоритму розуміється часова оцінка його роботи або ємність необхідної памяті. Апріорний аналіз алгоритму теоретично, тестування практична перевірка. Розмірність задачі (вхідних даних) це число (ціле), яке характеризує розмір вхідних даних задачі (розмірність одномірних, двомірних масивів, ...). Часова ск?/p>