如何比较以下两个对象？

Question

我正在尝试使用 DFS/BFS 算法解决 9 块拼图（让我们关注 DFS，因为这两者基本相同）算法，经过一些调试后我得出结论，为什么我的代码没有没用。

我正在使用边界堆栈和闭集集合来实现算法，有时我必须检查闭集中是否存在对象。所以我很自然地使用（temp 是一个 9-tile 对象）：

if (closed.find(temp) == closed.end()){ 
\do stuff
}

当我试图得出这个表达式时，我了解到我必须重载“<”和“>”运算符，以便 set.find() 可以工作。所以达到我的问题，9-tile 对象基本上是一个 2d 3x3 整数数组，空图块所在的值 0。例如，我如何确定板的以下状态之一是 "greater" 还是 "smaller"？

6 7 1   3 6 0
0 3 2   2 8 4
4 5 6   5 1 7

我尝试将每个元素与最终状态进行比较，即：

1 2 3
4 5 6
7 8 0

每张与决赛相同的牌加一分，但行不通，显然是因为两张牌完全错误放置的棋盘得分相同，所以我无法比较它们。

我也试过遍历两个板的元素，并像这样作曲谱：

bool operator < (const Board &A, const Board &B){
    int scoreA=0, scoreB=0;

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            scoreA += i * j * A.getTile(i, j);
            scoreB += i * j * B.getTile(i, j);
        }
    }
    return scoreA < scoreB;
}

但是我不确定这是正确的，因为我没有得到我想要的结果。

你能提出一个更好的方法来比较这样的两个板吗？

Answer 1

您可以尝试从棋盘上生成一个整数，例如

1 2 3 4 5 6 = 123456780 7 8 0

或者您想要更多的任何模式。

这样，您不必比较板，只需比较整数表示。

Answer 2

因为你比较的变量是分数，我假设你想做比较来检查哪个板更接近瓷砖移动问题的解决方案。

在这种情况下，您必须定义一些函数 double calculateScore(const Board& board) 然后进行比较：

double calculateScore(const Board& board)
{
  double score = 0.0;
  // as you wrote: adding one point for each tile that is the same as in the final 
  return score;
}

bool operator<(const Board& lhs, const Board& rhs)
{
  return calculateScore(lhs) < calculateScore(rhs);
}

然后您的目标是拿下使该分数最大化的棋盘。

Answer 3

由于您使用的是 BFS/DFS，因此 'greater' 或 'less' 元素并不重要。您只需要顺序保持一致（如果 a < b 和 b < c，则 a < c），只要两个板不同，您需要一个小于另一个。

瓷砖的排版比较就足够了。像这样：

bool operator < (const Board &A, const Board &B){

    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            int aTile = A.getTile(i,j);
            int bTile = B.getTile(i,j);
            if (aTile != bTile) {
                return (aTile<bTile);
            }
        }
    }
    return false; //equal
}

请注意，这会工作得很好，但使用 unordered_set 会更快。

此外，由于您将创建如此多的图板，因此最好使用较小的表示形式。如果按照另一位发帖者的建议将它们打包成 int，那么您可以将它们与标准 < 进行比较。如果将它们打包成字节数组，则可以使用memcmp.

如何比较以下两个对象？

How can I comapre two of the following objects?

c++

operators

set

data-structures