How to find the minimum sum of multiple different routes

Question

Valkmi 2016-9-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/303859-how-to-find-the-minimum-sum-of-multiple-different-routes

评论： Valkmi 2016-9-21

Hi everyone, this is my first question and I appreciate for all the help I can get. I'm having a problem solving the following problem:

For example: x1 = 2

x2 = 3

x3 = 1.5

y1 = 5

y2 = 4

y3 = 1

z1 = 2

z2 = 4

z3 = 2

I need to find the minimum sum of x,y and z while the indices 1,2,3 are only used once, for example the solution could be x1 + y2 + z3 or z1 + x2 + y3. In this case the solution would be z1 + x2 + y3. This is simple version of the problem, in reality I have much more data, which is why I need to create this algorithm.

2 个评论
显示无隐藏无

Adam 2016-9-21

编辑：Adam 2016-9-21

It would be trivial to do in a nested for loop using circshift and sum, but I'm sure someone can come up with a better solution that that.

As an aside though don't name your variables like that.

Either put them all in one 3 x 3 array of have 3 arrays x, y, z each of length 3, depending which works better for your solution.

John D'Errico 2016-9-21

编辑：John D'Errico 2016-9-21

Yes. Just put your data in an array. You will gain greatly learning to use arrays.

Just as important, tell us what the real problem is. Is this a problem where you have n variables, each of which can appear in the sum only once? In that case, the problem has complexity of factorial(n), so expect it to be quite difficult to solve if n is at all large.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Steven Lord 2016-9-21

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/303859-how-to-find-the-minimum-sum-of-multiple-different-routes#answer_235509

This sounds like the assignment problem. The matrix formulation of the Hungarian algorithm linked to by that page shouldn't be too difficult to implement in MATLAB.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Valkmi 2016-9-21

That was exactly what is was looking for, thank you! In the bottom of the Hungarian algorithm wikipedia page is a link to MATLAB implementation of this algorithm.

请先登录，再进行评论。