距离最小化总：优化问题 [英] Minimizing Sum of Distances: Optimization Problem

问题描述

实际的问题是这样的：

麦当劳计划开设一些关节（说N）沿直线高速公路。这些关节需要仓库来存储他们的食物。仓库可以储存食物为任何数目的接头，但现在将位于只关节之一。麦当劳有仓库的数量有限（说k）的可用的，并希望将它们以这样的方式从它们的最接近的仓库关节的平均距离被最小化。

McDonald's is planning to open a number of joints (say n) along a straight highway. These joints require warehouses to store their food. A warehouse can store food for any number of joints, but has to be located at one of the joints only. McD has a limited number of warehouses (say k) available, and wants to place them in such a way that the average distance of joints from their nearest warehouse is minimized.

由于数组（n个元素）关节坐标的整数'K'返回'K'元素让仓库的最佳定位的坐标的数组。

Given an array (n elements) of coordinates of the joints and an integer 'k', return an array of 'k' elements giving the coordinates of the optimal positioning of warehouses.

对不起，我没有用，因为我是从内存中写下来的任何实例。无论如何，一个样品可能是：

Sorry, I don't have any examples available since I'm writing this down from memory. Anyway, one sample could be:

阵列= {1,3,4,5,7,7,8,10,11}（N = 9）
K = 1

array={1,3,4,5,7,7,8,10,11} (n=9)
k=1

答：{7}

这是我一直在想：对于k = 1，我们可以简单地找出一套，这将使仓库的最佳位置的中位数。然而，对于k> 1，所述给定集合应该分成数k子集（不相交，和的超集的连续元素），和平均对于每个子集将给予仓库的位置。不过，我不明白在什么基础上的'K'子集应该形成。先谢谢了。

This is what I've been thinking: For k=1, we can simply find out the median of the set, which would give the optimal location of the warehouse. However, for k>1, the given set should be divided into 'k' subsets (disjoint, and of contiguous elements of the superset), and median for each subset would give the warehouse locations. However, I don't understand on what basis the 'k' subsets should be formed. Thanks in advance.

编辑：有一个变化这个问题也：不是总和/平均，最大限度地减少了联合及其最亲密的仓库之间的最大距离。我真不明白这一点无论..

There's a variation to this problem also: Instead of sum/avg, minimize the maximum distance between a joint and its closest warehouse. I don't get this either..

推荐答案

直的高速公路，使这实乃动态规划，从左至右沿公路右侧工作。甲部分解决方案可以通过最右边的仓库的位置并置于仓库数进行说明。部分解决方案的成本将是到最近的仓库的总距离（对于固定ķ最小化，这是一样的最小化averge）或最大距离迄今为最接近的仓库。

The straight highway makes this an exercise in dynamic programming, working from left to right along the highway. A partial solution can be described by the location of the rightmost warehouse and the number of warehouses placed. The cost of the partial solution will be the total distance to the nearest warehouse (for fixed k minimising this is the same as minimising the averge) or the maximum distance so far to the closest warehouse.

在每一个阶段，你已经工作了答案最左边ñ关节和让他们通过使用仓库的数量，最右边的仓库位置索引 - 你需要保存只有最好的成本。现在考虑下联合制定出了N + 1的关节和k和最右边的仓库的所有可能值的最佳解决方案，使用已存储的N个关节的答案加快这。一旦你已经制定了涵盖所有你知道的关节最佳性价比的解决方案，其中最右边的仓库，它给你的一个仓库的位置。返回到具有仓库作为最右边的联合解决方案，并发现，是基于什么样的解决方案。这给你一个最右边的仓库 - 所以你可以用自己的方式工作，回到所有仓库的最佳解决方案的位置

At each stage you have worked out the answers for the leftmost N joints and have them indexed by number of warehouses used and position of the rightmost warehouse - you need to save only the best cost. Now consider the next joint and work out the best solution for N+1 joints and all possible values of k and rightmost warehouse, using the answers you have stored for N joints to speed this up. Once you have worked out the best cost solution covering all the joints you know where its rightmost warehouse is, which gives you the location of one warehouse. Go back to the solution that has that warehouse as the rightmost joint and find out what solution that was based on. That gives you one more rightmost warehouse - and so you can work your way back to the location of all the warehouses for the best solution.

我特意去工作了这一点，错误的成本，而且有N个节点和K仓库的地方，你有N个要采取的步骤，每一个的基础上考虑不超过NK previous解决方案的更多，所以我认为成本千牛^ 2。

I tend to get the cost of working this out wrong, but with N joints and k warehouses to place you have N steps to take, each of the based on considering no more than Nk previous solutions, so I reckon cost is kN^2.

这篇关于距离最小化总：优化问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！