我将在matlab中使用此特定字符生成10^6个随机点。这些点应该位于半径为25的球体内，是三维的，因此我们有x，y，z或r，theta，phi。每个点之间有一个最小距离。首先，我决定生成点，然后检查距离，然后忽略不具备这些条件的点。但是，它可能会省略很多点。另一种方法是使用RSA（随机序贯加法），表示以最小距离逐个生成点。例如生成第一个点，然后从点1的最小距离中随机生成第二个。继续下去，直到达到10^6分。但这需要很多时间，我无法达到10^6分6分，因为搜索新点的适当位置的速度将花费很长时间。
我现在正在使用这个程序：
Nmax=10000;
R=25;
P=rand(1,3);
k=1;
while k<Nmax
theta=2*pi*rand(1);
phi=pi*rand(1);
r = R*sqrt(rand(1));
% convert to cartesian
x=r.*sin(theta).*cos(phi);
y=r.*sin(theta).*sin(phi);
z=r.*cos(theta);
P1=[x y z];
r=sqrt((x-0)^2+(y-0)^2+(z-0)^2);
D = pdist2(P1,P,'euclidean');
% euclidean distance
if D>0.146*r^(2/3)
P=[P;P1];
k=k+1;
end
i=i+1;
end
x=P(:,1);y=P(:,2);z=P(:,3); plot3(x,y,z,'.');字符串
我如何能有效地生成点，通过这些条件？
3条答案
按热度按时间h9a6wy2h1#
我仔细看了一下你的算法，得出的结论是它永远不会工作-至少如果你真的想在那个球体上得到一百万个点的话。有一个简单的图片可以解释为什么不-这是你需要测试的点的数量图（使用你的RSA技术）得到一个额外的“好”点。正如你所看到的，这在几千个点上是渐进的（我对20万个点运行了一个稍微快一点的算法来产生这个）：
x1c 0d1x的数据
我不知道你是否曾经试图计算理论上的点的数量，当你把它们完美地排列在你的球体上时，但我开始怀疑这个数字比1 E6小得多。
我用来研究这个问题的完整代码，加上它生成的输出，可以在here中找到。我从来没有达到我在前面的回答中描述的技术......在你描述的设置中还有太多其他的东西。
编辑：我开始想，即使有“完美”的安排，也不可能达到100万点。我为自己做了一个简单的模型，如下所示：
假设你从“ shell ”（r=25）开始，试着拟合等距点，如果你用“ shell ”的面积除以一个“排除盘”（半径为r_sub_crit）的面积，你会得到该距离上的点的数量的（高）估计：
字符串
下一个“shell”的半径应该小于0.146*r^（2/3）-但是如果你认为这些点是非常仔细排列的，你可能会得到一点接近。同样，让我们慷慨地说，这些shell可以比标准接近1/sqrt（3）。然后你可以从外部shell开始，使用一个简单的python脚本来工作：
型
其输出为：
型
这似乎证实了你真的无法达到一百万，无论你如何尝试。
5ktev3wc2#
你可以做很多事情来改进你的程序--算法和代码。
在代码方面，真正使您的速度变慢的一个原因是，您不仅使用了
for循环（这很慢），而且在行字符串
您将元素添加到数组中。每次发生这种情况时，Matlab都需要找到一个新的位置来放置数据，并在此过程中复制所有的点。这很快就会变得非常慢。
型
记录到目前为止已找到的点数N，并将距离计算改为
型
至少能解决这个问题。
另一个问题是，您需要对照以前找到的所有点来检查新点，因此，当您有100个点时，您需要检查大约100 x100个点，对于1000，它是1000 x1000。您可以看到，此算法至少是O（N^3）......不考虑随着密度的增加，您将获得更多“未命中”的事实。10 E6至少需要10 E18个周期;如果你有一台4GHz的机器，每次比较一个时钟周期，你需要2.5E9秒=大约80年。你可以尝试并行处理，但那只是蛮力--谁愿意呢？
我建议您考虑将问题分解为更小的部分（字面意思）：举例来说，如果你把球体分成大小与你的最大距离相当的小方块，并记录每个方块中的点，那么你只需要检查“这个”方块中的点及其紧邻的点--总共27个方块。2如果你的方块有2.5毫米宽，您将有100 x100 x100 = 1 M个盒子。这看起来很多，但现在您的计算时间将大幅减少，因为（在算法结束时）每个盒子平均只有1个点......当然，根据您使用的距离标准，您将在中心附近有更多的点，但这只是一个细节。
您需要的数据结构是一个100 x100 x100的单元数组，每个单元包含“在该单元中”迄今为止找到的好点的索引。单元数组的问题在于它不适合矢量化。如果您有足够的内存，则可以将其指定为一个10 x100 x100 x100的4D数组。假设每个像元中的点不超过10个（如果超过10个，则必须单独处理;在此与我一起工作...）。对于尚未找到的点，使用
-1索引那么你的支票应该是这样的：
型
。
型
我不知道你能不能从这里开始，如果你不能，在笔记里说，我可能会在这个周末有时间来更详细地编码。有一些方法可以通过一些矢量化来加快速度，但是很快就变得很难管理了。
我认为在空间中随机放置大量的点，然后使用上面的方法进行巨大的矢量化剔除，可能是一种可行的方法。但我建议先采取一些小步骤......如果你能让上面的方法很好地工作，那么你可以进一步优化（数组大小等）。
xdnvmnnf3#
我发现the reference -“Simulated Brain Tumor Growth Dynamics Using a Three-Dimensional Cellular Automaton”，Ansal et al（2000）.
我同意这是令人费解的-直到你意识到一个重要的事情。他们报告他们的结果在
mm，但你的代码是写在cm。虽然这似乎无关紧要，公式“临界半径”，rc = 0.146r^(2/3)包括一个常数，0.146，这是维数-维数是mm^(1/3)，而不是cm^(1/3)。当我在我的python代码中进行修改以评估可能的晶格点的数量时，它跳了10倍。现在他们声称他们使用了0.38的“干扰限制”-你真的找不到更多的点。如果你包括这个限制，我预测不会超过20万个点-仍然低于他们的1.5M，但不那么疯狂。