Алгоритм A* - История изменений

Ctrlalt в 14:03, 1 января 2026

2026-01-01T14:03:35Z

← Предыдущая версия		Версия от 14:03, 1 января 2026
Строка 38:		Строка 38:
	\|width=50%\|		\|width=50%\|
	int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {		int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {
	vector<int> dist(graph.size, 1e9);		vector<int> dist(graph.size(), 1e9);
	{{Changed\|1=vector<int> distH(graph.size(), 1e9);}}		{{Changed\|1=vector<int> distH(graph.size(), 1e9);}}
	set<pair<int, int>> q;		set<pair<int, int>> q;

Ctrlalt: /* Общая схема перехода от Дейкстры к A* */

2022-12-12T01:08:28Z

Общая схема перехода от Дейкстры к A*

← Предыдущая версия		Версия от 01:08, 12 декабря 2022
Строка 6:		Строка 6:
	* Заметим, что если h() всегда возвращает 0, то A* превращается в алгоритм Дейкстры.		* Заметим, что если h() всегда возвращает 0, то A* превращается в алгоритм Дейкстры.

	~~{\|width=100%~~
	~~\|width=50%\|~~
	{\|width=100%		{\|width=100%
	\|width=50%\|		\|width=50%\|

Ctrlalt: /* Общая схема перехода от Дейкстры к A* */

2022-10-07T07:21:23Z

Общая схема перехода от Дейкстры к A*

← Предыдущая версия		Версия от 07:21, 7 октября 2022
Строка 40:		Строка 40:
	\|width=50%\|		\|width=50%\|
	int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {		int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {
	vector<int> dist(size, 1e9);		vector<int> dist(graph.size, 1e9);
	{{Changed\|1=vector<int> distH(graph.size(), 1e9);}}		{{Changed\|1=vector<int> distH(graph.size(), 1e9);}}
	set<pair<int, int>> q;		set<pair<int, int>> q;

Ctrlalt: /* Общая схема перехода от Дейкстры к A* */

2022-04-07T02:14:28Z

Общая схема перехода от Дейкстры к A*

← Предыдущая версия		Версия от 02:14, 7 апреля 2022
Строка 29:		Строка 29:
	if (dist[to] > dist[v] + w) {		if (dist[to] > dist[v] + w) {
	q.erase({ dist[to], to });		q.erase({ dist[to], to });
	dist[to] = dist[v] + 1;		dist[to] = dist[v] + w;
	q.insert({ dist[to], to });		q.insert({ dist[to], to });
	}		}
Строка 58:		Строка 58:
	if (dist[to] > dist[v] + w) {		if (dist[to] > dist[v] + w) {
	q.erase({ {{Changed\|distH}}[to], to });		q.erase({ {{Changed\|distH}}[to], to });
	dist[to] = dist[v] + 1;		dist[to] = dist[v] + w;
	{{Changed\|1=distH[to] = dist[to] + h(to);}}		{{Changed\|1=distH[to] = dist[to] + h(to);}}
	q.insert({ {{Changed\|distH}}[to], to });		q.insert({ {{Changed\|distH}}[to], to });

Ctrlalt: /* Общая схема перехода от Дейкстры к A* */

2021-12-26T03:13:56Z

Общая схема перехода от Дейкстры к A*

← Предыдущая версия		Версия от 03:13, 26 декабря 2021
Строка 11:		Строка 11:
	\|width=50%\|		\|width=50%\|
	int dijkstra(vector<vector<pair<int, int>>> &graph, int start, int finish) {		int dijkstra(vector<vector<pair<int, int>>> &graph, int start, int finish) {
	~~vector<~~vector<int>> dist~~(graph.size(), vector<int>~~(graph.size(), 1e9));		vector<int> dist(graph.size(), 1e9);
	set<pair<int, int>> q;		set<pair<int, int>> q;

Строка 40:		Строка 40:
	\|width=50%\|		\|width=50%\|
	int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {		int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {
	~~vector<~~vector<int>> dist(size~~, vector<int>(graph.size()~~, 1e9));		vector<int> dist(size, 1e9);
	{{Changed\|1=~~vector<~~vector<int>> distH~~(graph.size(), vector<int>~~(graph.size(), 1e9));}}		{{Changed\|1=vector<int> distH(graph.size(), 1e9);}}
	set<pair<int, int>> q;		set<pair<int, int>> q;

Ctrlalt: /* Общая схема перехода от Дейкстры к A* */

2021-12-26T03:09:57Z

Общая схема перехода от Дейкстры к A*

← Предыдущая версия		Версия от 03:09, 26 декабря 2021
Строка 11:		Строка 11:
	\|width=50%\|		\|width=50%\|
	int dijkstra(vector<vector<pair<int, int>>> &graph, int start, int finish) {		int dijkstra(vector<vector<pair<int, int>>> &graph, int start, int finish) {
	vector<vector<int>> dist(size, vector<int>(size, 1e9));		vector<vector<int>> dist(graph.size(), vector<int>(graph.size(), 1e9));
	set<pair<int, int>> q;		set<pair<int, int>> q;

Строка 40:		Строка 40:
	\|width=50%\|		\|width=50%\|
	int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {		int aStar(vector<vector<pair<int, int>>> &graph, int start, int finish) {
	vector<vector<int>> dist(size, vector<int>(size, 1e9));		vector<vector<int>> dist(size, vector<int>(graph.size(), 1e9));
	{{Changed\|1=vector<vector<int>> distH(size, vector<int>(size, 1e9));}}		{{Changed\|1=vector<vector<int>> distH(graph.size(), vector<int>(graph.size(), 1e9));}}
	set<pair<int, int>> q;		set<pair<int, int>> q;

Ctrlalt: /* Ссылки */

2021-08-07T01:41:04Z

Ссылки

← Предыдущая версия		Версия от 01:41, 7 августа 2021
Строка 304:		Строка 304:

	== Ссылки ==		== Ссылки ==
			* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_A* neerc.ifmo.ru/wiki — Алгоритм A*]
	* [http://www.redblobgames.com/pathfinding/a-star/introduction.html Red Blob Games — Introduction to the A* Algorithm]		* [http://www.redblobgames.com/pathfinding/a-star/introduction.html Red Blob Games — Introduction to the A* Algorithm]
	* [http://www.redblobgames.com/pathfinding/a-star/implementation.html Red Blob Games — Implementation of A*]		* [http://www.redblobgames.com/pathfinding/a-star/implementation.html Red Blob Games — Implementation of A*]

Ctrlalt в 01:27, 7 августа 2021

2021-08-07T01:27:53Z

Внесённые изменения

Ctrlalt в 05:31, 30 июня 2021

2021-06-30T05:31:02Z

@@ Строка 1: / Строка 1: @@
   const int SIDE = 4;
   const int SIZE = SIDE * SIDE;
@@ Строка 53: / Строка 58: @@
       return in;
+  }
+|-
   string aStar(Board &board) {
       if (board.unsolvable)
@@ Строка 73: / Строка 80: @@
           q.erase(q.begin());
-          if (!v.manhattanHeuristic) {
+          if (!v.manhattanHeuristic)
               break;
           for (int d = 0; d < 4; d++) {
@@ Строка 84: / Строка 89: @@
               Board to = v.move(dy[d], dx[d]);
-              if (auto it = dist.find(to); it == dist.end() || it->second > vDist + to.manhattanHeuristic) {
+              if (auto it = dist.find(to); it == dist.end() ||
                   q.erase({ dist[to], to });
                   dist[to] = vDist + to.manhattanHeuristic;
@@ Строка 92: / Строка 98: @@
+          }
+      }
       string path;
@@ Строка 110: / Строка 120: @@
       cout << aStar(board) << "\n";
+  }
 == Ссылки ==

Ctrlalt в 03:33, 30 июня 2021

2021-06-30T03:33:22Z

← Предыдущая версия		Версия от 03:33, 30 июня 2021
Строка 1:		Строка 1:
			const int SIDE = 4;
			const int SIZE = SIDE * SIDE;

			struct Board {
			vector<int> a;
			int zy, zx, manhattanHeuristic, unsolvable;

			void recalculate() {
			manhattanHeuristic = 0;
			int inv = 0;
			for (int y = 0; y < SIDE; y++) {
			for (int x = 0; x < SIDE; x++) {
			if (a[y * SIDE + x]) {
			for (int d = 0; d < y * SIDE + x; d++)
			inv += a[d] && a[d] > a[y * SIDE + x];
			} else {
			zy = y;
			zx = x;
			}
			int tile = (a[y * SIDE + x] + SIZE - 1) % SIZE;
			int ty = tile / SIDE, tx = tile % SIDE;
			manhattanHeuristic += abs(y - ty) + abs(x - tx);
			}
			}
			unsolvable = (inv + zy) % 2 == 0;
			}

			bool operator < (const Board &that) const {
			if (manhattanHeuristic != that.manhattanHeuristic)
			return manhattanHeuristic < that.manhattanHeuristic;
			return a < that.a;
			}

			bool canMove(int dy, int dx) {
			int ty = zy + dy, tx = zx + dx;
			return 0 <= ty && ty < SIDE && 0 <= tx && tx < SIDE;
			}

			Board move(int dy, int dx) {
			Board res = *this;
			int ty = zy + dy, tx = zx + dx;
			swap(res.a[zy * SIDE + zx], res.a[ty * SIDE + tx]);
			res.recalculate();
			return res;
			}
			};

			istream &operator >> (istream &in, Board &board) {
			board.a.resize(SIZE);
			for (int i = 0; i < SIZE; i++)
			in >> board.a[i];
			board.recalculate();
			return in;
			}

			string aStar(Board &board) {
			if (board.unsolvable)
			return "NO SOLUTION";

			set<pair<int, Board>> q;
			map<Board, int> dist, pred;

			q.insert({ board.manhattanHeuristic, board });
			dist[board] = board.manhattanHeuristic;
			pred[board] = -1;

			static vector<int> dy = { -1, 0, 1, 0 };
			static vector<int> dx = { 0, 1, 0, -1 };
			static string dc = "URDL";

			while (!q.empty()) {
			auto [vDist, v] = *q.begin();
			q.erase(q.begin());

			if (!v.manhattanHeuristic) {
			board = v;
			break;
			}

			for (int d = 0; d < 4; d++) {
			if (!v.canMove(dy[d], dx[d]))
			continue;

			Board to = v.move(dy[d], dx[d]);

			if (auto it = dist.find(to); it == dist.end() \|\| it->second > vDist + to.manhattanHeuristic) {
			q.erase({ dist[to], to });
			dist[to] = vDist + to.manhattanHeuristic;
			pred[to] = d;
			q.insert({ dist[to], to });
			}
			}
			}

			string path;
			while (1) {
			int d = pred[board];
			if (d == -1)
			break;
			path.push_back(dc[d]);
			board = board.move(dy[(d + 2) % 4], dx[(d + 2) % 4]);
			}
			reverse(path.begin(), path.end());
			return path;
			}

			void solve() {
			Board board;
			cin >> board;
			cout << aStar(board) << "\n";
			}

	== Ссылки ==		== Ссылки ==
	* [http://www.redblobgames.com/pathfinding/a-star/introduction.html Red Blob Games — Introduction to the A* Algorithm]		* [http://www.redblobgames.com/pathfinding/a-star/introduction.html Red Blob Games — Introduction to the A* Algorithm]