Я работаю над программой на C ++, где мы должны пройти через граф вершин и взвешенных ребер так, чтобы мы начинали с указанной пользователем вершины, а затем заканчивали в той же самой вершине после прохождения определенного желаемого расстояния.
Я не уверен, как реализовать это с помощью кода, но у меня есть это до сих пор:
void DijkstrasShortestPath()
{
while (vertices.size() != 0)
{
Vertex* u = extract_min(vertices);
vector<Vertex*>* adjVertex = AdjVertices(u);
const int size = adjVertex->size();
for (int i=0; i<size; ++i)
{
Vertex* v = adjVertex->at(i);
int distance = travel_dist(u, v) +
u->distFromStart;
if (distance < v->distFromStart)
{
v->distFromStart = distance;
v->previous = u;
}
}
delete adjVertex;
}
}
Vertex* extract_min(vector<Vertex*>& vertices)
{
int size = vertices.size();
if (size == 0) {
return NULL;
}
int minimum = 0;
Vertex* min = vertices.at(0);
int i = 0;
for( i=1; i<size; ++i)
{
Vertex* temp = vertices.at(i);
if( temp->distFromStart < min->distFromStart) {
min = temp;
minimum = i;
}
}
vertices.erase(vertices.begin() + minimum);
return min;
}
vector <Vertex*>* AdjVertices(Vertex* vert)
{
vector<Vertex*>* adjVertex = new vector <Vertex*> ();
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
Vertex* adjacent = NULL;
if (edge->intersection1 == vert)
{
adjacent = edge->intersection2;
}
else if (edge->intersection2 == vert)
{
adjacent = edge->intersection1;
}
if (adjacent && vertices_check(vertices, adjacent))
{
adjVertex->push_back(adjacent);
}
}
return adjVertex;
}
int travel_dist(Vertex* u, Vertex* v)
{
const int size = edges.size();
for(int i=0; i<size; ++i)
{
Edge* edge = edges.at(i);
if (edge->street_connection(u, v))
{
return edge->distance;
}
}
return -1;
}
bool vertices_check(vector<Vertex*>& vertices, Vertex* vert)
{
const int size = vertices.size();
for(int i=0; i<size; ++i)
{
if (vert == vertices.at(i))
{
return true;
}
}
return false;
}
По сути, это алгоритм кратчайшего пути Дейкстры, который не совсем то, что я хочу. То, что я пытаюсь сделать, — это заставить программу рассчитать маршрут, расстояние которого находится в пределах 1 единицы от указанного пользователем расстояния и начинается и заканчивается в одной и той же вершине.
Есть ли способ сделать это, изменив то, что у меня есть?
Требует ли это поиска по ширине или по глубине вместо алгоритма Дейкстры?
Алгоритм Дейкстры будет хранить только кратчайший путь от начального узла до любого другого узла. Вместо этого вам нужно отслеживать все пути, ведущие к узлу. Если они у вас есть, вы можете проверять каждый раз, когда вы найдете новый путь к узлу, существует ли путь, который был найден до того, длина которого плюс длина нового пути находятся в пределах одной единицы от указанного пользователем расстояния. Если вы затем идете одним путем вперед, а другим назад — у вас есть петля.
Один из возможных методов.
Вы могли бы использовать ограниченное best-first search
.
Создать структуру P
который хранит список узлов, формирующих потенциальную петлю, вместе с длиной созданной петли.
Запустить поиск по указанной вершине S
делая отдельную P-структуру для каждого из узлов, которые S
ссылки на. Добавьте эти P-структуры в приоритетную очередь, которая отсортирована по длине пути, описанного P-структурой.
Рассмотрим каждый из этих узлов по очереди, удаляя их P-структуры из очереди приоритетов, копируя их P-структуры и добавляя узлы, на которые они ссылаются. Если добавляемый узел уже присутствует в P-структуре, а его нет S
, затем откажитесь от структуры и больше не рассматривайте этот маршрут. Аналогично, если какой-либо путь превышает указанную стоимость C
затем откажитесь от этого пути и больше не рассматривайте его. Если путь не был отброшен, добавьте связанную с ним P-структуру в очередь приоритетов.
Если S
действительно появляется в P-структуре дважды, и длина пути, описанного P-структурой, находится в допустимом диапазоне, затем успешно завершается. Если нет, продолжайте поиск, пока приоритетная очередь не станет пустой.
Вы можете ускорить алгоритм с помощью допустимая эвристика угадать расстояние от данного узла до S
добавление этого к установленной стоимости выполняемого пути и использование суммы в качестве ключа сортировки для очереди с приоритетами. Такая эвристика лежит в основе Алгоритм *, который может быть интересен для вас.
Это понятно? Если нет, я мог бы написать короткий пример кода.