Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм прямой волны.

Алгоритмы поиска решений в ПРИЗе.

Алгоритм прямой волны.

Пусть есть набор аксиом:

Задача: B

Доказать: ├ В.

Предположим, что все n_i=1, берем список всех различных переменных {z₁,…, z_m}.

Тогда ФТ может быть описана графом. Каждой переменной соответствует вершина.

• z₁

•Y⁰

•z₄

•z₂

X⁰•

•z₃

Если имеется аксиома X Y, то проводим ребро из вершины, соответствующей X, в вершину, соответствующую Y. Очевидно, что выводимость из аксиом формулы X⁰ Y⁰ равносильна ответу на вопрос, есть ли путь в графе между вершинами, соответствующими X⁰ и Y⁰? То есть, наша задача сводится к поиску пути в ориентированном графе.

Задача решается с помощью алгоритма прямой волны.

Источник X⁰ (отсюда ищем путь). Выписываем все переменные, в которые можно перейти из X⁰ за один шаг (фронт волны). Если фронт пустой, то задача не имеет решения. Если Y⁰ попадает во фронт, то задача решена положительно. Если Y⁰ не попадает во фронт, то продолжаем работу алгоритма.

k<m

Алгоритм всегда закончит свою работу.

Алгоритм переносится на ФТ, но в качестве ядра берется множество всех .

На каждом этапе алгоритма просматриваем все правила вывода. Если все посылки некоторого правила уже выведены, а заключение ещё нет, то включаем его во фронт. Если фронт пустой, то задача не имеет решения. Если Y⁰ попадает во фронт, то задача решена положительно. Если Y⁰ не попадает во фронт, то продолжаем работу алгоритма.

Сложность алгоритма прямой волны: , где , m – число этапов (фронтов волны), т.е. алгоритм работает квадратичное время.

Алгоритм со счётчиками.

Для каждой аксиомы вводим счётчик , который на каждом этапе будет равен количеству ещё не выведенных переменных в посылке аксиомы.

В начале работы

Пусть М – число переменных, N – число аксиом.

Заведем следующие массивы:

1) ПЕР­_В_ЛЕВ_Ч [1:M]

значение i-той компоненты - список номеров аксиом < >, в левую часть которых входит переменная z_i;

2) ПЕР_ПРАВ_Ч [1:N]

значение i-той компоненты - номер переменной, которая является правой частью i- той аксиомы;

3) ВЫВ_П [1:M] - булевский массив.

i- тая компонента равна t, если переменная z_i выведена, и равна f, если переменная z_i еще не выведена.

4) П_В_СПИСКЕ [1:M] –булевский массив.

i- тая компонента равна t, если переменная z_i выведена, но не «обработана» и включена в список для «обработки», и равна f, если переменная z_i не находится в списке для обработки.

Алгоритм:

Составляем список S для обработки переменных, куда в начало помещаем .

Отметим их в массиве П_В_СПИСКЕ [1:M], чтобы не повторятся, и в массиве ВЫВ_П [1:M], что они уже выведены.

Берём последнюю переменную p из списка S и «обрабатываем» ее, т.е. находим в массиве ПЕР_В_ЛЕВ_Ч номера аксиом, в левую часть которых она входит, и уменьшаем на 1 соответствующие счётчики. Если некоторый счетчик становится равным 0, то берём переменную из правой части соответствующей аксиомы (в массиве ПЕР_ПРАВ_Ч). Если она не в списке для обработки, то метим ее, как выведенную, и помещаем в список для обработки. После этого переменная p исключается из списка S,

и т.д.

Алгоритм работает, пока список S не станет пустым.

Если по окончании алгоритма переменная Y⁰ помечена как выведенная в массиве ВЫВ_П [1:M], то «успех», иначе – «неудача».

Время работы этого алгоритма равно числу вхождений переменных в левую часть всех аксиом .

Таким образом, алгоритм работает линейное время.