Рекурсивный алгоритм сетки путешествия


Я пытаюсь придумать решение для кодирования вызов на архив, где есть 2D сетки, заполненной с X и O, и цель состоит в том, чтобы выяснить, является ли или не дано начальной точки может достигнуть определенных координат, путешествуя вверх, вниз, влево или вправо. Только не судоходна, а ширина и высота сетки может быть до 1000 символов.

Вот пример сетки:

xoxxx
ooxxo
oxxxo
ooooo
oxxxx
ooooo

Я определяю это как

std::vector<std::string> space;

Для этого пространство, например, space[0][1] может достигать space[5][4].

Примечание: это не совсем проблема. Я обобщал его немного, потому что есть некоторые нюансы, которые немного не имеет отношения к эффективности. Вот актуальная проблема.

Я взял рекурсивный подход к этой проблеме, и моя программа проходит первые 22 из 25 общих тестов, прежде чем превышает 1-секундный лимит времени. Алгоритм, который я думал, должен был постоянно проверять, будет ли следующая действительная координата может дойти до конца. Базовый случай возникает, когда начальная координата конечной координат, а это означает, что начальная точка проблема может достигнуть конечной точки. Если нет рядом места, то текущий путь не может достичь конечной точки. Если все пути в тупик, то это означает, что отправная точка проблемы не может добраться до конечной точки.

Здесь находятся мозги программы (в частности canTravel):

struct Point {
    int x, y;
    friend bool operator==(const Point &p1, const Point &p2);
};

bool operator==(const Point &p1, const Point &p2) {
    return p1.x == p2.x && p1.y == p2.y;
}

std::vector<Point> memo; // take note of the visited locations to avoid revisiting them

bool memoContains(const Point &p1) {
    return std::find_if(memo.begin(), memo.end(), [&](const Point &p) { return p == p1; }) != memo.end();
}

bool canTravel(const std::vector<std::string> &space, const Point &start, const Point &end) {
    if (start == end) // base case: the start == the destination
        return true; 

    memo.push_back(start); // add current location to the list of visited locations

    /*
    format:

    const auto &next_location = avoid out of bounds error &&
        next location is an 'o' &&
        avoid revisiting a location &&
        recursively check whether the next location can reach the destination

    */

    const auto &right = start.x < space[start.y].length() - 1 && 
        space[start.y][start.x + 1] == 'o' && 
        !memoContains({ start.x + 1, start.y }) && 
        canTravel(space, { start.x + 1, start.y }, end);

    const auto &left = start.x > 0 && 
        space[start.y][start.x - 1] == 'o' && 
        !memoContains({ start.x - 1, start.y }) && 
        canTravel(space, { start.x - 1, start.y }, end);

    const auto &down = start.y < space.size() - 1 && 
        space[start.y + 1][start.x] == 'o' && 
        !memoContains({ start.x, start.y + 1 }) && 
        canTravel(space, { start.x, start.y + 1 }, end);

    const auto &up = p1.y > 0 && 
        space[start.y - 1][start.x] == 'o' && 
        !memoContains({ start.x, start.y - 1 }) && 
        canTravel(space, { start.x, start.y - 1 }, end);

    return right || left || down || up; // at least one path needs to reach the destination
}

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



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

Что убивает вашу производительность memoContains. Она превращает ваш алгоритм с O(Н) В О(N^2).

Лучшее решение-создать второй массив такого же размера, как ваш вклад, где вы отмечаете каждую ячейку посещал. Затем вы можете проверить за O(1).

Далее необходимо осуществить короткое замыкание по вашей логике. Если right верно, нет смысла в вычислении других направлениях.

Почему вы определяете right и трех других значений в качестве ссылок?

Есть еще несколько уловок, которые можно применить, например, чтобы избежать проверки на Ауте индексации, просто сделать массив на одну ячейку больше со всех сторон, и заполнять эти позиции с X.

Наконец, что касается рекурсии. Это хороший способ описания алгоритма. Вы можете получить лучшую производительность, если вы вместо того, чтобы использовать стек. Но единственный способ узнать наверняка-это проверить его и время. :)

Да, и еще одна вещь:

std::vector<std::string> space;

Это крайне неэффективно. Ваши данные по всей памяти, так как данные для каждого блока выделяется самостоятельно. Вы, вероятно, следует сделать это один вектор (или строки, если нужно), что вы индекс row * width + column. Обратите внимание, что теперь вы можете индексировать соседних клеток с помощью простой арифметики указателей (добавить 1 к указателю получить доступ к ячейке справа, например).

1
ответ дан 27 января 2018 в 03:01 Источник Поделиться