python - 在图中追逐(有点)未知点的算法

Question

我正在开发一个模拟器，供应商可以在其中创建由消费者购买的报价。

• 提供商将报价放在价格(y 轴)x 质量(x 轴)平面上。
• 消费者只会购买价格低于他们偏好但质量更高的商品
• 消费者购买具有最大欧氏距离的商品。
• 消费者只能购买一种优惠。
• 提供者不知道消费者的确切位置。它确实知道消费者所在的区域，并且确实知道与消费者的距离。

我需要为供应商实现一种算法来更新他们的报价并提高其效用。

为了说明这个问题，这里有一个例子:

 P ^         .
   |         .
   |   C     .
   |     \   .
   |      \  .
   |       \ .
   |........ P
   |
   |
   |
   +---------------------> Q

提供者 (P) 知道它把报价放在哪里，所以它知道消费者 (C) 必须在虚线区域内。

我想出了几个算法来接近消费者。

1. 提供商提高价格并降低质量一个单位(向点 (1, 0) 移动)。这种方法的问题是，当消费者位于虚线区域的其中一个轴上时，供应商很快就会失去销售，因为其报价将不再满足消费者。

2. 在点 (1, 0) 的方向上向消费者移动一半的距离。这可以更快地到达消费者，但会遇到与之前相同的问题(当消费者沿着虚线区域轴时)。

还有其他我不知道的算法吗？是否有用于此的 Python 模块？ (:) 现在几乎所有东西都有模块)

Answer 1

在您的第一个猜测 (x0,y0)(P 在您的模式中)和给定的 d(对于给定的从 C 到 P 的欧氏距离)。Offer(xc,yc)位于圆心(x0,y0)和半径d的圆上。

  +
  |
  |          XXXXXX
  |        XXX
  |      XC
  |     X
  |    X
  |   X
  |   X            P0
  |
  |
+-+---------------------------------+

如果您选择 (x0, y0+e) e 您“可以”选择的最小值，则 (xc,yc) 也位于中心 (x0, y0+e) 和半径 d2 的圆上所以 C 位于两个圆的交点上

  +
  |              XXX
  |           XXXXXX
  |        XXXX
  |      XXCX
  |     X X
  |    X X         P1
  |   X
  |   X            P0
  |
  |
+-+---------------------------------+

然后你可以解决这个系统:

sqrt((xc-x0)^2 + (yc-y0)^2) = d^2
sqrt((xc-x1)^2 + (yc-y1)^2) = d2^2

在这里你会得到 x1==x0

d^2 - (yc-y0)^2 = d2^2 - (yc-y1)^2

这很容易解决(变量是yc)

然后你选择yc使得y_0<y_c并返回 xc 使得 0<x_c< x_0 .

问题简化为:您只需要在第二次猜测时获得“幸运”，以便边界框仍然是地球 C。

如果您在 x 轴上移动 eps，则使 C 无效的几率是多少，y 轴也是如此。取决于您的供应商是否倾向于在质量或价格上给自己一些 margin ...