Как я могу объединить два из следующих объектов? - PullRequest
Новая
       13

Как я могу объединить два из следующих объектов?

0 голосов
/ 03 апреля 2019

Я пытаюсь решить головоломку из 9 плиток с помощью алгоритма DFS / BFS (давайте сосредоточимся на DFS, поскольку эти два в основном одинаковы), и после некоторой отладки я пришел к выводу, почему мой код не работает.

Я реализую алгоритм, используя стек для границы и набор для закрытого набора, и в какой-то момент я должен проверить, существует ли объект в закрытом наборе. Поэтому, естественно, я использую (temp является объектом из 9 плиток): 

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

Когда я пытался выпустить это выражение, я узнал, что мне пришлось перегрузить операторы '<' и '>, чтобы set.find () мог работать. Таким образом, достигнув моей проблемы, объекты из 9 плиток представляют собой массив целых чисел 2d 3x3 с значение 0, где пустая плитка. Как я могу определить, является ли, например, одно из следующих состояний моей доски "большим" или "меньшим", чем другое? 

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;
}

Однако я не уверен, что это правильно, поскольку я не получаю желаемых результатов.

Можете ли вы предложить лучший метод сравнения двух плат, как этот?

Ответы [ 3 ]

0 голосов
/ 03 апреля 2019

Поскольку ваши переменные, которые вы сравниваете, являются баллами, я предполагаю, что вы хотите провести сравнение, чтобы проверить, какая доска ближе к решению проблемы перемещения плиток.

В этом случае вам нужно определить некоторую функцию 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);
}

Ваша цель - взять доску с максимальным количеством очков.

0 голосов
/ 03 апреля 2019

Поскольку вы используете BFS / DFS, не имеет значения, какие элементы «больше» или «меньше».Вам просто нужно, чтобы порядок был последовательным (если a Лексографическое сравнениеплитки достаточно.Примерно так: 

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.

0 голосов
/ 03 апреля 2019

Вы можете попробовать сделать целое число на доске, например,

1 2 3 4 5 6 = 123456780 7 8 0

или любым другим шаблоном, который вам больше нравится.

Таким образом, вы надеваетене нужно сравнивать доски, только целочисленные представления.

...