Параллельные алгоритмы поиска решений в таблицах

Алгоритмы поиска в таблицах решений можно разделить на параллельные и последовательные. Рассмотрим суть алгоритмов первой группы на примере параллельного алгоритма поиска по ключу.

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

  • 1. В зависимости от выполнимости входных условий формируем ключ k = (kv к2,..., кп)т, представляющий собой комбинацию нулей и единиц. Здесь и далее Т — символ транспонирования; к(= 1, если /-е условие истинно, и ki = 0 в противном случае.
  • 2. Ключ последовательно сравниваем со всеми кодовыми комбинациями таблицы решений до совпадения. Напомним, что символ безразличия в таблице решений совпадает с любым из символов 0,1, стоящим в соответствующей позиции ключа.
  • 3. Выполняем переход в раздел «Тело действий» и выбираем действие, которое закреплено за найденной кодовой комбинацией. Если таких действий несколько, то выбираем любое из них или используем для выбора дополнительные критерии.

Обратимся к примеру, представленному в табл. 4.7. Пусть описание ситуации имеет вид

Материал = Алюминий, Этап = Черновой, 30 < Диаметр < 50.

Ключ в этом случае равен (1,0,1,0,0,1,0). Сравнение этого ключа со столбцами таблицы решений дает совпадение с пятым столбцом, которому соответствует действие «Припуск = 0,3».

Алгоритм поиска по ключу является не вполне состоятельным с точки зрения вычислительной сложности. В теории вычислительной сложности качество алгоритмов принято оценивать по наихудшему случаю. В алгоритме поиска по ключу наихудшим будет вариант, когда искомый столбец расположен в самом конце таблицы. Это значит, что для принятия решения придется просмотреть все столбцы таблицы, число которых, как отмечалось выше, может быть чрезвычайно большим. Можно показать, что алгоритм поиска по ключу имеет экспоненциальную вычислительную сложность. Алгоритмы с такой характеристикой считаются неэффективными, и их нецелесообразно использовать для решения задач высокой размерности.

Поиск по ключу относится к параллельным алгоритмам поиска решений, поскольку все условия ключа одновременно сравниваются с кодовыми комбинациями таблицы.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >