|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Параллельный алгоритм решения задачи РАНЕЦ методом динамического программированиядоклад на конференции
- Авторы: Лазарев А.А., Сальников А.М., Баранов А.В.
- Всероссийская Конференция : Параллельные вычисления и задачи управления (РАСО)
- Даты проведения конференции: 2010
- Тип доклада: не указан
- Докладчик: не указан
- Место проведения: Москва, ИПУ РАН, Russia
-
Аннотация доклада:
В работе рассмотрена модификация алгоритмов динамического программирования(АДП), называемых графическими алгоритмами (ГА). Для задачи РАНЕЦ показано, что временная сложность ГА ниже, чем у стандартных АДП. Средняя продолжительность работы ГА также зачастую существенно меньше. ГА также могут решать примеры большой размерности и примеры с нецелочисленными параметрами. Кроме того, для некоторых задач ГА обладают полиномиальной временной сложностью, в то время как АДП обладают псевдополиноминальной сложностью. В работе рассмотрен параллельный АДП для задачи РАНЕЦ, основанный на блочной декомпозиции, а также предложен быстрый алгоритм решения задачи и представлены результаты моделирования, подтверждающие эффективность алгоритма.
- Добавил в систему: Лазарев Александр Алексеевич