Optimum cone filling with direct access dispenser
Suppose the conveyor belt moves from right to left. Below I will describe a way to formulate and solve the problem in such a way as to fill the number of maximum possible cones, under the assumption that the dispenser never moves to the left faster than the conveyor. For n cones, the main algorithm has a very loose (see below) upper time limit of O (n ^ 3) and O (n ^ 2) - this should be possible for up to 1000 cones or so. If you have more cones than this, you can break them into blocks no larger than this size and simply process each block one by one. There is also a way to ease the restriction on moving back and forth a bit and thus potentially fill more cones, without the whole problem becoming exponential - I will describe this later.
Suppose that all cones have positive x coordinates and that the hose length reaching area, which initially extends from x = 0 to the left to x = -P, moves to the right above the cones, which themselves remain stationary. Thus, at time t, the hose pipe coverage area will extend from x = U * t to the left to x = U * t - P. When describing the position of the dispenser, I will always use the same (that is, absolute) ordinate system; we will ensure that it remains in the actual position (inside the scope of the hose), ensuring that at any time t its location x is between U * t - P and U * t. Please note that the pairs (time, cone ID) are enough to fully determine the position of both the hose coverage area and the dispenser, if we interpret this as meaning that the dispenser is directly above the cone at a given time. (Later this will help simplify the description of the state of the system.) Finally, I will name any movement of the dispenser that does not reduce its absolute coordinate x (this includes any reverse movement relative to its body, which is lower in speed than U, and also no movement at all ) "forward", as well as any movement "backward".
Dynamic programming language
Sort the cones by increasing the x position, arbitrarily breaking the bonds. Let (x_i, y_i) be the position of the ith cone in this sorted order.
Let e (i) be the earliest time when we could essentially position the dispenser over the cone i, if it were the only cone we cared for, and the dispenser was already “waiting” in the correct vertical position (namely, y_i) at the far right of the hose coverage area: it's just x_i / U.
Let m (i, j) be the time required to move the dispenser from the cone i to the cone j, assuming that this is possible without waiting for someone to “scroll through the image”: it can be easily calculated for any pair (i, j) from their coordinates and speeds V and U (this remains true even if the dispenser can simultaneously move with arbitrary speeds V_x and V_y in the x and y directions).
Now we will move on to the function, which is the key to effectively solving this problem:
Let f (i, j) be the earliest time when we could finish filling the cone i so that we still fill exactly j cones (including this one, therefore 1 <= j <= i) or infinity if this is not possible . Let g (i, j) be an auxiliary function that is defined identically, except that we allow the last step of filling the cone to advance the dispenser too far to the left (you will see why in a minute). We can compute g (i, j) and, more importantly, f (i, j) as follows:
g(i, j) = max(e(i), minimum of f(k, j-1) + m(k, i) over all k st j <= k < i) + T f(i, j) = IF U * g(i, j) - P <= x_i THEN g(i, j) ELSE infinity
What a mess! Release part by part.
The term f(k, j-1) + m(k, i) is the least amount of time it takes to fill j-1 cones ending in cone k, then move the dispenser to cone i. max(e(i), ...) around this ensures that if the movement implied by the above term leads to the dispenser moving too far to the right (i.e., to some x-coordinate> U * t), this will not be accepted. Instead, we will move the dispenser to (U * t, y_i), that is, to the correct y coordinate for the cone I and as far as possible, and then wait for the cone to scroll (and therefore appear directly under the dispenser) at time e (i). Regardless of which of these actions we take, it then takes another T units of time to fill the cone i.
(Technically, the above calculation assumes that if it is possible to move the dispenser to (x_i, y_i) for some given time t, then you can also move it to (U * t <x_i, y_i) at the same time at the latest. since our initial location x is <= U * t, the only way this can not be held back is if the function describing the time required to move between two given points violates the triangle inequality - something that does not happen when the hose moves relative to its body with constant soon Tew V or independently in two directions with constant speed and V_x V_y or does not use any crazy drive system.)
How about the left edge of the hose coverage area? U * g(i, j) - P is the position of the left edge of this region at time moment g (i, j). Since this time is the earliest possible time that we could finish the task of filling j cones, the last of which is cone i, this expression gives the leftmost possible position in which the left edge of the hose pipe coverage area can be located when the task is completed. Therefore, if this position remains to the left of x_i, this means that we can actually fill the cone I after those j-1 previous cones, but if this is not so, we know that trying to do this will make the dispenser too far to the left (this can happen when trying to go to the cone I or when filling it - it does not matter). Thus, in the latter case, we reduce the time cost associated with task f (i, j), up to infinity, ensuring that it will not be used as part of the solution for any larger subtask.
Use of time and space
The calculation of any value of f (i, j) takes O (n) time, therefore, the calculation of all O (n ^ 2) of these values takes O (n ^ 3). However, in practice, we are unlikely to need to take into account all possible values of k that are less than i in the minimum indicated above. In addition to the fact that the sequence of movements, implied by f(i, j) , remains doable, max(e(i), ...) also the key to great practical acceleration: as soon as we serve on ak, which leads to that e (i) the term “hit in” (becoming the larger of the two terms compared with max() ), it will remain the best possible option - since any subsequent k, which is designed to provide a faster completion of the task, necessarily includes a push dispenser too far right in the last step. This means that we do not need to try to fulfill any of these other values of k: e (i) is indeed a real minimum.
If all we wanted to calculate was the minimum time needed to fill a certain given number of cones, we could actually do this only in O (n) space, using the fact that when calculating f (i, j), we we get only the previous values of f () having the second argument equal to j-1. But since we really want a sequence of actions corresponding to such a minimum time , we will need to write a table of predecessors p [i] [j], and this requires O (n ^ 2) space.
pseudo code
Sort cone[1 .. n] by increasing x co-ord. Compute e[i] for all 1 <= i <= n. Set f[i][1] = e[i] + T for all 1 <= i <= n. Set f[i][j] = infinity for all 1 <= i <= n, 2 <= j <= i. maxCones = 0. bestTime = infinity. # Compute f(i, j) for all i, j. For j from 2 up to n: For i from j up to n: g = infinity. # Best time for f(i, j) so far. For k from j up to i-1: z = f[k][j-1] + m(k, i) + T. If z < g: p[i][j] = k. If z < e[i] + T: g = e[i] + T. Break out of innermost (k) loop. Else: g = z. If U * g - P <= cone[i].x: f[i][j] = g. If maxCones < j or (maxCones == j and g < bestTime): maxCones = j. # New record! bestI = i. bestTime = g. Else: f[i][j] = infinity. # Trace back through p[][] to find the corresponding action sequence. For j from maxCones down to 1: fill[j] = bestI. bestI = p[bestI][j].
After doing this, maxCones will contain the maximum number of cones that can actually be filled, and if it is> = 1, then fill[1] through fill[maxCones] will contain the corresponding sequence of maxCone cone identifiers (positions in the sorted sequence), and the total time necessary for this will be in bestTime .
Possible improvements
The above algorithm solves the problem optimally only if it is limited that the dispenser never moves back too fast. In practice, this can be quite restrictive: for example, a cone model similar to the following
XXXX XXXX
will cause the distributor to make a long vertical stroke between each cone filled with it (provided that he can fill all of them). Filling several cones on one line and only then moving to another line will save a lot of time.
The difficulty of solving the problem optimally without the restriction above is that it starts to resemble very strongly some NP-hard problems, such as the Euclidean TSP problem. I don’t have time to look for a formal abbreviation, but I’m sure that the unlimited version of your problem is NP-hard, so the best we can hope to do with the polynomial time algorithm is to look for a good heuristic. For this purpose:
The DP solution above basically finds for each cone i the best way to fill the j cones as a whole, ending on the cone i and using only the other cones to the left of it. We can solve a slightly more general problem by breaking the sorted sequence of cones into adjacent blocks of b cones, and then finding for each cone I’m the best way to fill j cones in the sum that ends on cone i and use only cones that are either (a) in the earlier block (these cones should be to the left of i), or (b) in the same block as I (these cones are not necessary). The only solutions that are not taken into account in this approach are those that require us to fill the cone in some block, and then fill the cone in an earlier block (this includes, in particular, all the solutions in which we fill the cone in some block, cone into another block, and then another cone in the first block - at least one of the two movements between the blocks must be moved to the previous block).
Obviously, if we choose b = n, then this will find a common optimum (in a million years), but b should not be somewhere close to this large in order to get the optimal solution. Using a variation, the O (n ^ 2 * 2 ^ n) DP algorithm to solve the TSP to help calculate the optimal paths inside the block, choosing b = 10, say, would be quite feasible.
Another assumption is that instead of fixing the block size to exactly b, the cones at first could be more reasonably divided into blocks of size no more than b, that is, in such a way that the (unknown) optimal solution rarely had to fill the cone in previous block. In fact, provided that it is possible to heuristically evaluate the “quality” of a breakpoint (for example, using the minimum distance between any pair of points in 2 blocks), calculating a lock pattern that maximizes the estimate can be easily performed during O (bn) using (other) DP!