1

道具 A. 我写了一个邮政编码服务器,它给了我 32,000 个美国邮政编码。每个邮政编码都有一个关联的经纬度。给定 2 个邮政编码,我可以使用它们的经纬度找到它们之间的距离。

道具 B。我还编写了一个天气服务器,您可以在其中输入最多 200 个邮政编码,它会输出每个邮政编码的温度。

有人告诉我他的邮政编码是 Z,温度是 T。他问我,离 Z 最近的地方是哪里,那里的温度至少低 10 度?

因此,我从 Z 中得到了一个按距离排序的 200 个邮政编码列表(使用 Prop A)。我把它喂给 B 并得到 200 个温度。如果没有一个是 10 度,我会得到接下来的 200 个邮政编码并重复直到完成。

问题:这似乎非常低效和蛮力。我觉得我缺少一些物理洞察力。并非总是如此,如果您向北行驶,温度会降低,而向南行驶会升温。所以方向没有帮助。海拔高度可能会(山比山谷凉爽),但很难找到与海拔高度相关的邮政编码数据。

你们能想出一些更聪明的方法来解决这个问题吗?任何建议表示赞赏。注意:天气数据很昂贵。您只能点击天气服务器几次,每次只能获得 200 个温度。(otoh,任何 2 个邮政编码之间的距离都是预先计算的常数,并且不需要任何成本。)

4

3 回答 3

0

我同意物理论坛的评论,即这不是一个物理问题,但物理学(或至少是数学)的一些见解可能确实是有序的。如果您能够廉价地获得天气数据,您也许可以建立一个数据集并执行一次分析来指导您的搜索。

具体来说,同时记录每个位置的温度。然后,对于每个位置,计算每个相邻邮政编码的温度变化,并将其与相对坐标(即到相邻邮政编码的方向)相关联,并按温度排序存储此列表。当有人输入查询 zip 时,您的算法将从列表顶部的 zip 开始,然后向下运行。每个不满意的答案都被添加到堆栈中。如果相邻的拉链都不符合标准(在这种情况下冷却 10 度),则算法将开始通过新堆栈重复该算法。

我不是一个出色的程序员,所以我不会给出任何代码,但在我看来,这会比蛮力搜索更好地“遵循”温度图的自然轮廓,并且会在结果的接近性上保持首要地位。如果您使用多个并发温度测量设置初始数据集,则可以对这些数据进行时间平均以获得更好的性能。

于 2011-08-24T20:27:11.847 回答
0

您可以通过对所有邮政编码进行二进制排序并在排序列表中获取所有低于用户邮政编码的所有邮政编码,然后对该子集执行相同的距离。这应该相当快 - 二进制排序是 log(n),所以你不会在排序上自杀。

于 2011-08-24T20:10:48.403 回答
0

这最适合stackoverflow。

合并数据库。

编写查询 abs(lat-lat_o) + abs(long-long_0) < 2.00 AND temp < temp_0 - 10。该查询将利用您服务器上的索引。

如果没有结果,将 2.00 增加一个倍数并重复。

如果结果,找到最接近的。如果最近的距离比边界框的最近边缘更远,请保存该条目并将该距离增加 2.000,然后查看其中一个是否更近。

扩展,有效地使用数据库。

于 2011-08-24T22:25:14.083 回答