повысить A * посетителя с пользовательским штрафом веса края?

Я играю с алгоритмом Boost A *, начав с примера, найденного на: http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cpp

Я вижу, что вы можете переопределить его эвристику и его посетителя, чтобы иметь какие-то пользовательские настройки, просто я пока не совсем понял концепцию для такой вещи, как следующее, в качестве примера обучения, я хотел бы, чтобы алгоритм НЕ выбирайте город края — город, если время в пути (вес края) больше X, например 100 минут. (только если возможно, если никакой другой путь не найден, тогда этот город должен быть выбран, а не найден)

Я попробовал пользовательский эвристический класс, который возвращает больше времени, чем реальность, чтобы «обмануть» его, чтобы он не выбирал этот город, однако проблема в том, что с этим приемом штрафной город отбрасывается даже для дальнейших взаимодействий. (Следующий пример объясняет это: B-> D отбрасывается, поскольку найден лучший путь, но город D не отбрасывается (вы видите, что он выбран в следующей итерации)

Итак, я упростил задачу:

enum nodes {
A, B, C, D, E, N
};
const char *name[] = {
"A", "B", "C", "D", "E", "F"};
edge edge_array[] = {
edge(A,B), edge(B,C),
edge(C,D), edge(D,E),
edge(B,D) // B to D is the problem here, it should be excluded
};
cost weights[] = { // estimated travel time (mins)
// 107, 174, 283, 71, 436
35, 58, 94, 23, 145
};

В этом примере (взяв код из оригинала в качестве базы), я получаю маршрут:

Начальная вершина: A

Вершина цели: E

Кратчайший путь от A до E: A -> B -> D -> E

Общее время в пути: 204,5

Проблема состоит в том, что путь B -> D является таким большим расстоянием (например, если предположить пороговое значение 100, которое будет предпочтительнее для пути, подобного: A -> B -> C -> D -> E, таким образом, расстояние между двумя городами не превышает 100 (конечно, только если это возможно, если нет другого пути, нужно выбирать какой-либо другой)

Я решил это неоптимальным способом: пользовательская функция, добавив ребро, (или установив вес вручную) return travelTime > 100 ? travelTime * 2 : travelTime, что может быть достигнуто для тестирования с:

cost weights[] = { // estimated travel time (mins)
// 107, 174, 283, 71, 436
(35 > 100) ? 35*2 : 35, (58 > 100) ? 58*2 : 58, (94>100) ? 94*2 : 94, 23, (145 > 100) ? 145*2 : 145
}; // The comparisons are not needed, just there to better explain what the custom add_edge function will do.

С помощью этого метода я получаю желаемое A -> B -> C -> D -> E, но, таким образом, это просто взломать / обойти проблему и внутренне изменить входные данные, что, я думаю, не самое лучшее решение.

Есть ли лучший способ добиться этого без необходимости вручную менять расстояние / время в пути?

1

Решение

Я думаю, что вы просто хотели кратчайшие пути здесь (с dijkstra было бы хорошо).

Ключ должен понять, что вы можете использовать клиента edge_weight карта недвижимости. Это может быть, например, boost::property_map::transform_value_property_map<> вот так:

auto my_custom_weight_map =
boost::make_transform_value_property_map(
[](float w) { return w>100? 10*w : w; },
boost::get(boost::edge_weight, g));

Вы видите, что любой вес ребра выше 100 будет увеличен в десять раз.

Затем, вы в основном уже сделали:

    astar_search_tree(g, start,
distance_heuristic<mygraph_t, cost>(goal),
boost::weight_map(my_custom_weight_map) // THIS LINE ADDED
.predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g)))
.distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g)))
.visitor(astar_goal_visitor<vertex>(goal))
);

И результат:

Start vertex: A
Goal vertex: E
Shortest path from A to E: A -> B -> C -> D -> E
Total travel time: 210

Жить на Колиру

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/property_map/transform_value_property_map.hpp>
#include <iostream>
#include <list>

// auxiliary types
struct location {
float y, x; // lat, long
};

typedef float cost;

// euclidean distance heuristic
template <class Graph, class CostType>
class distance_heuristic : public boost::astar_heuristic<Graph, CostType> {
public:
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
distance_heuristic(Vertex goal) : m_goal(goal) {}
CostType operator()(Vertex /*u*/) {
return 0; // Not really needed here
}

private:
Vertex m_goal;
};

struct found_goal {}; // exception for termination

// visitor that terminates when we find the goal
template <class Vertex> class astar_goal_visitor : public boost::default_astar_visitor {
public:
astar_goal_visitor(Vertex goal) : m_goal(goal) {}
template <class Graph> void examine_vertex(Vertex u, Graph &/*g*/) {
if (u == m_goal)
throw found_goal();
}

private:
Vertex m_goal;
};

int main() {
// specify some types
typedef boost::adjacency_list<boost::listS, boost::vecS,
boost::undirectedS, boost::no_property,
boost::property<boost::edge_weight_t, cost>
> mygraph_t;

typedef boost::property_map<mygraph_t, boost::edge_weight_t>::type WeightMap;
typedef mygraph_t::vertex_descriptor vertex;
typedef mygraph_t::edge_descriptor edge_descriptor;
typedef std::pair<int, int> edge;

enum nodes { A, B, C, D, E, N };
const char *name[] = { "A", "B", "C", "D", "E", "F" };
edge edge_array[] = {
edge(A, B), edge(B, C), edge(C, D), edge(D, E), edge(B, D) // B to D is the problem here, it should be excluded
};
cost weights[] = { // estimated travel time (mins)
// 107, 174, 283, 71, 436
35, 58, 94, 23, 145
};

unsigned int num_edges = sizeof(edge_array) / sizeof(edge);

// create graph
mygraph_t g(N);
WeightMap weightmap = get(boost::edge_weight, g);
for (std::size_t j = 0; j < num_edges; ++j) {
edge_descriptor e;
bool inserted;
boost::tie(e, inserted) = add_edge(edge_array[j].first, edge_array[j].second, g);
weightmap[e] = weights[j];
}

// pick start/goal
vertex start = A;
vertex goal = E;

std::cout << "Start vertex: " << name[start] << std::endl;
std::cout << "Goal vertex: "  << name[goal]  << std::endl;

std::vector<mygraph_t::vertex_descriptor> p(num_vertices(g));

using boost::get;

// do a real edit
std::vector<cost> d(num_vertices(g));

auto my_custom_weight_map =
boost::make_transform_value_property_map(
[](float w) { return w>100? 10*w : w; },
boost::get(boost::edge_weight, g));

try {
// call astar named parameter interface
astar_search_tree(g, start,
distance_heuristic<mygraph_t, cost>(goal),
boost::weight_map(my_custom_weight_map)
.predecessor_map(make_iterator_property_map(p.begin(), get(boost::vertex_index, g)))
.distance_map(make_iterator_property_map(d.begin(), get(boost::vertex_index, g)))
.visitor(astar_goal_visitor<vertex>(goal))
);

} catch (found_goal fg) { // found a path to the goal
std::list<vertex> shortest_path;
for (vertex v = goal;; v = p[v]) {
shortest_path.push_front(v);
if (p[v] == v)
break;
}

std::cout << "Shortest path from " << name[start] << " to " << name[goal] << ": ";
std::list<vertex>::iterator spi = shortest_path.begin();
std::cout << name[start];

for (++spi; spi != shortest_path.end(); ++spi)
std::cout << " -> " << name[*spi];

std::cout << std::endl << "Total travel time: " << d[goal] << std::endl;
return 0;
}

std::cout << "Didn't find a path from " << name[start] << "to" << name[goal] << "!" << std::endl;
return 0;
}
1

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

То, что вы пытаетесь сделать, не имеет ничего общего с эвристикой. Алгоритм поиска A * — это поиск в ширину с преимуществами. Эвристика есть, чтобы добавить нижняя граница до какой будет окончательная стоимость. Для карты с указанием улиц прямое расстояние — идеальная эвристика. Смысл эвристики заключается в том, чтобы вы расширили своих наиболее вероятных кандидатов перед своими наиболее вероятными кандидатами. Опять же, в смысле карты, поиск в ширину будет в основном кружить наружу, пока вы не найдете свой пункт назначения, в то время как эвристика делает это так, чтобы вы могли просачиваться прямо к пункту назначения и иметь гораздо меньше путей, которые стоит рассмотреть. С другой точки зрения — эвристика — это функция, которая берет текущую последнюю точку пути и точку назначения и возвращает стоимость. Вы не можете использовать его для исключения ребер, так как он не знает о пути. Он знает только о двух моментах.

Вернемся к вашей проблеме. Ты хочешь:

Я бы хотел, чтобы алгоритм НЕ выбирал город края — город, если время в пути (вес края) больше X, например 100 минут. (только если возможно, если никакой другой путь не найден, тогда этот город должен быть выбран, а не найден)

Эвристический ничего такого делать с конкретными узлами графа или ребрами. Это просто оценка окончательной стоимости и, вероятно, не должна зависеть от самого графика. То, что вы просите, связано с весами. A * — это поиск пути с минимальным весом. Если вы хотите, чтобы край НЕ был взят … просто увеличьте его вес!

Пример, на который вы ссылаетесь, имеет следующие значения:

cost weights[] = { // estimated travel time (mins)
96, 134, 143, 65, 115, 133, 117, 116, 74, 56,
84, 73, 69, 70, 116, 147, 173, 183, 74, 71, 124
};

Вы хотите новые веса, в основном:

auto new_weights = at_most(weights, 100); // I don't want to use any edges
// that take 100 minutes

Который мы могли бы написать так:

template <size_t N>
std::array<cost, N> at_most(cost (&old)[N], cost max_cost) {
cost total = std::accumulate(old, old+N, 0.0f) * N;
std::array<cost, N> new_weights;
for (size_t i = 0; i < N; ++i) {
new_weights[i] = old[i] < max_cost ? old[i] : old[i] + total;
}
return new_weights;
}

По сути, мы просто суммируем ВСЕ веса и заменяем все ребра, стоимость которых превышает сумму, указанную вами в качестве максимума, новым весом, превышающим взятие ВСЕ ребер. Конечным результатом этого является то, что если существует путь, который не использует ни одного из> 100-весовых ребер, он определенно будет иметь меньшую общую стоимость, чем этот новый путь. Конкретный новый вес, который мы используем, не важен, он просто должен быть достаточно большим, чтобы гарантировать правдивость предыдущего утверждения.

Нам не нужно менять эвристику. Просто вес.

3

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector