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）

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

4

1 回答 1

3

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

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

我认为，如果我们简明扼要地将我们解决问题的方法表述为Dijkstra's、 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 向后跟踪父项来找到最短路径。

如果您对这些类型的问题感兴趣，您应该考虑参加研究生级别的 AI 课程，他们会在其中解决这些类型的问题 :-)

于 2012-10-31T19:00:33.700 回答