A星アルゴリズムとIDA星アルゴリズム

この2つのアルゴリズムは、DLXが見た検索に最も適したアルゴリズムである.A*を広捜の進化と見なし,IDAstarをA*の時間的空間形式と見なすことができる.
まずA*アルゴリズムについて議論する.実は彼は広捜に似ていると思いますが、次のような要素があります.
1.評価関数f=g+hは、初期状態から現在状態までの距離と現在状態から目標状態までの推定距離をそれぞれ表すgとhの2つの部分から構成される.
2.最適ノードを拡張するたびに.すなわち、すべての拡張ノードから評価関数の値が最も小さいノードを選択するたびに拡張されます.
3.評価関数におけるh<=h*は、推定距離が最適距離より大きくなければならない.これは重要な点です.これはA*アルゴリズムがAアルゴリズムと同じかどうか、そして検索された結果が最適解であるかどうかに直接関係します.
どのように実現しますか?まず、条件1と3を満たす評価関数の計算式を設計する必要があります.また、hの値が大きいほど(h*以下を満たす場合)、検索が速くなる.広検索では、h関数を0と見なすことができるので、広検索が最もゴミのA*アルゴリズムともいえる.なお、条件2を満たすためには、毎回最適なノード拡張を素早く取り出す必要がある.スタックが最適であることは間違いない.
このように,A*アルゴリズムは,広探索にh<=h*の評価関数を加え,キューを優先キュー(スタック)に置き換える.
IDA*について議論します.まず、反復と深い検索とは何かを知る必要があります.
ある时、1つの局面は多くの层を検索することができて、このように普通の深さはきっと挂かります.どうしようかな?検索深度が制限されている場合は、現在の検索の深度を毎回制限し、各深度を検索できます.
時間を無駄にしているように聞こえ、ほとんど毎回元の検索状態を繰り返します.しかし、これには、最適解が必要であれば、すべての状態(深さ検索)を拡張することを避けることができ、最適解を得ることができるという明らかな利点がある.
じゃ、どうして広く探さないのですか.明らかに、いくつかの検索では、20層を超えるのに必要な空間が512 Mを爆発させることができる.反復と深さの検索は時間でこの不足を補った.だから、彼は広捜査と深捜査の間にあるアルゴリズムです.
では、IDA*とは何でしょうか.明らかに,A*アルゴリズムにおける評価関数との反復を加えて深く検索する.評価関数をどのように利用しますか?明らかに、評価関数の現在の制限を超えない深さです.h<=h*であるため,結果の最適化は絶対的に保証できる.
このようにIDA*アルゴリズムは,反復深さ探索に加えてh<=h*の評価関数を加え,制限された深さ限界値で評価関数を用いる.
では、彼らの効率はどうでしょうか.15デジタル問題で議論してもいいです.
まず時間効率です.テスト結果によると、A*>=双方向広捜>=IDA*(実は双方向広捜とは差が少ない)>=広捜(>=深捜ですが、誰も書いていません).
さらに空間効率です.IDA*は、他のすべての実行可能なアルゴリズムよりもはるかに優れていることは明らかです.
評価結果は以下の通りである:前後して広捜、IDA*、A*(A*の後ろの間違いは空間が詰まっているため)
以下に、A*とIDA*のコードをそれぞれ入力します.

#include 
#include 
#include 
#include 
#include 
#include 

typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define swap(a, b, t) ({t _ = (a); (a) = (b); (b) = _;})
#define MAX(a, b, t) ({t _ = (a), __ = (b); _ > __ ? _ : __;})
#define MIN(a, b, t) ({t _ = (a), __ = (b); _ < __ ? _ : __;})

typedef int maintype;
#define max(a, b) MAX(a, b, maintype)
#define min(a, b) MIN(a, b, maintype)

#define maxs 18
#define maxn 200005
#define abs(a) ({int _ = a; _ < 0 ? - _ : _;})
#define opt(a) (a[maxs - 1])
#define data(u) ((u)->f + (u)->g)

const int ppp[maxs] = {1, 2, 6, 24, 120, 720, 5040, 40320, 
    362880, 3628800, 39916800, 479001600, 227020758, 
    1178290605, 1674359019, 789744213, 1073741823};

typedef int gate[maxs];
gate a, b, c, d;
int cost[maxs][maxs], hash[maxn];
int n, m, dis, top, tot, p, q, f, g, temp, ha;
struct node{gate a; node * pre; int f, g;};
node vess[maxn], * h[maxn], * u, * v;

void up(int p)
{
    for (; (p >> 1) and data(h[p]) < data(h[p >> 1]); p >>= 1)
        swap(h[p], h[p >> 1], node *);
}

void down(int p)
{
    while ((p << 1) <= tot)
        if ((p << 1) == tot)
        {
            if (data(h[p << 1]) < data(h[p]))
                swap(h[p << 1], h[p], node *);
            break;
        }
        else
        {
            int q = data(h[p << 1]) < data(h[p << 1 | 1]) ? (p << 1) : (p << 1 | 1);
            if (data(h[q]) < data(h[p])) swap(h[q], h[p], node *), p = q; else break;
        }
}

node * pop()
{
    node * p = h[1];
    return h[1] = h[tot --], down(1), p;
}

void push(gate a, node * pre, int f, int g)
{
    h[++ tot] = vess + ++ top;
    memcpy(h[tot]->a, a, sizeof (gate));
    h[tot]->pre = pre, h[tot]->f = f, h[tot]->g = g, up(tot);
}

int cantor(gate a)
{
    int k = 0;
    for (int i = m; i; -- i)
        k += a[i] * ppp[i];
    return (k & 0xFFFFFFF) % maxn;
}

void printans(node * u)
{
    if (opt(u->pre->a)) printans(u->pre);
    printf("%d
", opt(u->a));
}

void work()
{
    for (int i = m; i; -- i)
        if (a[i]) dis += cost[i][c[a[i]]];
    hash[cantor(a)] = dis;
    for (push(a, 0, dis, 0); top + 5 < maxn; )
    {
        u = pop(), p = u->a[0], g = u->g + 1;
        for (int i = 1; i <= 4; ++ i)
        {
            if ((q = p + d[i]) < 1 or q > m or cost[p][q] != 1) continue;
            f = u->f - cost[q][c[u->a[q]]] + cost[p][c[u->a[q]]];
            if (g + f > 30) continue;
            if (f == 0)
            {
                printf("%d
", g);
                printans(u), printf("%d
", i);
                exit(0);
            }
            swap(u->a[p], u->a[q], int);
            if (hash[ha = cantor(u->a)])
                if (hash[ha] < f) continue; else;
            else hash[ha] = f;
            u->a[0] = q, temp = opt(u->a), opt(u->a) = i;
            push(u->a, u, f, g);
            u->a[0] = p, opt(u->a) = temp;
            swap(u->a[p], u->a[q], int);
        }
    }
    puts("No");
}

void init()
{
    scanf("%d", & n), m = n * n;
    d[1] = - n, d[2] = n, d[3] = - 1, d[4] = 1;
    for (int i = 1; i <= m; ++ i)
    {
		scanf("%d", & a[i]);
        if (a[i] == 0) a[0] = i;
    }
    for (int i = 1; i <= m; ++ i)
		scanf("%d", & b[i]), c[b[i]] = i;
	for (int i = m; i; -- i)
		for (int j = m; j; -- j)
		{
			cost[i][j] += abs((i - 1) / n - (j - 1) / n);
			cost[i][j] += abs((i - 1) % n - (j - 1) % n);
		}
}

int main()
{
    freopen("gate.in", "r", stdin);
    freopen("gate.out", "w", stdout);
    
    init();
    work();
    
    return 0;
}

#include 
#include 
#include 
#include 
#include 
#include 

typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define swap(a, b, t) ({t _ = (a); (a) = (b); (b) = _;})
#define MAX(a, b, t) ({t _ = (a), __ = (b); _ > __ ? _ : __;})
#define MIN(a, b, t) ({t _ = (a), __ = (b); _ < __ ? _ : __;})

typedef int MAINTYPE;
#define max(a, b) MAX(a, b, MAINTYPE)
#define min(a, b) MIN(a, b, MAINTYPE)

#define maxs 18
#define maxd 30

typedef int gate[maxs];
gate a, b, c, d;
int n, m, dis, cost[maxs][maxs];
int now, temp, opt[maxd + 5];

void printans(int i, int g)
{
	printf("%d
", now);
	for (int j = 1; j < g; ++ j)
		printf("%d
", opt[j]);
	printf("%d
", i);
	exit(0);
}

void dfs(int g, int h, int p)
{
	for (int i = 1, q; i <= 4; ++ i)
	{
		if ((q = p + d[i]) < 1 or q > m or cost[p][q] != 1) continue;
		int gg = g + 1, hh = h - cost[q][c[a[q]]] + cost[p][c[a[q]]];
		if (gg + hh > now) continue;
		if (hh == 0) printans(i, gg);
		swap(a[p], a[q], int);
		opt[gg] = i, dfs(gg, hh, q);
		swap(a[p], a[q], int);
	}
}

void work()
{
	for (int i = 1; i <= m; ++ i)
		if (a[i]) dis += cost[i][c[a[i]]];
	for (now = 1; now <= maxd; ++ now)
		dfs(0, dis, a[0]);
	puts("No");
}

void init()
{
	scanf("%d", & n), m = n * n;
	d[1] = - n, d[2] = n, d[3] = - 1, d[4] = 1;
	for (int i = 1; i <= m; ++ i)
		scanf("%d", & a[i]), a[0] = a[i] ? a[0] : i;
	for (int i = 1; i <= m; ++ i)
		scanf("%d", & b[i]), c[b[i]] = i;
	for (int i = 1; i <= m; ++ i)
		for (int j = 1; j <= m; ++ j)
			cost[i][j] = abs((i - 1) / n - (j - 1) / n) + abs((i - 1) % n - (j - 1) % n);
}

int main()
{
    freopen("gate.in", "r", stdin);
    freopen("gate.out", "w", stdout);
    
    init();
	work();
    
    return 0;
}

から分かるように、コード量と効率の比では、IDA*の性価比がかなり高い.