25447

Автор(ы): 

Автор(ов): 

2

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems

Электронная публикация: 

Да

ISBN/ISSN: 

ISSN 0898-1221

Наименование источника: 

  • Mathematical and Computer Modelling

Обозначение и номер тома: 

58, No.4

Город: 

  • Oxford

Издательство: 

  • Elsevier Science

Год издания: 

2009

Страницы: 

619-631. http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a
Аннотация
In this paper, we consider a graphical realization of dynamic programming. The concept is discussed on the partition and knapsack problems. In contrast to dynamic programming, the new algorithm can also treat problems with non-integer data without necessary transformations of the corresponding problem. We compare the proposed method with existing algorithms for these problems on small-size instances of the partition problem with n≤10 numbers. For almost all instances, the new algorithm considers on average substantially less “stages” than the dynamic programming algorithm.

Библиографическая ссылка: 

Лазарев А.А., Werner F. A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems / Mathematical and Computer Modelling. Oxford: Elsevier Science, 2009. 58, No.4. С. 619-631. http://www.zentralblatt-math.org/zmath/en/search/?q=ai:lazarev.alexander-a.