A* search algorithm

Resources:

wikipedia.org ==> A*_search_algorithm

hackerearth blog

GFG

stanford.edu

hackerrank Problems

implementation from Youtube Video:

	/// A*( A-star) Algorithm.
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 1000005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	const ll mod = 1e9 + 7;
	inline void normal(ll &a) { a %= mod; (a < 0) && (a += mod); }
	inline ll modMul(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
	inline ll modAdd(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
	inline ll modSub(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
	inline ll modPow(ll b, ll p) { ll r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
	inline ll modInverse(ll a) { return modPow(a, mod - 2); }
	inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
	///**
	template < typename F, typename S >
	ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << *it;
	}
	return os << "}";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin()) os << ", ";
	os << *it;
	}
	return os << "]";
	}
	template < typename F, typename S >
	ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << it -> first << " = " << it -> second ;
	}
	return os << "]";
	}
	#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
	clock_t tStart = clock();
	#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
	void faltu () { cerr << endl; }
	template <typename T>
	void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
	}
	template <typename T, typename ... hello>
	void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
	// Program showing a policy-based data structure.
	#include <ext/pb_ds/assoc_container.hpp> // Common file
	#include <ext/pb_ds/tree_policy.hpp>
	#include <functional> // for less
	#include <iostream>
	using namespace __gnu_pbds;
	using namespace std;
	// GNU link : https://goo.gl/WVDL6g
	typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update>
	new_data_set;
	// find_by_order(k) – ফাংশনটি kth ordered element এর একটা পয়েন্টার রিটার্ন করে। অর্থাৎ তুমি চাইলেই kth ইন্ডেক্সে কি আছে, সেটা জেনে ফেলতে পারছো!
	// order_of_key(x) – ফাংশনটি x এলিমেন্টটা কোন পজিশনে আছে সেটা বলে দেয়।
	/**___________________________________________________**/
	const int N = 10000;
	const int E = 30000;
	int dist[N], current, current_time, edge, new_time;
	list<int>:: iterator it;
	list<int> graph[N];
	int edge_to[E];
	int edge_weight[E];
	int edge_from[E];
	int edge_t0[E];
	int edge_P[E];
	int edge_d[E];
	int n, m, q, s, g;
	void dijkstra()
	{
	priority_queue<int, vector<int>, greater<int> > PQ;
	for (int i = 0; i < n; i++) {
	dist[i] = INT_MAX;
	}
	dist[s] = 0;
	PQ.push(s);
	while (!PQ.empty()) {
	current = PQ.top();
	current_time = dist[current];
	PQ.pop();
	if (current_time == INT_MAX) break;
	for (it = graph[current].begin(); it != graph[current].end(); it++) {
	edge = *it;
	int t = edge_t0[edge], w;
	if (edge_P[edge] > 0) {
	w = current_time < t ? t - current_time :
	((current_time - t) % edge_P[edge] < 1 ? 0 : edge_P[edge] - ((current_time - t) % edge_P[edge]));
	}
	else {
	if (edge_t0[edge] < current_time) continue;
	else
	w = edge_t0[edge] - current_time;
	}
	new_time = current_time + edge_weight[edge] + w;
	if (new_time < dist[edge_to[edge]]) {
	dist[edge_to[edge]] = new_time;
	PQ.push(edge_to[edge]);
	}
	}
	}
	}
	int main()
	{
	FASTIO
	///*
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	n = 4;
	m = 4;
	q = 4;
	s = 0;
	for (int i = 0; i < n; i++) graph[i].clear();
	edge_from[0] = 0;
	edge_to[0] = 1;
	edge_t0[0] = 15; // when visit time start
	edge_P[0] = 10; // interval time to visit node
	edge_weight[0] = 5;
	graph[0].push_back(0);
	edge_from[1] = 1;
	edge_to[1] = 2;
	edge_t0[1] = 15; // when visit time start
	edge_P[1] = 10; // interval time to visit node
	edge_weight[1] = 5;
	graph[1].push_back(1);
	edge_from[2] = 0;
	edge_to[2] = 2;
	edge_t0[2] = 5; // when visit time start
	edge_P[2] = 5; // interval time to visit node
	edge_weight[2] = 30;
	graph[0].push_back(2);
	edge_from[3] = 3;
	edge_to[3] = 0;
	edge_t0[3] = 0; // when visit time start
	edge_P[3] = 1; // interval time to visit node
	edge_weight[3] = 1;
	graph[3].push_back(3);
	dijkstra();
	for (int i = 0; i < q; i++) {
	if (dist[i] == INT_MAX) printf("Impossible\n");
	else printf("%d\n", dist[i]);
	}
	}

view raw A_starSearch.cpp hosted with ❤ by GitHub

Share: