C语言中的“机器人手臂移动块堆栈”编程挑战

Question

我试图解决这个问题是为了好玩，但我在实现上遇到了一些麻烦，问题是：

有n组包含m块的块，在c++中设计一个程序，用最小的移动量控制移动块的机械臂形成非官方的配置，您的手臂一次只能移动一个块，只能在堆栈的顶部取块，您的解决方案应该使用指针或递归方法。

换句话说，这些块应该从这里开始(假设有3个堆栈和3个块)：

| || || |
|3|| || |
|2||1|| |

对此：

| ||1|| |
| ||2|| |
| ||3|| |

使用最短的移动量打印每次移动

我在想，也许我可以用一棵树来解决这个问题(也许是一棵树？)因为这是指针和递归方法的完美使用，但到目前为止，它被证明是不成功的，我很难定义能存储所有运动的estructure，因为每次我想要在树上添加一个新的移动(如果之前没有这样做)，我希望每一片叶子都是唯一的，所以当我找到解决方案时，它会给我最短的路径。

这就是我在想的数据结构：

typedef struct tree(
char[MAX_BLOCK][MAX_COL] value;    
struct tree *kids
struct tree *brothers;
)Tree;

(我在C上是个新手，很抱歉，如果这一切都错了，我更习惯Java了)

你们会怎么做？你有什么好主意吗？

Answer 1

你有基本的想法--尽管我不知道你为什么选择选择兄弟而不是父母。

您可以通过简单的BFS搜索来解决这个问题，但这是一个稍微不那么有趣的解决方案，而不是您似乎已经为自己设置的解决方案。

我认为，如果我们简明扼要地说明我们对这个问题的处理方法是迪克斯特拉氏，A*或其他搜索算法的公式，那将是有帮助的。

如果您不熟悉Dijkstra的算法，那么在进一步尝试之前，您必须阅读该算法。它是最短路径探索的基础性工作之一。

由于对Dijkstra的熟悉，A*可以很容易地描述为

Dijsktra从一开始就最小化了距离。A*增加一个启发式，使(预期的)距离最小化到终点。

考虑到这个算法，让我们声明A*搜索算法的具体输入。

给定一个启动配置S-start和一个结束配置S-end，我们能找到从S-start到S-end的最短路径吗？

现在，我们可以想象我们的数据结构不是一棵树，而是一个图表。节点将是板状态，我们可以使用我们的规则从状态转换到状态，R.我们将使用奖励函数T (启发式到A* )选择要遵循的边。

数据结构中缺少的是成本。在每个节点上，您将希望存储当前最短路径，以及该路径是否已完成。

让我们修改一下您的数据结构，这样我们就可以轻松地遍历图并存储最短路径信息。

typedef struct node {
  char** boardState;
  struct node *children;
  struct node *parent;
  int distance;
  char status; //pseudo boolean
} node;

如果你对自己发现算法感兴趣，你可能想在这里停下来。

我们现在考虑我们系统的规则:每次从堆栈顶部的一个块。每一次移动将构成我们的图中的一个边，它的权重取决于从S-begin到我们添加的启发式的最短移动数。

然后，我们可以给出算法的草图如下：

node * curr = S-begin;
while (curr != S-end) {
  curr->status == 'T'; //T for True
  for(Node child : children) {
     // Only do this update if it is cheaper than the 
     int updated = setMin(child->distance, curr->distance + 1 + heuristic(child->board));
     if(updated == 1) child->parent = curr;  
  } 
  //set curr to the node with global minimum distance who has not been explored
}

然后，通过将父母从S-end追溯到S-S，您可以找到最短的路径。

如果你对这些类型的问题感兴趣，你应该考虑参加一门高级人工智能课程，在那里他们会处理这些类型的问题:-)