0

你能想到任何维度和任何度量中最近的点对和最远的点对的任何用法吗?

这是我的想法。

最近的一对点:

  • 测试- 我们有一组点,例如某些公司拥有的一些实验室;公司建有传送器;它只能在这些实验室中重建,因为例如他们的墙壁是用黄金建造的,并且出于某种原因需要将传送器封装在黄金房间中;但是一个传送器会产生磁场,如果他们在一个学院中建造 2 个传送器,磁场会干扰,它们将无法工作;并且他们想要测试它们,最好先测试它们尽可能小的距离;所以他们必须找到两个彼此最近的实验室
  • 许多旅行- 点是医院;每家医院正好有 1 公斤青霉素(或任何药物);X先生每天需要1.5公斤的青霉素才能生存;每家医院每天得到这1公斤的药物;因此,X 每天必须访问 2 家医院;他会搬到这个国家的任何地方,但他不想每天都去很远的地方
  • 遗传学- 点是人;我们想找到两个 DNA 最接近的人(这并不符合我们如何计算两个人之间的距离);为什么?因为例如他们想知道我们彼此之间的距离有多近,以及我们必须改变一个人的最少核碱基数量是多少才能使他足够不同
  • 遗传学 II - 点是人,但我们用外表来衡量他们之间的距离;例如,我们快要毁灭了,我们需要派一个人去执行一个他可能会死的任务;我们有一个完成任务所必需的设备,但它只适用于它通过外观识别的一个人(并且它的验证机制非常精确)所以我们需要找到两个尽可能相似的人

最远的一对点:

  • 测试——我们已经成功地测试了传送的最小距离,截止日期快到了,所以我们希望尽可能彻底地检查它;所以我们需要找到两个尽可能远的实验室
  • 逃生/安全——后世界末日;只有一些地方(点)适合居住;人们可以住在其中一个上,因为他们需要彼此靠近以确保安全(他们很少);但是生活在某个地方会产生化学云(致命的),它会扩大到未知的大小;由于某种原因,它可能只发生一次;所以他们必须住在这样一个他们可以找到尽可能远的其他栖息地的地方
  • 遗传学- 我们希望找到两种尽可能不同的生物,以便对它们进行实验并获得更多种类的物种,或者只是为了检查哺乳动物的多样性

我知道这些“有点”牵强,但重要的用途是在破折号之前(测试、遗传学等)。除了传送器,可能还有其他东西,更有可能存在,但用法是一样的。找到两个可能有其他实际用途,因为可能有相似的生物,但我不得不问遗传学家。但是请随意为我的用法写更多实用的故事。

有一个更大尺寸的例子会很棒。

4

1 回答 1

0

最近对的应用。

以下算法和应用程序可以使用最近对数据结构有效地实现,或者将最近对计算作为重要的子程序。

  1. 动态最小生成树
  2. 组合优化中的二次优化启发式
  3. 直骨架和屋顶设计
  4. 射线相交图
  5. 其他碰撞检测应用
  6. 层次聚类
  7. 旅行推销员启发式
  8. 贪心匹配
  9. 建设性归纳
  10. Gröbner 基地

资源

至于你的想法:

  1. 测试 是的,这会起作用,但是可以很容易地找到一个更现实的例子,想想航空业的一些事情(例如)。
  2. 许多旅行我们可以把它写成“旅行距离”,是的,这也可以。
  3. 遗传学 I & II 例子也没有错,但又有点模糊。

最远对的应用。

关于你的想法,它们似乎并没有错,但正如你所说的有点牵强。


更大尺寸的示例。

好吧,我上面提到的应用程序可以去到更高的维度,例如凸包。另一个例子可以来自生物信息学领域,那里有许多分子,并且出于某种生物学原因,您想找到最接近的对。

于 2014-11-27T15:20:56.307 回答