Одна параллельная процедура построения функции Беллмана в обобщенной задаче курьера с внутренними работами

Рассматривается схема решения экстремальной задачи маршрутизации с ограничениями в виде условий предшествования, основанная на одной модификации метода динамического программирования. Основное внимание уделяется вопросу, связанному с распараллеливанием процедуры построения слоев функции Беллмана. Предлагается гипотетическая конструкция такого распределения пространства позиций между процессорами, при котором они могут работать без какого-либо обмена информацией вплоть до последнего этапа вычислений.

Статья представлена к публикации членом редколлегии: А. И. Кибзун