需要帮助找到启发式序列的逻辑

Question

我正在开发一个系统，可以完全探索这种性别的简单启发式地图（可以有不同数量的分支和不同深度）：

因此，我将探索的位置保存在地图深度大小的 int 数组中。目标是探索地图的所有节点，所以得到这个输出：0 2 6, 0 2 7, 0 3 8, 0 3 9, 1 4 10 etc.. 但实际上我的代码（需要调用多次，因为它只能更新数组一次），我有这个： 0 2 6, 0 2 7, 0 3 8, **1** 3 9, 1 4 10 etc..

这是我的代码，我不知道如何解决这个问题..

void get_next_branch(int *s, int nbr_branch, int size)
{
    int a;

    a = 0;

    while (a < size)
    {
        condition = (size - a)/(nbr_branch - 1);
        if (condition)
        {
            if (s[size - 1] % (condition) + 1 == condition)
                s[a]++;
        }
        a++;
    }
}

这是调用这个函数的主要例子

int main(void)
{
    int id[3] = {0, 2, 6};

    while (id[2] < 13)
    {
        printf("%d %d %d\n", id[0], id[1], id[2]);
        get_next_branch(id, 2, 3);
    }

    return (0);
}

先谢谢你了！

Answer 1

你可能想对这个问题使用闭合公式

b为分支数
d 你想要在 (d >= 0)

我们马上得到

Number of nodes at depth d = b^d+1

（因为在深度 0 处我们已经有两个节点，所以没有使用“根”节点）。

深度d第一个节点的个数是下层节点个数的总和。基本上，

first node number at depth 0 = 0

first node number at depth d > 0 = b¹ + b² + b³ + ... + b^d

这是比值为b的几何级数之和。感谢公式(Wolfram)

first node number at depth d = b * (1 - b^d) / (1 - b)

例如b == 2 和 d == 2（3^rd 级别）

Number of nodes: 2 ^ 3 = 8

Starting at number: 2 * (1 - 2^2) / (1 - 2) = 6

可以根据上面的公式来显示任何级别的树的程序。

要打印具有 b 个分支的树的多个级别：

效用函数

int power(int n, int e) {
   if (e < 1) return 1;
   int p=n;
   while (--e) p *= n;
   return p;
}

以上两个公式

int nodes_at_depth(int branches, int depth) {
   return power(branches, depth+1);
}

int first_at_depth(int branches, int depth) {
    return (branches * (1 - power(branches, depth))) / (1 - branches);
}

示例主程序，待调用

./heuristic  nb_of_branches  nb_of_levels

即调用两个函数

int main(int argc, char **argv)
{
   if (argc != 3) return 1;

   int b = atoi(*++argv);
   int d = atoi(*++argv);

   if (b < 2) return 2;

   int i,j;
   for (i=0 ; i<d ; i++) {
      int n = nodes_at_depth(b, i);  // number of nodes at level i
      int s = first_at_depth(b, i);  // first number at that level
      for (j=0 ; j<n ; j++) printf(" %d", s+j);
      printf("\n");
   }

   return 0;
}

通话中

./heuristic 2 4

给予

 0 1
 2 3 4 5
 6 7 8 9 10 11 12 13
 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

需要帮助找到启发式序列的逻辑

Need help for find the logic of a heuristic sequence

c

math

heuristics

sequence

brute-force