Пройдите по графику от начальной точки и заканчивая в начальной точке Переполнение стека

Я работаю над программой на 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 единицы от указанного пользователем расстояния и начинается и заканчивается в одной и той же вершине.
Есть ли способ сделать это, изменив то, что у меня есть?

Требует ли это поиска по ширине или по глубине вместо алгоритма Дейкстры?

1

Решение

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

1

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

Один из возможных методов.

Вы могли бы использовать ограниченное best-first search.

Создать структуру P который хранит список узлов, формирующих потенциальную петлю, вместе с длиной созданной петли.

Запустить поиск по указанной вершине S делая отдельную P-структуру для каждого из узлов, которые S ссылки на. Добавьте эти P-структуры в приоритетную очередь, которая отсортирована по длине пути, описанного P-структурой.

Рассмотрим каждый из этих узлов по очереди, удаляя их P-структуры из очереди приоритетов, копируя их P-структуры и добавляя узлы, на которые они ссылаются. Если добавляемый узел уже присутствует в P-структуре, а его нет S, затем откажитесь от структуры и больше не рассматривайте этот маршрут. Аналогично, если какой-либо путь превышает указанную стоимость Cзатем откажитесь от этого пути и больше не рассматривайте его. Если путь не был отброшен, добавьте связанную с ним P-структуру в очередь приоритетов.

Если S действительно появляется в P-структуре дважды, и длина пути, описанного P-структурой, находится в допустимом диапазоне, затем успешно завершается. Если нет, продолжайте поиск, пока приоритетная очередь не станет пустой.

Вы можете ускорить алгоритм с помощью допустимая эвристика угадать расстояние от данного узла до Sдобавление этого к установленной стоимости выполняемого пути и использование суммы в качестве ключа сортировки для очереди с приоритетами. Такая эвристика лежит в основе Алгоритм *, который может быть интересен для вас.

Это понятно? Если нет, я мог бы написать короткий пример кода.

0

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