检查交集的数学技术
想象一下有一个非常非常大的房间，形状为空心立方体。在房间的固定离散位置上，空中悬挂着魔法球。没有一个魔法球的正上方有另一个魔法球。如果我们取一个面积无限大的假想水平面并穿过立方体，我们如何确定该平面不会穿过任何魔球？
魔球的高度是其位置（x 和 y）的函数。分布是这样的：一些球处于相同高度，而另一些球则处于不同高度。 设函数为z = axy + bx + cy
其中 a、b、c 是正整数常数。 位置（x 轴和 y 轴值）以及高度 (z) 都是离散值（为简单起见，我们可以将它们视为正整数）。
如果球分布函数为 z=10xy+8x+4y，则 z 值不可能为 15 或 21。因此 z=15 或 z=21 的平面不会切割任何球！事实上，在这种情况下，任何具有一定高度（z = 任何奇数）的平面都不会穿过球。值得注意的是，有一些高度为偶数的平面没有穿过球。
我们不想找到所有魔球的高度并将其与水平面的高度进行比较，因为这样这就像尝试所有可能的组合，即使在计算机上也需要很长时间。
我们的目标是找到一种快速方法，通过该方法我们可以判断给定的 z（高度）值是否可以由任意一对 (x,y)（位置）产生。如果无法产生给定的 z，则那个高度的飞机不会切穿任何球！ 该问题也类似于查找给定数字是否存在于由两个变量的函数产生的序列中。
如果你能给我任何解决这个问题的建议，那将会有很大的帮助。谢谢。 （我已经尝试过进化计算，如 GA、PSO、DE、SA 等。该方法需要是确定性的）。
Imagine there is a very very large room in the shape of a hollow cube. There are magic balls hanging in the air at fixed discrete positions of the room. No magic ball has another one exactly above it. If we take an imaginary horizontal plane of infinite area and pass through the cube, how can we be sure that the plane doesn't cut through any of the magic balls ?
The height of a magic ball is given as a function of its position (x and y). The distribution is such a way that some balls are at the same height while other are at different heights.
Let the function bez = axy + bx + cy
where a,b,c are positive integer constants.
The positions (x-axis and y-axis values) and also the height (z) are discrete values (for simplicity, we can consider them positive integers).
If the ball distribution function was z=10xy+8x+4y, then it is impossible to have a z value of 15 or 21. So a plane at z=15 or z=21 would not cut any of the balls! In fact, in this case, any plane with a height (z = any odd number) would not cut through the balls. It is noticeable that there a some planes with height as even numbers that donot cut through the balls.
We do not want to find the heights of all the magic balls and compare it with the height of the horizontal plane, as that would be like trying all the possible combinations and would take very long time even on a computer.
Our aim is to find a fast method by which we can tell whether a given value of z (height) can be produced by any pair of (x,y) (positions).If a given z cannot be produced, then a plane at that height doesn't cut through any balls!
The question is also similar to finding whether a given number is present in a sequence produced by a function of two variables.
It would a great help if U could give me any suggestions to solve this problem. Thank You.
(I have already tried evolutionary computing like GA,PSO,DE,SA etc. The method needs to be deterministic).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
听起来你房间里有很多球。房间高度从 z=A 到 z=B。您感兴趣的是是否有高度 z 的物体。要做到这一点，而不必迭代所有球，您需要首先假设范围 A 到 B 为空，然后迭代球，将该范围的部分标记为已满，直到完全满或没有球。在前一种情况下，没有任何平面可以满足要求，但您还没有遍历所有球来了解这一点。在后一种情况下，您的 z 范围内没有球，您可以使用这些范围轻松检查多个平面，但初始成本是遍历所有球。
It sounds like you have a lot of balls in the room. The room height is from z=A to z=B. What you're interested in is whether any are at height z. To do that without necessarily iterating through all the balls, you need to start by assuming that the range A to B is empty and iterate through the balls, marking parts of this range as full, until it is either full completely or there are no balls. In the former case, no plane will satisfy, but you haven't iterated through all the balls to know that. In the latter case, you have ranges of z in which there are no balls and you can use these to check more than one plane easily, however at the initial cost of iterating through all balls.