3

在“自我避免随机游走”的情况下，我有一个具有步长坐标配置的二维向量。我希望能够检查某个站点是否已被占用，但问题是轴可以为零，因此检查fabs()坐标是否为true（或它有一个值）将不起作用。因此，我考虑循环遍历这些步骤并检查我的坐标是否等于所有轴上的另一个坐标，如果是，则退后一步再试一次（所谓的深度优先方法）。

有没有更有效的方法来做到这一点？我见过有人使用具有所有可能坐标的布尔数组，如下所示：

bool occupied[nMax][nMax];          // true if lattice site is occupied
for (int y = -rMax; y <= rMax; y++)
        for (int x = -rMax; x <= rMax; x++)
            occupied[index(y)][index(x)] = false;

但是，在我的程序中，维数是未知的，因此可以采用以下方法：

typedef std::vector<std::vector<long int>> WalkVec;
WalkVec walk(1, std::vector<long int>(dof,0));
siteVisited = false; counter = 0;  
            while (counter < (walkVec.back().size()-1))
            {
                tdof = 1;
                while (tdof <= dimensions)
                {

                    if (walkHist.back().at(tdof-1) == walkHist.at(counter).at(tdof-1) || walkHist.back().at(tdof-1) == 0)
                    {
                        siteVisited = true;
                    }
                    else
                    {
                        siteVisited = false;
                        break;
                    }
                    tdof++;
                }

work where dof if 维数。（检查零检查位置是否是原点。三个零坐标或同一步骤上的三个访问坐标是使其成为真的唯一方法）有没有更有效的方法呢？

4

2 回答 2

3

您可以分别使用 STL 的 set 或 unordered_set 在 O(log n) 或 O(1) 时间内执行此检查。unordered_set 容器需要你为你的坐标编写一个自定义的散列函数，而 set 容器只需要你提供一个比较函数。set 实现特别简单，对数时间应该足够快：

#include <iostream>
#include <set>
#include <vector>
#include <cassert>

class Position {
public:
    Position(const std::vector<long int> &c)
        : m_coords(c) { }

    size_t dim() const { return m_coords.size(); }
    bool operator <(const Position &b) const {
        assert(b.dim() == dim());
        for (size_t i = 0; i < dim(); ++i) {
            if (m_coords[i] < b.m_coords[i])
                return true;
            if (m_coords[i] > b.m_coords[i])
                return false;
        }
        return false;
    }

private:
    std::vector<long int> m_coords;
};

int main(int argc, const char *argv[])
{
    std::set<Position> visited;
    std::vector<long int> coords(3, 0);
    visited.insert(Position(coords));

    while (true) {
        std::cout << "x, y, z: ";
        std::cin >> coords[0] >> coords[1] >> coords[2];
        Position candidate(coords);
        if (visited.find(candidate) != visited.end())
            std::cout << "Aready visited!" << std::endl;
        else
            visited.insert(candidate);
    }
    return 0;
}

当然，正如 iavr 所提到的，任何这些方法都需要 O(n) 存储。

编辑：这里的基本思想很简单。目标是以一种允许您快速检查是否已访问过特定位置的方式存储所有访问过的位置。您的解决方案必须扫描所有访问过的位置才能进行此检查，这使得它成为 O(n)，其中 n 是访问过的位置的数量。为了更快地做到这一点，您需要一种方法来排除大多数访问过的位置，这样您根本不必与它们进行比较。

您可以通过考虑对排序数组进行二进制搜索来理解我的基于集合的解决方案。首先，您想出一种比较（排序）D 维位置的方法。这就是 Position 类的 < 运算符正在做的事情。正如 iavr 在评论中指出的那样，这基本上只是一个字典比较。然后，当所有访问的位置都按此顺序排序时，您可以运行二进制搜索来检查候选点是否已被访问：您递归地检查候选点是否会在列表的上半部分或下半部分找到，消除一半在每一步比较的剩余列表。在每一步中将搜索域减半为您提供对数复杂度 O(log n)。

STL 集容器只是一个很好的数据结构，它可以在插入和删除元素时保持元素的排序，确保插入、删除和查询都很快。如果您好奇，我使用的 STL 实现使用红黑树来实现此数据结构，但从您的角度来看，这无关紧要；重要的是，一旦你给它一种比较元素的方法（< 运算符），将元素插入集合（set::insert）并询问一个元素是否在集合中（set::find）是 O(日志 n)。我只是通过将其添加到访问集来检查原点——没有理由特别对待它。

unordered_set 是一个哈希表，是一种渐近更高效的数据结构 (O(1))，但更难使用，因为您必须编写一个好的哈希函数。此外，对于您的应用程序，从 O(n) 到 O(log n) 应该足够好。

于 2013-11-18T15:11:20.953 回答
2

您的问题涉及算法而不是（C++）语言的使用，所以这里是一个通用的答案。

您需要一个数据结构来存储一组（点坐标），并通过有效的操作来查询新点是否在集合中。

将集合显式存储为布尔数组提供了恒定时间查询（最快），但在空间中，维度数是指数的。

详尽搜索（您的第二个选项）提供在集合大小（步行长度）中线性的查询，在集合大小也是线性且与维度无关的空间中。

其他两个常见的选项是树结构和哈希表，例如可用std::set（通常使用红黑树）和std::unordered_set（后者仅在 C++11 中）。树结构通常具有对数时间查询，而哈希表查询实际上可以是恒定时间的，几乎让您回到布尔数组的复杂性。但是在这两种情况下，所需的空间在集合大小上也是线性的，并且与维度无关。

于 2013-11-18T15:09:43.650 回答