5

我在部分（？）隐式的图上运行 astar 算法 - 它是从大型分页数据源构建的，但图是持久的。每当 astar 算法到达未完全分页的区域时，我都需要在图形的新部分中处理分页 - 理想情况下，无需完全重新开始 astar 搜索。

我尝试了几种解决方案，但遇到了一些障碍，我想知道我是否遗漏了一些明显的东西，或者只是错误地解决了问题。

我目前正在使用 boost 1.45，但计划升级到 1.51。

首先，我尝试修改 astar 访问者，以便当它确定需要分页新数据时，它会调用图形上的一个函数并将其加载 - 但是，由于图形是 const，这是不可能的。我环顾四周，发现另一个问题boostimplicit graph 和 astar_search_no_init引用了一个演示文稿，该演示文稿表明有人已经完成了使这成为可能的工作，但看起来实际代码不可用。

其次，我认为当我到达需要分页更多数据的地方时，我可能能够退出算法，并保存 distance_map、previous_map 和 color_map 的状态，以便我可以使用它们“恢复”使用 astar_search_no_init 进行搜索。我不确定这是否可行，因为一旦我切换到使用 astar_search_no_init，我看到虽然访问者似乎在做寻路工作，但前任地图是空的 - 因为我使用前任地图来构建路径访客完成后，我需要知道访客是如何构建路径的。

这是我的图表的定义以及我如何调用 astar_search，如果这有帮助的话。

typedef adjacency_list<
     vecS,         
     vecS,        
     undirectedS, 
     VertexInfo,        //contains geographic location     
     EdgeInfo,          //contains weight information             
     no_property,     
     setS>            
        BoostGraph;
...
ColorMap cmap = get(vertex_color_t, myGraph);           
astar_search(
     myGraph, 
     source,
     distance_heuristic(myGraph, destination), //geometric distance heuristic
     predecessor_map(&srcPredmap[0]).
     distance_map(&distMap[0]).
     color_map(cmap).
     visitor(astar_goal_visitor<vertex_descriptor>(destination, this)). //throws an exception when it finds the goal
     weight_map(make_function_property_map<edge_descriptor>(  //copied make_function_property_map functionality from boost 1.51 since I can't upgrade just yet
        EdgeWeightAdjuster(&myGraph, weightFactors))));       //modifies edge weights based on weightFactors construct
4

1 回答 1

1

您写道：“但是，由于图形是 const，所以这是不可能的……”那么简单的 CAST（事件是旧的 C-cast）呢？您应该至少尝试一下这个选项。修改图可能会使迭代器等无效。这是真的。尽管如此，您仍然应该尝试。

“技术常数”和“概念常数”是有区别的。在你的情况下，你只会打破技术，而不是概念。

于 2012-09-24T04:23:58.483 回答