State cost estimation and early stopping of DP procedure for TSPs with profits

Continuing the series on DP for TSPs with profits (Orienteering Problem of not surpassing a certain threshold on the cost defined on the arcs of the graph while maximizing the profits defined on the graph's nodes and Prize Collecting TSP of minimizing the costs while surpassing a certain profit threshold), we present our results on estimating the cost of states and terminating the algorithm early, without having to calculate the costs for all of the states of the corresponding TSP—all of that for the mere metricity of the cost function.