Предлагается графический метод решения задач комбинаторной оптимизации, которые допускают декомпозицию и использование принципа оптимальности Беллмана при их решении. В отличие от алгоритмов динамического программирования, использующих тот же принцип, в графическом алгоритме все возможные состояния системы рассматриваются не отдельно, а группами. Это становится возможным, если принимать во внимание аналитический вид целевой функции, т.е. работать с «графиком» функции, преобразовывая его на каждой стадии аналитически. Графический метод позволяет значительно сократить трудоемкость решения некоторых задач и строить эффективные аппроксимационные схемы. Результаты численных экспериментов свидетельствуют об эффективности графического метода.
E.R. Gafarov (2016). Graphical method to solve combinatorial optimization problems. Automation and Remote Control, Volume 77, Issue 12, 2110–2117 (journal impact factor 2018: 0.589). Q2