17.4 Пример работы алгоритма решателя

Рассмотрим работу решателя на конкретном примере. Пусть дана следующая задача: Из пунктов А и Б навстречу друг другу вышли два пешехода. Известно расстояние 10 км, время в пути 2 часа. Известно также, что скорость второго пешехода на 1 км/ч больше, чем скорость первого. Необходимо найти скорость первого пешехода. Для решения этой задачи база знаний должна содержать следующие формулы:

Формализованная постановка задачи может быть получена с помощью генератора задач. Первым шагом поиска решения является построение дерева решений. Дерево решений для нашего примера показано на рис.16.1. Построение начинается с записи искомой переменной V1 (см. описание алгоритма построения дерева И-ИЛИ). Далее записываются формулы, с помощью которых определяется искомая переменная (это формулы S1/t1 и V2 ? K). Использование второй формулы приводит к решению через нахождение переменной V2. Для краткости этот вариант рассматриваться не будет. Рассмотрим ветвь для формулы S1/t1. Для данного узла будут записаны два сына - переменная S1 и переменная t1. Переменная t1 известна по условию задачи. Она становится листом. Далее рассматривается переменная S1. Для нее в базе знаний имеется две формулы S - S2 и V1 *t1. Использование второй формулы не приведет к решению, т.к. происходит сокращение переменных. Для формулы S - S2 необходимо найти S2, т.к. переменная S известна. Для переменной S2 в базе знаний имеется две формулы: V2 * t2 и S - S1. Использование второй формулы приводит к рекурсии, т.к. ранее подстановка для переменной S1 уже использовалась. Рассмотрим формулу V2 * t2. Здесь неизвестная переменная V2. Для нее производим подстановки. Это формулы S2/t2 и V1 + K. Первая формула приводит к рекурсии и вторая формула также приводит к рекурсии. Таким образом, процесс построения дерева заканчивается.

После построения дерева решений производится его анализ. Анализ включает: подсчет количества вариантов , анализ каждого варианта с использованием алгоритмов эквивалентных преобразований. Всего вариантов решений, без учета ветви V2 + k, будет 4. (см. рис.16.1). Решение будет получено при использовании варианта с номером 1 (см. алгоритм нумерации И-ИЛИ дерева). Этот вариант показан на рис.16.2 В этом дереве записаны подстановки формул, приводящие к построению уравнения.

Рассмотрим эти подстановки:

Тогда выражение, содержащее уравнение, будет следующего вида:
V1 = (S ? ((V1 + K) * t2))/t1.

Раскрывая скобки, подставляя конкретные значения для S, t1, t2 и K, производя сокращение подобных членов, получим следующее линейное уравнение:
2 * V1 ? 4 = 0. Отсюда решение: V1 = 2.