I have a interesting question that is related to calculating the shortest distance. However, rather than choosing a path for any given graph (vertices and edges), in this problem, the path is given and it requires generating a graph under certain constraint.

So let’s go through this problem in a bit more detail:

Problem

There is a fixed amount of positions (N) into which we need to place N different objects. The traveling distance between all the positions are pre-determined and fixed. The task includes a sequence of objects to pick in an order that cannot be changed and the same objects can be picked multiple times. The question is how to place those objects in an order so that the total traveling distance can be minimized.

Example

Now, let’s give an example.

Position

Assuming that we have 4 positions in a 1D dimension (list). And we can easily calculate the pair wise distance between those positions.

	P0	P1	P2	P3
P0	0	1	2	3
P1		0	1	2
P2			0	1
P3				0

Task

Now let’s go through our task. Our task might be any sequence of any length of different combinations of 4 objects. For example, it could be 1232213. It means first to pick up object1, and then pick up object2, then 3 so on and so forth. To calculate the total distance, it is as simple as adding up the distance between each objects. (for the first element and last element, we can simply by assuming a situation which all picks needs to originates from a starting point and ending point that doesn’t belong to any of these positions, but they take equal amount of travel to go to all the positions). In that case, our total distance will be:

Total Distance (1212103) = Const + D(1,2) + D(2,1) + D(1,2) + D(2,1) + D(1,0) + D(0,3) + Const

Distance is a function of positions and to pick objects, objects will be mapped to the position.

Distance between two objects x, y = D(p(x), p(y)) where p is one mapping

Scenario1

Keep in mind that the numbers above are not indices to positions, they are objects. But if we put all the objects in the same order as the positions, the calculation is as straight forward as:

Total Distance (1212103) = Const + D(1,2) + D(2,1) + D(1,2) + D(2,1) + D(1,0) + D(0,3) + Const
= … + 1 + 1 + 1 + 1 + 1 + 3 … = 8

Simple right? in this case, for this type of positioning, we achieve a total cost of 10.

Scenario2

Now let’s try a different positioning, let’s swap the position of object0 and object1.

	P0 (O1)	P1(O0)	P2 (O2)	P3 (O3)
P0 (O1)	0	1	2	3
P1 (O0)		0	1	2
P2 (O2)			0	1
P3 (O3)				0

Total Distance (1212103) = Const + D(1,2) + D(2,1) + D(1,2) + D(2,1) + D(1,0) + D(0,3) + Cons
= D(0,2) + D(2,0) + D(0,2) + D(2,0) + D(0,1) + D(1,3)
= 2 + 2 + 2 + 2 + 1 + 2 = 11

So far, we have two different positioning and each yields a different total traveling distance. And the default one is considered better than the second one.

The goal is to find the most optimized positioning that yields the shortest total distance.

Bruce Force

Here is a small demo of the bruce force approach given 4 objects at 4 positions. There are in total 4! = 24 different permutations and there are two positioning that yield that shortest distance. Luckily, one of the examples that we covered above happens to the the most optimal solution.

I have thought about some of the previous models that I have worked with but none seems to be a good match right off the bat. For example, the Dijkstra is to find the shortest path or sequence given the graph, the Knapsack’s is to find the subset of the goods to maximize the weight.

Now the question is can we find an existing algorithm that solve this problem in an efficient way, if so, how efficient?