К вопросу о нахождении значения маршрутной задачи с ограничениями

Abstract

Розглянуто задачу послідовного обходу мегаполісів з обмеженнями різних типів. Вважається, що функції вартості, а також «поточні» обмеження можуть залежати від списку завдань (можлива залежність від списку виконаних або, навпаки, ще не виконаних завдань). Запропоновано підхід до визначення глобального екстремуму (значення задачі) на основі динамічного програмування в широкому сенсі. Завдяки такому підходу досягається економія пам’яті комп’ютера, що дозволяє визначати экстремум в задачі більшої розмірності та використовувати його для тестування евристичних алгоритмів. Для побудови шарів функції Беллмана використовується скорочена процедура, що дозволяє зменшити складність обчислювань (за умов передування не передбачається побудова всього масиву значень функції Беллмана).

The problem of sequential travelling of megapolises with constraints of different types is considered. It is supposed that cost functions and «current» constraints can be dependent on the tasks list (it is possible that dependence on the fulfilled or nonfulfilled tasks arises). Approach to determination of global extremum (the problem value) on the basis of widely interpreted dynamic programming is proposed. Under given approach, economy of computer memory is reached; this permits to determine extremum in problem with larger dimensionality and use it for testing of heuristic algorithms. Under construction of layers of Bellman function, truncated procedure which enables one to decrease computing complexity is used (under preceding conditions, construction of all array of the Bellman function values is not provided).