所有旅行时间的最小总和

我在interviewStreet网上找到了一个谜题,并尝试按如下方式解决:

有一个无限的整数网格,N人有他们的房子。 他们决定团结在一个共同的聚会场所,这是一个人的家。 从任何给定的小区,所有8个相邻小区在1个单位时间内可达。 例如:(x,y)可以在一个单位时间内从(x-1,y + 1)到达。 找到一个共同的会面地点,最大限度地减少所有人的旅行时间总和。

我首先想到的是及时编写n²复杂度的解决方案,但约束条件是

1 <= N <= 10 ^ 5并且输入中每个坐标的绝对值将至多为10 ^ 9

所以,我改变了我的第一种方法,而不是考虑距离和旅行时间的问题,我把不同的房子看作不同的身体,不同的重量。 而不是计算所有距离,我寻找这组物体的重心。

这是我的“求解”函数的代码,vectorToTreat是一个lengthX2表,存储有关网格上各点的所有数据,结果是打印到stdout的数字:

long long solve(long long** vectorToTreat, int length){ long long resul = 0; int i; long long x=0; long long y=0; int tmpCur=-1; long long tmp=-1; for(i=0;i<length;i++){ x+=vectorToTreat[i][0]; y+=vectorToTreat[i][1]; } x=x/length; y=y/length; tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y)); tmpCur = 0; for(i=1;i<length;i++){ if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){ tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y)); tmpCur = i; } } for(i=0;i<length;i++){ if(i!=tmpCur) resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1])); } return resul; } 

现在的问题是我通过了12个官方测试案例超过13个,我不知道我做错了什么想法? 提前致谢。 AE

这个问题的关键是一组点的质心概念。 会议地点是代表所有房屋的一组点的质心最近的房子。 使用这种方法,您可以在线性时间内解决问题,即O(N)。 我在Python中完成了它,提交了我的解决方案并通过了所有测试。

但是,很容易构建质心方法不起作用的数据集。 这是一个例子:

 [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3), (3, 0), (3, 1), (3, 2), (3, 3), (101, 101)] 

最好的解决方案是在(2,2)的房子会议,成本是121(你可以通过详尽的搜索找到它 – O(N ^ 2))。 但是,质心方法会产生不同的结果:

  • 质心是(7,7)
  • 离质心最近的房子是(3,3)
  • 在(3,3)见面的费用是132

网站上的测试用例显然是以质心解决方案正常的方式塑造的,或者他们只是想知道你是否知道质心的概念。

我没有阅读您的代码,但请考虑以下示例:

  • 2个人住在(0,0)
  • 1个人住在(2,0)
  • 4个人住在(3,0)

重心位于(2,0),总行程时间最短为8,但最佳解决方案为(3,0),总行程时间最短为7。

您好,感谢您的回答和评论,他们非常乐于助人。 我终于放弃了使用重心的算法,当我在其上运行一些样本时,我注意到当房屋聚集在不同村庄时,它们之间的距离不同,算法不起作用。 如果我们考虑@Rostor上面所说的例子:

(0,0),(1,0),(2000,0),(3000,0),(3001,0),(3002,0),(3003,0)

使用重心的算法回答第三宫是解决方案,但正确的答案是第四宫。 在这种问题中使用的正确概念是中位数,并使其适应所需的维度。 这是一篇很棒的文章,谈论几何中位数 ,希望它有所帮助。

解:

  1. 如果所有点都排成一行,人们只能在2次干扰中移动(左右)

    如果它们仅向左移动则对两个数组进行排序并计算两个数组,如果它们仅向右移动则计 添加两个向量并找到最小值以找到解决方案

  2. 如果人们只能移动4个方向(左,下,上,右)你可以应用相同的规则,你需要支持的是当你在一个轴上排序时你必须能够回来,所以在排序时你还必须保存排序排列

  3. 如果人们可以在8个方向上移动(如问题所示),你可以使用与在4个方向上使用相同的算法(2.算法),因为如果你正确地观察到移动,你可以看到如果每个人都可以做出相同数量的移动只对角线移动并且不需要它们向左,向右和向下移动,但只有左上,右上,左下和右下,如果每个点(x,y)都保持(x +) y)%2 == 0 – 想象网格是棋盘,而房屋只在黑色方块上

    在应用2. algorhitm之前,你必须进行点变换

    (x,y)变为(x + y,xy) – 这是点旋转45度。 然后你应用2. algorhitm并将结果除以2。

“……这是某人的房子”意味着你选择一个被占用的房子,而不是一个任意的位置。

编辑 :oops,max(abs(aA),abs(bB))替换(abs(aA)+ abs(bB))。 当p-> infinty时,请参阅L_p空格以获取更多详细信息。

从(a,b)到(A,B)的距离是max(abs(aA),abs(bB))。 蛮力的方式是计算每个被占用房屋的总出行时间,跟踪到目前为止最好的会面地点。

可能还要等一下。 质心中心排序可以允许您确定搜索顺序的优先级。 我看到你正在使用这个指标的良好质心计算:采用第一个坐标的简单平均值和第二个成分的简单平均值。

如果您对距离函数有所了解,可以得到(x1,y1)和(x2,y2)之间的旅行时间

 def dist( (x1,y1), (x2,y2)): dx = abs(x2-x1) dy = abs(y2-y1) return max(dx, dy) 

如果在带有网格的纸张上绘制草图,则可以看到。

因此,您只需要遍历每个房子,总结其他房屋的旅行时间,并以最低金额购买房屋。

完整的解决方案是

 houses = [ (7,4), (1,1), (3,2), (-3, 2), (2,7), (8, 3), (10, 9) ] def dist( (x1, y1), (x2, y2)): dx = abs(x1-x2) dy = abs(y1-y2) return max(dx, dy) def summed_time_to(p0, houses): return sum(dist(p0, p1) for p1 in houses) distances = [ (summed_time_to(p, houses), i) for i, p in enumerate(houses) ] distances.sort() min_dist = distances[0][0] print "best houses are:" for d, i in distances: if d==min_dist: print i, "at", houses[i] 

我在scala中编写了一个快速且脏的网格距离测试器,它将平均值与穷举搜索的最小值进行比较:

 class Coord (val x:Int, val y: Int) { def delta (other: Coord) = { val dx = math.abs (x - other.x) val dy = math.abs (y - other.y) List (dx, dy).max } override def toString = " (" + x + ":" + y + ") " } def run (M: Int) { val r = util.Random // reproducable set: // r.setSeed (17) val ucells = (1 to 2 * M).map (dummy => new Coord (r.nextInt (M), r.nextInt (M))).toSet take (M) toSeq val cells = ucells.sortWith ((a,b) => (ax < bx || ax == bx && ay <= by)) def distanceSum (lc: Seq[Coord], cell: Coord) = lc.map (c=> cell.delta (c)).sum val exhaustiveSearch = for (x <- 0 to M-1; y <- 0 to M-1) yield (distanceSum (cells, new Coord (x, y))) def sum (lc: Seq[Coord]) = ((0,0) /: lc) ((a, b) => (a._1 + bx, a._2 + by)) def avg (lc: Seq[Coord]) = { val s = sum (lc) val l = lc.size new Coord ((s._1 + l/2) / l, (s._2 + l/2) / l) } val av = avg (ucells) val avgMethod = distanceSum (cells, av) def show (cells : Seq[Coord]) { val sc = cells.sortWith ((a,b) => (ax < bx || ax == bx && ay <= by)) var idx = 0 print ("\t") (0 to M).foreach (i => print (" " + (i % 10))) println () for (x <- 0 to M-1) { print (x + "\t") for (y <- 0 to M -1) { if (idx < M && sc (idx).x == x && sc (idx).y == y) { print (" x") idx += 1 } else if (x == av.x && y == av.y) print (" A") else print (" -") } println () } } show (cells) println ("exhaustive Search: " + exhaustiveSearch.min) println ("avgMethod: " + avgMethod) exhaustiveSearch.sliding (M, M).toList.map (println) } 

这是一些示例输出:

 run (10) 0 1 2 3 4 5 6 7 8 9 0 0 - x - - - - - - - - 1 - - - - - - - - - - 2 - - - - - - - - - - 3 x - - - - - - - - - 4 - x - - - - - - - - 5 - - - - - - x - - - 6 - - - - A - - x - - 7 - xx - - - - - - - 8 - - - - - - - - - x 9 x - - - - - - - - x exhaustive Search: 36 avgMethod: 37 Vector(62, 58, 59, 60, 62, 64, 67, 70, 73, 77) Vector(57, 53, 50, 52, 54, 57, 60, 63, 67, 73) Vector(53, 49, 46, 44, 47, 50, 53, 57, 63, 69) Vector(49, 46, 43, 41, 40, 43, 47, 53, 59, 66) Vector(48, 43, 41, 39, 37, 37, 43, 49, 56, 63) Vector(47, 43, 39, 37, 36, 37, 39, 46, 53, 61) Vector(48, 43, 39, 36, 37, 38, 40, 43, 51, 59) Vector(50, 44, 40, 39, 38, 40, 42, 45, 49, 57) Vector(52, 47, 44, 42, 42, 42, 45, 48, 51, 55) Vector(55, 52, 49, 47, 46, 47, 48, 51, 54, 58) 

平均值并不总是最佳位置(如本例所示),但您可以跟随具有更高或更好价值的邻居,找到最佳位置。 这是一个很好的起点,我在下面找到了一个局部最优样本,你会陷入困境。 这对于庞大的数据集来说非常重要。

但我没有certificate这是否总是如此,以及如何直接找到完美的位置。

这就是我所做的

 def abs(a) (a < 0) ? -a : a end # Calculate distance between cell(i) to cell(j) # # a and b are point structures each having x, y co-ordinate def dist(a, b) if ((a[0] == b[0]) && (a[1] == b[1])) return 0 end del_row = abs(a[0] - b[0]) del_col = abs(a[1] - b[1]) if (del_row == del_col) return del_row else return del_row > del_col ? del_row : del_col end end # Find the median cell from an array of cells def find_median(array) # If array is of even length, the median element is not in the array. We've to consider # two adjacent elements of the median. For odd case we've just one median n = array.length # Median finding can be done at O(n)... # # Sort cell array - O(nlogn) array = array.sort do |cell1, cell2| # Try first by comparing x if (cell1[0] != cell2[0]) cell1[0] < cell2[0] ? -1 : 1 else # Resolve tie by comparing y cell1[1] <=> cell2[1] end end # Find median k = n / 2 median_element = [] if ((n % 2) == 0) median_element << array[k] median_element << array[k+1] else median_element << array[k] end median_element end # Calculate travel time given an array of cells and a cell indicating the meeting point def calculate_travel_time(array, meeting_cell) travel_time = 0 array.each do |cell| # Skip the meeting cell itself if (!((cell[0] == meeting_cell[0]) && (cell[1] == meeting_cell[1]))) travel_time = travel_time + dist(cell, meeting_cell) end end travel_time end def figure_out_the_meeting_point(array) if (array.nil?) return 0 end n = array.length if (n == 0) return 0 end if (n == 1) # Lonely person return 0 end if (n == 2) # Just two neighbors return dist(array[0], array[1]) end # Find median median = find_median(array) median_length = median.length min_travel_time = 0 meeting_point = nil if (median_length == 1) min_travel_time = calculate_travel_time(array, median[0]) meeting_point = median[0] else # We've two candidates. Need to check minimum of them t_first_median = calculate_travel_time(array, median[0]) t_second_median = calculate_travel_time(array, median[1]) if (t_first_median < t_second_median) min_travel_time = t_first_median meeting_point = median[0] else min_travel_time = t_second_median meeting_point = median[1] end end return min_travel_time, meeting_point end # Handle STDIN and STDOUT for I/O def handle_io() STDOUT.flush n = gets.to_i array = [] (n).times do STDOUT.flush s = gets array << s.split(' ').map(&:to_i) end array end tt, mp = figure_out_the_meeting_point(handle_io) puts tt puts mp 

网格是无限的。 因此,解决方案应该是整数溢出安全的。 我已经检查了大量的int并且Ruby正确地按照预期将它们转换为BigNum。

知道为什么我没有通过所有测试用例。

我尝试使用几何中位数的方法来解决这个问题。 但13个测试用例中只有11个通过。 这是我的策略。

 1. finding centroid of a set of points. 2. then found the point closest to that centroid. 

我甚至试过但只通过了13个测试用例中的4个。 他们说,分段故障。

但我已经制作了两个100001的数组,并使用了一些变量。

我的算法。

找到给定点的质心。

找到最靠近质心的点。 使用最大值(abs(aA),abs(bB))得到所有距离的总和。