使用C编程挑战: 机器臂移动方块堆栈。

Question

使用C编程挑战: 机器臂移动方块堆栈。

3

我在尝试解决这个有趣的问题，但在实现过程中遇到了一些麻烦，问题如下：

有n堆包含m个块的方块，设计一个用C语言编写的程序来控制机械臂，将块从初始配置移动到最终配置，使用尽可能少的动作次数，你的机械臂每次只能移动一个块，并且只能取栈顶上的块。你的解决方案应该使用指针或递归方法。

换句话说，这些方块应该从这里移动(假设有3个堆和3个块)：

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

转换为：

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

使用最短的步骤打印每一步。

我想也许我可以使用某种树来解决它（可能是n叉树？），因为这是指针和递归方法的完美运用，但到目前为止它已经被证明是不成功的，我在定义存储所有动作的结构时遇到了很多麻烦，因为我每次想要添加一个新动作到树中时都必须检查是否之前已经执行过此动作，我希望每个叶子都是唯一的，这样当我找到解决方案时它将给我最短的路径。

这是我考虑的数据结构：

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

我对C语言还很陌生，如果下面的内容有错误，请提前谅解，因为我更熟悉Java。

你们会如何做？有什么好的想法吗？

- Jimmy López Portillo

除非我错了，否则这听起来像汉诺塔。 - Burhan Khalid

@BurhanKhalid，不是很准确，因为块的堆叠没有任何限制。 - Carl Norum

3

好的观点——所期望的结果 1 > 2 > 3——就像汉诺塔问题一样。对于发帖者来说，看看C语言中的汉诺塔解法会很有益。 - Burhan Khalid

@BurhanKhalid 确实，堆叠没有任何限制，它可以以任何配置开始和结束，我考虑递归是因为这是解决ToH问题的方法。 - Jimmy López Portillo

在任何中间时间，是否有一个约束条件，即堆栈永远不会比m更高？ - stark

并不是这样，尽管堆栈数量较少、块数量较多时问题可能是无解的。 - Jimmy López Portillo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Austin · Accepted Answer

你已经有了基本的想法 - 尽管我不确定为什么你选择兄弟而不是父母。

你可以用简单的BFS搜索解决这个问题，但这是一个稍微不那么有趣的解决方案，并且似乎不是你设定的解决方案。

我认为，如果我们把我们解决问题的方法简明清晰地陈述为Dijkstra、A*或其他搜索算法的公式，这会有所帮助。

如果你不熟悉Dijkstra算法，在进一步尝试之前，有必要阅读有关该算法的资料。这是最短路径探索中的基础性工作之一。

在熟悉Dijkstra算法的情况下，A*可以被描述为

Dijsktra的最小化起点距离。A*添加了一个启发式，最小化（预期的）终点距离。

有了这个算法，让我们说明A*搜索算法的具体输入。

给定一个起始配置 S-start 和一个结束配置 S-end，在给定一组由奖励函数 T 管理的规则 R 的情况下，我们能否找到从 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-begin追溯父节点来找到最短路径。

如果你对这些类型的问题感兴趣，可以考虑参加高年级的人工智能课程，他们会涉及这些类型的问题。 :-)