0

我有一个包含n元素的序列，我想在其中随机放置k“断点”，每个至少minDist彼此远离（和末端）。例如，对于n=9, k=2, minDist=2，我想以相等的概率生成以下之一：

[2 4][2 5][2 6][2 7][3 5][3 6][3 7][4 6][4 7][5 7]

到目前为止，我想出了：随机放置一个，“禁用”它周围所需数量的节点，然后选择另一个随机数，但这让我觉得效率有点低。我在 MATLAB 中编程，但任何语言都可以。

我将使用它来初始化一些遗传算法的种群，所以我希望每种可能性都具有相同的可能性，以确保我覆盖了整个搜索空间。仅仅确定性地分布断点是不够的。

4

4 回答 4

1

如果您不介意随机（但很小）的计算时间，您可以使用拒绝方法：

  1. 随机生成分布均匀的暂定断点；
  2. 检查它们是否满足您的限制；
  3. 如果他们不这样做，请重复。

这确保了每个有效的断点组合的概率相等，而不必最初生成所有这些组合。

在 Matlab 中：

done = 0;
while ~done
  breakPoints = sort(randi(n,1,k));
  done = all(diff([0 breakPoints n]) >= minDist);
end
于 2013-10-07T12:51:10.430 回答
1

这是一个生成所有可能的断点组合的函数，你可以将它们存储在一个列表中而不是打印它们，然后统一选择其中一个：

static void breakpointCombinations(List<int> possiblePositions, List<int> breakpointCombination, int remainingBreakpoints, int minSpace, int currentPos)
{
    if (remainingBreakpoints == 0)
    {
        foreach (int tempPos in breakpointCombination)
        {
            Console.Write(tempPos + " ");
        }
        Console.WriteLine();
    }

    else if (remainingBreakpoints * minSpace > possiblePositions.Count - currentPos)
        return;

    else
    {
        if (currentPos >= minSpace - 1)
        {
            breakpointCombination.Add(possiblePositions[currentPos]);
            breakpointCombinations(possiblePositions, breakpointCombination, remainingBreakpoints - 1, minSpace, currentPos + minSpace);
            breakpointCombination.Remove(possiblePositions[currentPos]);
        }

        breakpointCombinations(possiblePositions, breakpointCombination, remainingBreakpoints, minSpace, currentPos + 1);
    }
}

对函数的调用（在此示例中，10 个元素，2 个断点，最小空间为 2）：

static void Main(string[] args)
{
    List<int> Positions = new List<int>();
    for (int i = 0; i < 10; i++)
    {
        Positions.Add(i);
    }

    breakpointCombinations(Positions, new List<int>(), 2, 2, 0);
}

从您的示例中暗示，空格 2 意味着在 2 个断点之间应该至少有一个位置（例如，这意味着 [2, 4] 是合法的），我从头到尾处理相同的空格（这在示例中不一致），这意味着如果元素是 [0, ... ,9]，则第一个合法断点位于元素 1，最后一个合法断点位于元素 8。

于 2013-10-07T11:22:46.600 回答
0

根据您的规范，您可以从左侧开始，并k-1在每个minDist元素之后放置断点时间。

如果您希望您的部门分布更均匀，则必须修改您的规范。

于 2013-10-06T21:58:17.270 回答
0

实际上，如果你想覆盖整个搜索空间，你不应该选择随机点。

相反，您应该选择所有点，也许以随机顺序。

这是一种选择所有点的简单方法k = 2：

n=9;
minDist = 2;
p = [];
for x = minDist:n-minDist*2
   for y = x+minDist:n-minDist
     p = [p;x y]
   end
end

对于较低的 k 值，您可以简单地添加嵌套循环。

一旦你有了所有的点，随机挑选它们应该是微不足道的。

于 2013-10-07T11:32:45.133 回答