我试图解决这个问题是为了好玩，但我在实现时遇到了一些麻烦，问题是这样的:
有 n 堆积木，每堆积木包含 m 个积木，用 c 语言设计一个程序，控制机械臂移动积木，使用尽可能少的移动量从初始配置到最终配置，您的 ARM 只能一次移动一个 block 并且只能取栈顶的 block ，你的解决方案应该使用指针或递归方法
换句话说， block 应该从这里开始(假设有 3 个堆栈和 3 个 block ):
| || || |
|3|| || |
|2||1|| |
为此:
| ||1|| |
| ||2|| |
| ||3|| |
使用最短的移动量打印每一步
我在想也许我可以使用某种树来解决它(也许是 n 叉树？)，因为这是对指针和递归方法的完美使用，但到目前为止它被证明是不成功的，我有定义将存储所有 Action 的 estructure 有很多麻烦，因为我每次想向树添加一个新 Action 时都必须检查，如果以前没有做过该 Action ，我希望每片叶子都是独一无二的，所以当我发现它将给我最短路径的解决方案。
这是我想到的数据结构:
typedef struct tree(
char[MAX_BLOCK][MAX_COL] value;
struct tree *kids
struct tree *brothers;
)Tree;
(我真的是 C 的新手，如果这一切都是错误的，请事先道歉，我更习惯 Java)
你们会怎么做呢？你有什么好的想法吗？
最佳答案
你有基本的想法 - 虽然我不确定你为什么选择选择兄弟而不是 parent 。
您可以通过简单的 BFS 搜索来解决这个问题，但这是一个稍微不那么有趣的解决方案，而不是您似乎已经为自己设定的解决方案。
我认为，如果我们以 Dijkstra's 中任一公式的形式简明扼要地说明我们解决问题的方法，将会有所帮助。 、A* 或其他一些搜索算法。
如果您不熟悉 Dijkstra 的算法，则必须在进一步尝试之前阅读该算法。它是最短路径探索的基础性工作之一。
在熟悉 Dijkstra 的情况下，A* 可以很容易地描述为
Dijsktra's minimizes distance from the start. A* adds a heuristic which minimizes the (expected) distance to the end.
考虑到这个算法，让我们说明 A* 搜索算法的特定输入。
Given a start configuration S-start, and an ending configuration S-end, can we find the shortest path from S-start to S-end given a set of rules R governed by a reward function T
现在，我们可以将我们的数据结构想象成一张图，而不是一棵树。节点将是棋盘状态，我们可以使用我们的规则 R 从一个状态转换到另一个状态。我们将使用奖励函数 T(A* 的启发式)选择要遵循的边。
您的数据结构中缺少的是成本。在每个节点，你会想要存储当前的最短路径，以及它是否最终确定。
让我们对您的数据结构进行修改，这将使我们能够轻松地遍历图形并存储最短路径信息。
typedef struct node {
char** boardState;
struct node *children;
struct node *parent;
int distance;
char status; //pseudo boolean
} node;
You may want to stop here if you were interested in discovering the algorithm for yourself.
我们现在考虑我们系统的规则:一次一个 block ，从堆栈的顶部开始。每一步都将构成我们图中的一条边，其权重由从 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 向后跟踪父节点来找到最短路径。
如果您对这些类型的问题感兴趣，您应该考虑参加本科阶段的 AI 类(class)，他们会在这些类(class)中处理这些类型的问题:-)
关于c - "Robot Arm moving block stacks"C 编程挑战，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12995328/