BC/NW 2007, №1, (10) :5.1

АЛГОРИТМ IDA* ПОИСКА НА ДЕРЕВЬЯХ РЕШЕНИЙ НА ЯЗЫКЕ ФУНКЦИОНАЛЬНЫХ СХЕМ

Д.Ю. Митрофанов, студ.; рук. А.П. Еремеев

(Москва, Московский энергетический институт (технический университет), Россия)

Цель данной работы – исследовать методы параллельного программирования для повышения эффективности поиска на многопроцессорных и многокомпьютерных вычислительных системах и реализовать параллельно алгоритм IDA* на языке функциональных схем.

В данной работе:

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

- исследованы параллельные подходы к решению задач поиска, позволяющие находить приемлемое решение в условиях реального времени

исследованы языки и модели параллельных алгоритмов;

подробно изучен язык функциональных схем, в семантике которого заложен неявный параллелизм;

- реализована параллельная модификация алгоритма IDA*, а также изучен алгоритм AIDA*, реализуемый на MIMD-системах и обладающий огромным потенциалом

Результаты:

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

Был сделан вывод, что, ЯФС, обладая большим потенциалом, для данной задачи является не самым удачным решением ввиду использования модели неявного параллелизма.

Алгоритм AIDA*, позволяющий добиться очень впечатляющего ускорения в 807 раз в системе из 1024 процессоров, можно реализовать только используя явный параллелизм, то есть на ЯФС его невозможно реализовать.

Литература

1. В.П.Кутепов. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения. // Изв. РАН. Теория и системы управления.. №5, 1996. стр. 97-114.

2. Системы поддержки принятия решений (обзор литературы) / под. Рук. Д.А.Поспелова. М.: АН СССР. САИИ., 1990. стр. 92-93.

3. Нильсон Н. Искусственный интеллект. // Методы решения плохоформализованных задач. М.:Мир, 1971. стр. 75-84.

Кутепов В.П., Фальк В.Н. Модели асинхронных вычислений значений функций в языке функциональных схем // Программирование, 1978. №3. стр. 20-37.