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