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


Проблему я пытаюсь решить состоит в следующем:

У вас есть сетка 10x10 и начинаем с верхней левой точки, вы должны коснуться все точки, не проходя через точки, которые уже были затронуты, с ограниченным набором движений. По горизонтали вы можете перемещаться по трем точкам и по диагонали можно переходить на два пункта.

Испробовав безуспешно несколько раз рукой, я реализовал рекурсивного перебора алгоритм в C++, инкапсуляция в классе.

Vec2 это вспомогательный класс, я для того, чтобы сделать код чище и это просто целое число 2D векторной класс.

Основной функцией является bruteForce(), который ищет все возможные ходы с позиции и рекурсией, пока нет никаких возможных ходов не осталось, а рекурсией он хранит ходы он сделал в векторе.

Проблема решена, когда нет перемещается влево и размеров движения вектор составляет 99.

Ходы записываются по часовой стрелке, начиная с права вверх-вправо и регулировать с помощью следующих функций:

  • В isPossibleMove() возвращает true, если для данной позиции ход можно и false в противном случае
  • В getPossibleMoves() хранит все возможные ходы из данной позиция в векторе; он начинает поиск от последнего перехода(это значительно уменьшает время для поиска первого решения)
  • В getArrayIndex() используется для получения массива индексов от 2D координаты(массив строкам)

Board является вектор, содержащий 10х10 булевы решетки (1 Если точка была затронута, 0 в противном случае), уникальный для каждого шага рекурсии

Лучшее, что я мог сделать, чтобы сделать это быстрее, чтобы использовать OpenMP в первый шаг, создав в этом случае, 3 нити. На моей установке, она занимает около 20 мс, чтобы найти первое решение и около 1200 мс, чтобы найти первые 1000 решений.

Так, как это может быть быстрее?

Это выглядит так:

#include <vector>
#include <array>
#include "Point.h"

typedef Vec2 Point;

template<int gridSize>
class Solver
{
private:
    std::array<Vec2, 8> moves;
    bool solved;

    void initMoves()
    {
        moves[0] = Vec2(3, 0);
        moves[1] = Vec2(2, 2);
        moves[2] = Vec2(0, 3);
        moves[3] = Vec2(-2, 2);
        moves[4] = Vec2(-3, 0);
        moves[5] = Vec2(-2, -2);
        moves[6] = Vec2(0, -3);
        moves[7] = Vec2(2, -2);
    }

    bool isPossibleMove(const Point& p, int move, const std::vector<bool> &board) const
    {
        Point p1 = p;
        p1 += moves[move];

        return ((p1.getX() >= 0 && p1.getX() < gridSize && p1.getY() >= 0 && p1.getY() < gridSize) && !board[getArrayIndex(p1)]);
    }

    bool getPossibleMoves(const Point& p, const std::vector<bool> &board, int lastMove, std::vector<short>& possibleMoves) const //BECOMES BOOL
    {
        for (int i = lastMove; i < moves.size(); i++)
        {
            if (isPossibleMove(p, i, board))
            {
                possibleMoves.push_back(i);
            }
        }

        for (int i = 0; i < lastMove; i++)
        {
            if (isPossibleMove(p, i, board))
            {
                possibleMoves.push_back(i);
            }
        }

        return !possibleMoves.empty();
    }

    int getArrayIndex(const Vec2& vec) const
    {
        return vec.getX() + vec.getY() * gridSize;
    }

    bool verifySolution(const std::vector<short>& seq, const Vec2& start) const
    {
        Vec2 p = start;

        std::vector<bool> board(gridSize*gridSize, 0);

        board[getArrayIndex(p)] = 1;
        for (const auto &move : seq)
        {
            p += moves[move];
            board[getArrayIndex(p)] = 1;
        }

        for (const auto &i : board)
        {
            if (i == 0)
            {
                return false;
            }
        }

        return true;
    }

    void bruteForce(Point p, std::vector<short> seq, std::vector<bool> board)
    {
        if (!solved)
        {
            std::vector<short> possibleMoves;
            possibleMoves.reserve(8);

            board[getArrayIndex(p)] = 1;
            p += moves[seq.back()];

            while (getPossibleMoves(p, board, seq.back(), possibleMoves))
            {
                for (auto i = possibleMoves.begin(); i < possibleMoves.end() - 1; ++i)
                {
                    seq.push_back(*i);
                    bruteForce(p, seq, board);
                    seq.pop_back();
                }

                seq.push_back(possibleMoves.back());
                possibleMoves.resize(0);

                board[getArrayIndex(p)] = 1;
                p += moves[seq.back()];

            } 


            if (seq.size() == gridSize * gridSize - 1 && !solved)
            {
                std::cout << "SOLVED!!!!!\n";
                solved = true;
            }
        }
    }

public:
    Solver() : solved(false)
    {
        initMoves();
    }

    void start(Point p = Point(0, 0))
    {
        std::vector<bool> board(gridSize*gridSize, 0);
        board[getArrayIndex(p)] = 1;

        std::vector<short> possibleMoves;
        getPossibleMoves(p, board, 0, possibleMoves);

        for (const auto& i : possibleMoves)
        {
            bruteForce(p, std::vector<short>(1, i), board);
        }
    }

    void startOpenMP(Point p = Point(0, 0))
    {
        std::vector<bool> board(gridSize*gridSize, 0);
        board[getArrayIndex(p)] = 1;

        std::vector<short> possibleMoves;
        getPossibleMoves(p, board, 0, possibleMoves);

#pragma omp parallel for
        for (int i = 0; i < possibleMoves.size(); i++)
        {
            bruteForce(p, std::vector<short>(1, possibleMoves[i]), board);
        }
    }
};


Комментарии
2 ответа

Избавиться от векторов

Как правило, std::vector ваш друг в C++. Но это является динамически выделяемой структуры. Построение вектора и отодвигая поэтому дорого, и вы делаете это много.

Поскольку у вас есть только в четырех возможных ходов на каждом шагу, просто использовать фиксированный размер массива, чтобы сохранить их, и использовать любую другую переменную, чтобы хранить сколько ходов хранятся в массиве, или использовать предохранитель значение (например, -1), чтобы указать, что запись в массиве является недопустимым.

Во-вторых, нет необходимости использовать вектор seq для сохранения пути. Вместо этого, сделать board быть 10х10 массив shorts что магазин на следующий участок пути. Например, верхний левый элемент массива будет хранить координаты (1, 0), если путь идет вправо, или (0, 1) если она идет вниз. Опять же, имеет значение охранять, чтобы указать, что позиция еще не видел.

Очки против индексов

В настоящее время вы используете Point чтобы сохранить позиции. Однако, это не оптимально. Во-первых, это, вероятно, пары целых чисел, так что это займет до 64 бит на большинстве компьютеров сегодня, когда вам необходимо только несколько <= 100, чтобы сохранить положение на доске. Во-вторых, если реализация getX() и getY() не определен в заголовочном файле Point.h, а в Point.cтогда компилятор не сможет подставить его, и будет генерировать вызов функции. Это займет много времени по сравнению с просто доступ к переменной-члена непосредственно. В-третьих, вам придется конвертировать между точками координат и позиции в массиве. В то время как довольно тривиальный, его можно избежать.

Вместо того, чтобы использовать координаты X и y, просто использовать обычный int для хранения индексов в доску. А short может или не может быть быстрее. Чтобы перейти влево или вправо, просто добавить или вычесть единицу из индекса; чтобы идти вверх или вниз, просто добавить или вычесть 10. Вам нужно будет добавить проверку, чтобы убедиться, что вы не идете от угла, но вы должны делать это в любом случае.

3
ответ дан 18 марта 2018 в 03:03 Источник Поделиться

Интерфейс

Это довольно часто, чтобы заказать свой интерфейс от меньшего к большему ограничению. Т. е. public, protected, private. Таким образом пользователи вашего класса не придется прокручивать весь путь вниз, только чтобы увидеть, какие методы вы выставляете.

vector<bool> есть специальные

Это может иметь влияние на производительность, так что вы могли бы хотеть пересмотреть его использование. Если вы используете векторные убедитесь, что используете reserve чтобы избежать ненужных выделений.

Ранний выход

Во многих случаях это хорошая идея, чтобы выбрать для начала, если дела идут плохо.
Поэтому вместо того, чтобы:

if (condition) {
// do things
}

предпочитаю:

if (!condition) {
return;
}

// other code here

Таким образом, Вы избежать со стрелками код, который растет все больше и больше на правой части экрана

Накл.

В некоторых случаях вы по-прежнему использовать foo & вместо рекомендованных foo&. Ошибка копировать вставить?

Почему вы используете typedef и затем продолжать использовать Point в большинстве случаев? Это кажется несовместимым. Вы сказали Point это свою собственную реализацию, поэтому, если вы хотите другое имя просто переименовать класса/структуры.

Интересное использование template. Есть на корпусе, почему нельзя просто пройти gridSize в качестве параметра?
На этой ноте, если вы собираетесь использовать этот код, чтобы решить произвольных размеров сеток, вы могли бы взорвать ваш стек.

0
ответ дан 18 марта 2018 в 08:03 Источник Поделиться