Все выпуски

Рассматривается усложненный вариант задачи маршрутизации «на узкие места», а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также «текущие» ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм «полного» решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана.

A complicated variant of the “bottleneck problem” is considered, namely: the problem of sequential visiting of megalopolises with preceding constraints. It is supposed that costs functions and “current” constraints with respect to displacements selection depend on the tasks list which is not completed at the moment. The variant of widely understood dynamic programming is proposed, it doesn't foresee (with preceding conditions) construction of the whole array of the Bellman function values; the special layers of this function realizing in its totality the partial array of its values are constructed (it helps to decrease the calculation complexity). An algorithm of the problem value (global extremum) calculation is proposed, the computer realization of which implies the existence of only one layer of the Bellman function in a memory of computer; the obtained value may be used for the heuristics testing. The optimal algorithm of “complete” solving of the route problem is constructed, within which all layers of the Bellman function are used at the route and trace constructing.