Аннотация:
Доклад продолжает серию о задачах коммивояжера с прибылью — в
которых, кроме функции стоимость, заданной на перемещениях, также
присутствует отдельная стоимость, заданная на городах — задаче об
ориентировании (Orienteering Problem): собрать максимум по функции,
заданной на городах, не превысив порога для перемещинй по перемещениям
и задаче с призами (Prize Collecting TSP): потерять минимум по
функции, заданной на перемещениях, собрав необходимый минимум по
функции, заданной на городах.
В постановке ДП при достаточно обычных условиях ("метричность" функции
стоимости перемещений) может оказаться ненужным рассчитывать весь
массив значений функции Беллмана — состояния, не допустимые в связи
с превышением порога по перемещениям могут быть исключены; о теоремах,
позволяющих это осуществить и пойдет речь в докладе.
|
