时间戳

首页 > 解决方案 > 递归地执行多次自我回避行走

c++ - 递归地执行多次自我回避行走

问题描述

我有一个 3D 简单立方晶格，我Grid在我的代码中调用它，周期性边界条件大小为 20x20x20（数字是任意的）。我想要做的是种植多个聚合度为 N 的聚合物链（具有 N 个节点的图）不重叠，是自我避免的。

目前，我可以递归地种植一种聚合物。这是我的代码

const std::vector <int> ex{1,0,0}, nex{-1,0,0}, ey{0,1,0}, ney{0,-1,0}, ez{0,0,1}, nez{0,0,-1};     // unit directions 
const std::vector <std::vector <int>> drns = {ex, nex, ey, ney, ez, nez};                           // vector of unit directions 

void Grid::plant_polymer(int DoP, std::vector <std::vector <int>>* loc_list){
    // loc_list is the list of places the polymer has been 
    // for this function, I provide a starting point 
    if (DoP == 0){
        Polymer p (loc_list); 
        this->polymer_chains.push_back(p); // polymer_chains is the attribute which holds all polymer chains in the grid 
        return; // once the degree of polymerization hits zero, you are done
    }; 

    // until then 
    // increment final vector in loc_list in a unit direction 
    std::vector <int> next(3,0); 
    for (auto v: drns){

        next = add_vectors(&((*loc_list).at((*loc_list).size()-1)), &v);
        
        impose_pbc(&next, this->x_len, this->y_len, this->z_len); 
        
        
        if (this->occupied[next]==0){ // occupied is a map which takes in a location, and spits out if it is occupied (1) or not (0)
// occupied is an attribute of the class Grid
            dop--; // decrease dop now that a monomer unit has been added 
            (*loc_list).push_back(next); // add monomer to list 
            this->occupied[next] == 1; 
            return plant_polymer(DoP, loc_list); 
        } 
    }


    std::cout << "no solution found for the self-avoiding random walk...";
    return;

这不是一个通用的解决方案。我正在为聚合物提供种子，而且，我只种植一种聚合物。我想让它可以种植多种聚合物，而无需指定种子。每次我想添加聚合物时，是否可以递归地寻找起始位置，然后构建聚合物，同时确保它不与系统中已有的其他聚合物重叠？您的任何建议将不胜感激。

标签： c++recursiongame-physicsrandom-walk

解决方案

至少自 1960 年代以来，人们一直在研究自我避免的步行，并且有大量关于它们的文献。幸运的是，您面临的问题属于最简单的问题（步行长度固定在一个相对较小的值）。

1

您应该注意的第一件事是，您的问题太宽泛，无法给出唯一的答案。也就是说，如果您在系统中种植许多聚合物，您将获得的结果取决于聚合物种植和生长的动态。主要有两种情况。要么种植许多种子并开始从中生长聚合物，要么在“其他地方”种植每种聚合物，然后尝试将它们一一种植在系统中的随机位置，保持自我回避的状态。这两种方法将导致聚合物在统计上不同的分布，除了更详细地指定系统动力学外，您无能为力。

我相信第二种方法更容易一些，因为如果某些聚合物不能长到所需的长度（重新开始模拟？），它可以让您不必决定该怎么做，所以让我们只关注它。

一般算法可能如下所示：

  • 设置maximum_number_of_attempts为相当大，但不是太大的值，比如一百万
  • 设置required_number_of_polymers为所需的值
  • 设置number_of_attempts为 0
  • 设置number_of_planted_polymers为 0
  • 而number_of_attempts<maximum_number_of_attempts和 number_of_planted_polymers<required_number_of_polymers
    • 增加number_of_attempts1
    • 生成下一个无规聚合物
    • 在系统中选择一个随机位置（晶格位置）
    • 检查聚合物是否可以在该位置种植而没有交叉点
    • 当且仅当是，
      • 接受聚合物（将其添加到聚合物列表中；更新占用的晶格节点列表）
      • 增加 number_of_planted_polymers1

为了加快速度，您可以仅从未占用的站点（例如在while循环中）选择初始位置。另一个想法是尝试使用聚合物，在第一次电镀失败时，在不同的位置多次（但不要太多，你需要试验）。

2

现在下一步：如何生成一个自我避免的随机游走。您的代码几乎没问题，除了一些误解。

在功能上有一个严重的错误：它总是以完全相同的顺序void Grid::plant_polymer在可能的聚合物形状的空间中执行搜索。换句话说，它是确定性的。对于蒙特卡洛方法来说，这听起来像是一场灾难。您可能会做的一件事是随机改变方向。

  auto directions = drns;
  std::shuffle(begin(directions), end(directions), random_generator); // c++17
  for (const auto & v: directions)
  {
    ...

为此，您需要一个已经定义和初始化的随机数生成器，例如

    std::random_device rd;
    std::mt19937 random_generator(rd());

在程序中更早的地方，并且只有一次。

如果您不使用 C++17，请使用std::random_shuffle而不是std::shuffle，但请注意前者已被贬值，请参阅https://en.cppreference.com/w/cpp/algorithm/random_shuffle讨论原因。

附带说明一下，当询问与软件相关的特定问题时，请尝试提供一个最小的、可重现的示例。仅基于阅读代码回答问题几乎总是更耗时，而且答案往往更粗略且不太准确。

推荐阅读