Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <queue>
- #include <cmath>
- #include <climits>
- using namespace std;
- // Структура для хранения информации о вершине
- struct Vertex {
- double g = numeric_limits<double>::max(); // Стоимость пути от начальной вершины до данной
- double h; // Эвристическая оценка стоимости пути от данной вершины до конечной
- double f; // Общая стоимость пути (g + h)
- char parent; // Родительская вершина в пути
- };
- // Структура для сравнения вершин в очереди
- struct Compare {
- bool operator()(const pair<char, Vertex>& a, const pair<char, Vertex>& b) {
- return a.second.f > b.second.f;
- }
- };
- // Функция для вычисления эвристической оценки
- double heuristic(char a, char b) {
- return abs(a - b);
- }
- string aStar(map<char, vector<pair<char, double>>>& graph, char start, char goal) {
- map<char, Vertex> vertices;
- priority_queue<pair<char, Vertex>, vector<pair<char, Vertex>>, Compare> pq;
- // Инициализация начальной вершины
- vertices[start].g = 0;
- vertices[start].h = heuristic(start, goal);
- vertices[start].f = vertices[start].g + vertices[start].h;
- vertices[start].parent = ' ';
- pq.push({ start, vertices[start] });
- while (!pq.empty()) {
- char current = pq.top().first;
- pq.pop();
- if (current == goal) {
- string path;
- while (current != ' ') {
- path = current + path;
- current = vertices[current].parent;
- }
- return path;
- }
- for (auto& neighbor : graph[current]) {
- char next = neighbor.first;
- double tentative_g = vertices[current].g + neighbor.second;
- //cout << next << ' ' << tentative_g << ' ' << vertices[next].g << '\n';
- if (tentative_g < vertices[next].g) {
- vertices[next].g = tentative_g;
- vertices[next].h = heuristic(next, goal);
- vertices[next].f = vertices[next].g + vertices[next].h;
- vertices[next].parent = current;
- pq.push({ next, vertices[next] });
- }
- }
- //cout << current << '\n';
- }
- return "No path found";
- }
- int main() {
- map<char, vector<pair<char, double>>> graph;
- char start, goal;
- cin >> start >> goal;
- char from, to;
- double weight;
- while (cin >> from >> to >> weight) {
- graph[from].insert(graph[from].end(), {make_pair(to, weight)});
- }
- /*for (const auto& vert : graph) {
- std::cout << "vert = " << vert.first << '\n';
- for (const auto& pair : vert.second) {
- std::cout << " end vert = " << pair.first << " weight = " << pair.second;
- }
- std::cout << "\n";
- }*/
- string path = aStar(graph, start, goal);
- cout << path << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement