Описание реализации алгоритма поиска от общего к частному

В программе «Поиск от общего к частному» алгоритм поиска реализован на примере, подобном описанному в [1, 9.2.2] и [2].

Основные данные программы представлены следующим образом:

1. Класс exemplar. Она используется для описания гипотез и обучающих примеров.

Членами (полями) класса являются:

• 4) color типа string — цвет объекта;
• 5) size типа string — размер объекта;
• 6) shape типа string — форма объекта;
• 2. g_list типа ArrayList — список максимально конкретных значений;
• 3. n_list типа ArrayList — список для хранения отрицательных примеров;
• 4. p_list типа ArrayList — список для хранения положительных примеров;
• 5. goal типа string — цель обучения;
• 6. color_arr — массив элементов типа string, в котором хранятся возможные значения цветов объекта;
• 7. size_arr — массив элементов типа string, в котором хранятся возможные значения размеров;
• 8. shape_arr — массив элементов типа string, в котором хранятся возможные значения формы;

Последние три массива используются при операции замены элемента множества G его наиболее общей специализацией.

Алгоритм поиска реализован с помощью двух процедур:

• 3. GenToPartSearch (с входным параметром positive тип bool — отображающий к какому виду примеров он относится) для осуществления по шагового отображения выполнения алгоритма;
• 4. GenTopartSearch_Auto для реализации автоматического режима выполнения алгоритма.

Порядок работы пользователя с программой тот же, что и с программой «Поиск от частного к общему». Пользователь также в начале обучения задает изучаемое понятие. Программа инициализирует множество G наиболее общим понятием в пространстве поиска.

При задании пользователем положительного примера из списка g_list удаляются все гипотезы, не удовлетворяющие этому примеру. Просматривая список гипотез, программа проверяет ее соответствие положительному примеру. Если в поле гипотезы записана переменная или его значение равно значению соответствующего поля примера, то это означает, что гипотеза удовлетворяет примеру по данной позиции. Если по какой-либо позиции гипотеза не удовлетворяет примеру, то она удаляется. Рассмотренный пример добавляется в список p_list.

Работа с отрицательным примером происходит следующим образом. Просматривается список гипотез с целью нахождения гипотезы удовлетворяющей отрицательному примеру. Если такая гипотеза найдена, то сначала запоминается ее позиция в списке, а затем начинается замена гипотезы ее наиболее общей специализацией, не удовлетворяющей отрицательному примеру. Поочередно просматриваются все поля гипотезы. Если в поле гипотезы записана переменная, то в список гипотез добавляется множество гипотез, таких чтобы значение этого поля в них отличалось от значения поля в отрицательном примере. Предположим, мы рассматриваем поле color и в нем записана переменная X, а в обучающем примере в этом поле записано red. Тогда в список g_list добавляется множество всех возможных гипотез, в которых значение color не равно red (например, blue, white и т. д.). При этом остальные поля записываются с теми же значениями, что и в рассматриваемой гипотезе. После просмотра всех гипотез, помеченные на удаление удаляются из списка g_list.

Затем из списка гипотез удаляются все гипотезы, более частные, чем некоторые другие, а также гипотезы, не удовлетворяющие примерам из p_list. Аналогичные процедуры описаны в разделе, поэтому здесь их описание опускается.