Оценивание состояний и ранняя остановка алгоритма в задачах коммивояжера с прибылью

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