2

我的家庭作业（C++）有问题。我不是要求完整的解决方案，但朝正确的方向倾斜可能会有所帮助。:)

我有一个 NxN 板（最大 N = 100）和那个板上的 1x2 图形（立方体）。立方体的一侧涂成红色，另一侧涂成蓝色。立方体的默认位置是棋盘的左上角，蓝色面朝上：

B B . .
. . . .
. . . .
. . . .

（4x4 示例，B 代表蓝色）

黑板上可能有石头（障碍物）。 我可以用我的身材做的动作：

  • 顺时针旋转 90/180/270 度
  • 你可以围绕它的右/左/上/下边缘翻转立方体，改变它的“向上颜色”

例如，在默认位置使用向右翻转：

. . R R
. . . .
. . . .
. . . .

然后使用旋转 90：

. . R .
. . R .
. . . .
. . . .

然后使用左翻转：

. B . .
. B . .
. . . .
. . . .

当然，在旋转或翻转时，你不能落在石头上。所以，问题是——对于任何给定的棋盘配置（图形位置和石头位置）编写一个程序，使用最少的移动次数“将立方体带回家”在默认位置（蓝色面朝上！）如果可能，则返回 1，如果不可能，则返回 0。

我觉得这个问题很有趣，但我不得不承认我对此有点困惑。尤其是蓝边/红边部分。我真的不知道如何“翻译”那些我可以用通常的最短路径算法的语言使用的动作（我从来没有使用过这些）。因此，我将不胜感激您提供的每一条建议！:)

4

3 回答 3

1

首先，由于要求您找到确切的最佳路径，我会选择Dijksta's algorithm。

对于此算法，您需要：

  1. 给出下一个可能移动的函数。
  2. 一个告诉你一个位置是否已经被访问过的函数。
  3. 一个函数，它告诉你每条路径的总成本。
  4. 当然还有一个功能可以告诉您何时到达最终位置

给定一个初始位置，您的立方体可以恰好到达 7 个新位置。很容易选择哪些是可能的。

G 只是您到目前为止所做的移动次数+ 1 的下一步移动 :)

我会使用哈希表来跟踪访问的位置。（这可能是最难写的函数），但你现在不需要想太多。一个简单的向量和逐项比较就可以了。您可以在代码运行后对其进行优化。

最后，您需要检查立方体是否处于蓝色面朝上的初始位置。

于 2012-05-27T23:26:15.773 回答
1

您可以将每个可能的 1x2 块和颜色（红色或蓝色）组合解释为顶点并作为边移动。如果有可能在一次移动中从其他组合到达特定的 1x2 块和颜色组合（顶点），那么这两种组合之间存在连接（边缘）。然后，您必须在结果图中找到给定配置和“家庭”配置之间的最短路径（可能是广度优先搜索，因为无论您执行什么移动，移动成本都是相同的）。

如果想更进一步，您可以使用在图遍历期间使用启发式的高级图搜索算法（启发式是假设黑板上没有障碍物到达目的地所需的最小移动量）。例如，您可以使用A* 算法。

于 2012-05-27T23:41:32.260 回答
0

在处理这类问题时，首先要做的是找到问题状态的表示。在这种情况下，您需要：

  1. 代表图形左上角位置的两个整数
  2. 一个布尔值，代表图形的颜色（红/蓝）
  3. 一个布尔值，表示图形的方向（水平/垂直）

如果您熟悉位掩码，则应仅使用 32 位整数来执行此操作（x 位置为 8 位，y 位置为 8 位，其余为 2 位）。这样您就不需要实现比较运算符。 或者 您使用这 3 个信息定义一个简单的结构（调用它state）并对此进行严格排序比较（这只需要state放入std::set.

在此之后，您可以使用BFS解决此问题。

为此，您需要：

  1. 将std::map<state,state>您已经访问过的位置存储在键中，并将您来自的位置存储在值中（如果您可以使用 c++11 并且使用位掩码来存储您的状态，请替换map为）unordered_map
  2. Astd::queue<state>在其中推送和弹出要处理的状态。
  3. 一些代码来确定从给定状态可达到的每个可能状态（即实现所有可能的移动，注意棋盘尺寸）

伪代码：

   map<state,state>  visited;
   queue<state> to_be_processed;

   visited.insert( initial_state,initial_state); //you are not coming from anywhere
   to_be_processed.push ( initial_state);
   
   while(!to_be_processed.empty()) {

              state cur = to_be_processed.pop();
              if ( cur == end_state) //you are done
              {
                    //to get the path from initial_state to end_state you have just to walk visited in the inverse order.
                    return 1;
              }
              for ( i = every possible state reachable from cur) {
                    if (visited.count(i) != 0) continue; //already visited
                    to_be_processed.push(i);
                    visited.insert(i,cur); //i has been visited, and you reached i from cur
              }

   }
   return 0; //if you get here, no way

障碍的存在使问题更难编码，但在概念上并没有什么不同。

请注意，在这种情况下，BFS 有效，因为您从一个状态到另一个状态所支付的成本始终相同。

于 2012-05-28T02:02:50.007 回答