Dancing Links+A*正確なオーバーライド、重複オーバーライドに適用

Dancing LinksはKnuthによって提案された検索問題のクラスのための汎用的な最適化である.
あるいはDLXと呼ばれます.
主に正確なオーバーライドと重複オーバーライドに適用されます.
 
タイトルの正確な上書き:
      POJ3740、POJ3074、POJ3076、HDU4069
重複オーバーライド:
      HDU3529、HDU2295、POJ1084
 
DLXの詳細については、関連資料を参照してください.
1つの0-1行列を仮定すると、すべての列が1つ(正確なオーバーライド)しかないか、少なくとも1つ(重複オーバーライド)があるように、いくつかの行を選択する必要があります.
DLXは双方向チェーンテーブルを用いて探索を極めて最適化した.
DLXは一種のテンプレートと言える.一種類のテーマに応用する.問題モデリングを一定のフォーマットに変換すればDLXを適用できる.
正確なカバーは解数独、八皇后などに応用される.現在解数独速が最も速いのがDLXだそうです.
重複オーバーライドはレーダオーバーライドのような問題に適用される.
     
正確な上書きテンプレート:
     

void remove(const int &c)
{
	l[r[c]] = l[c];
	r[l[c]] = r[c];
	int i, j;
	for (i=d[c]; i!=c; i=d[i])
	{
		for (j=r[i]; j!=i; j=r[j])
		{
			u[d[j]] = u[j];
			d[u[j]] = d[j];
			s[ch[j]]--;
		}
	}
}

void resume(const int &c)
{
	int i, j;
	for (i=u[c]; i!=c; i=u[i])
	{
		for (j=l[i]; j!=i; j=l[j])
		{
			s[ch[j]]++;
			u[d[j]] = j;
			d[u[j]] = j;
		}
	}
	l[r[c]] = c;
	r[l[c]] = c;
}

bool dfs(const int &k)
{
	if (r[head]==head)
	{
		return true;
	}
	int ss = INT_MAX;
	int c;
	int i, j;
	for (i=r[head]; i!=head; i=r[i])
	{
		if (s[i]<ss)
		{
			ss = s[i];
			c = i;
		}
	}
	remove(c);
	for (i=d[c]; i!=c; i=d[i])
	{
		o[k] = rh[i];
		len = k;
		for (j=r[i]; j!=i; j=r[j]) remove(ch[j]);
		if (dfs(k+1)) return true;
		for (j=l[i]; j!=i; j=l[j]) resume(ch[j]);
	}
	resume(c);
	return false;
}

 
繰り返し上書きテンプレート:
 

void remove(int c)
{
    int i;
    for (i=d[c]; i!=c; i=d[i])
    {
        l[r[i]] = l[i];
        r[l[i]] = r[i];
    }
}

void resume(int c)
{
    int i;
    for (i=u[c]; i!=c; i=u[i])
    {
        l[r[i]] = r[l[i]] = i;
    }
}

int h()
{
    memset(used, false, sizeof(used));
    int c, i, j;
    int ret = 0;
    for (c=r[head]; c!=head; c=r[c])
    {
        if (!used[c])
        {
            ret++;
            used[c] = true;
            for (i=d[c]; i!=c; i=d[i])
            {
                for (j=r[i]; j!=i; j=r[j])
                {
                    used[ch[j]] = true;
                }
            }
        }
    }
    return ret;
}

void dfs(int k)
{
    if (k+h()>=len)//     
        return;
    if (r[head]==head)
    {
        len = k;
        return;
    }
    int ss = INT_MAX;
    int c, i, j;
    for (i=r[head]; i!=head; i=r[i])
    {
        if (s[i]<ss)
        {
            ss = s[i];
            c = i;
        }
    }
    for (i=d[c]; i!=c; i=d[i])
    {
        remove(i);
        for (j=r[i]; j!=i; j=r[j]) remove(j);
        dfs(k+1);
        for (j=l[i]; j!=i; j=l[j]) resume(j);
        resume(i);
    }
}

共通部分:
 

int new_node(int up, int down, int left, int right)
{
    l[size] = left;
    r[size] = right;
    u[size] = up;
    d[size] = down;
    l[right] = r[left] = u[down] = d[up] = size;
    return size++;
}

void init(int n, int m)
{
    size = 0;
    head = new_node(0, 0, 0, 0);
    len = n;
    int i;
    for (i=1; i<=m; i++)
    {
        new_node(i, i, l[head], head);
        ch[i] = i;
        s[i] = 0;
    }
    for (i=0; i<=n; i++)
        rh[i] = -1;
}

void insert_node(int i, int j)
{
    ch[size] = j;
    s[j]++;
    if (rh[i]==-1)
    {
        rh[i] = new_node(j, d[j], size, size);
    }
    else
    {
        new_node(j, d[j], rh[i], r[rh[i]]);
    }
}

DLXは一般的にモデリングが難しい.模範を立てさえすれば,すべてはやりやすい.
しかし、いくつかのテーマのモデリングプロセスは非常にわいせつです......例えばPOJ 1084......
問題:
     
POJ 3740:正確にカバーする基本テーマ.
POJ 3074、POJ 3076:数独の基本テーマ.配列を01行列に変換してDLXを行う.
HDU 4069:数独の小さな変種で、ブロックの部分が変わっただけで、影響は大きくありません.
 
HDU 3529:空白を行、障害を列とし、繰り返し上書きすればよい.
HDU 2295:NCの私は、アルファベットを1文字間違えてTLEを10回、そして精度の問題WAを3回、そしてCEを1つ、最終AC・・・二分レーダーの半径を繰り返しカバーし、レーダーを行とし、都市を列としています.
POJ 1084:超気持ち悪いテーマ.オーバーライドを繰り返します.マッチを行とし、四角を列とする.あるマッチがある四角(複数可)を支配すると、1と表記される.テーマが気持ち悪いので、四角い辺の長さは小さいから大きいまで並べなければなりません.大きいものから小さいものまで並べば、タイムアウトは言うまでもありません.この問題をするのにn日かかり、風邪を引く......