Алгоритмы упорядочения переменных в локальном элиминационном алгоритме

Журнал: 
Страница: 
81
УДК: 
519.68
 В работе рассмотрены пять алгоритмов упорядочивания переменных для решения разреженньїх задач дискретной оптимизации с помощью алгоритма несериального динамического программирования. В результате проведенного вычислительного экс-перимента, во-первнх, было отмечено, что для решения разреженных задач дискрет­ной оптимизации, упорядочивание переменных оказывает значительное влияние на время решения задачи. Помимо этого, было показано, что различные звристики упо­рядочивания наиболее зффективны для различных классов задач. И, наконец, было отмечено, что эвристики MCS и MIN-FILL показали наилучший результат для ре­шения задач дискретной оптимизации из предложенньїх классов тестовнх задач.  
info_eng: 
 Five ordering algorithms for the nonserial dynamic programming algorithm for solving sparse discrete optimization problems are considered. As a result of benchmarking, firstly, it was noted that for solving sparse discrete optimization problems, the ordering of the variables has a significant impact on the run-time of solving the problem. In additon? it was shown that the different heuristics ordering are most effective for different classes of problems. And finally, it was noted that heuristics MCS and MIN-FILL showed the best result for solving discrete optimization problems of the considered class of the problems.