Возобновление поиска звезд в BGL

Я использую алгоритм Astar на графике, который частично (?) Неявный — он построен из большого источника данных подкачки, но график является постоянным. Мне нужно обрабатывать разбиение на страницы в новых частях графика всякий раз, когда алгоритм Astar попадает в область, которая не полностью разбита на страницы — в идеале, без полного запуска поиска Astar.

Я попробовал пару решений, но столкнулся с некоторыми препятствиями, и мне интересно, упускаю ли я что-то очевидное или просто неправильно подхожу к проблеме.

Я в настоящее время использую повышение 1.45, но планирую обновить до 1.51.

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

Во-вторых, я подумал, что смогу выйти из алгоритма, когда доберусь до места, где мне нужно разместить больше данных, и сохранить состояние distance_map, precessor_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

5

Решение

Вы пишете: «однако, поскольку граф является константой, это невозможно …» А как насчет простого CAST (события старого C-cast)? Вы должны дать эту возможность хотя бы попробовать. Изменение графика может сделать недействительными итераторы и т. Д. Это правда. Тем не менее, вы все равно должны попробовать.

Существует различие между «техническим постоянством» и «концептуальным постоянством». В вашем случае вы сломаете только технический, а не концептуальный.

1

Другие решения

Других решений пока нет …