算法提高课汇总

算法思路

$IDA^*$

对于错误分支, 可能出现$ABFE\;ABFE…$的情况, 每4次操作状态回到原点 — 错误分支的深度
可能会很深.

为避免在错误分支消耗太多时间, 考虑用$IDA^*$求解.

估价函数

我们将注意力放在中间的8个格子上, 观察每次操作: 将一个数字移出, 将另一个数字加入. 最好情况
是每次都加入当前最多的数字, 加上当前数目最多的数字有$cnt$个, 则当前状态$u$到最终状态至少要走
$f(u) = 8 - cnt$.

具体实现

字典序最小

题目要求方案字典序最小 — 每层分支均按移动的字典序顺序枚举. 也就是搜索树同层左侧对应方案字典序
比右侧小. 具体可以用反证法证明.

优化

每次枚举可以加入一个优化: 当前移动不会选择与上一次移动相反的方向, 否则就是在做无用功.

打表

由于题目状态对应图形比较复杂, 可以把每个操作数字对应的下标硬编码hard code存储在数组中.

实现代码

/*
 *           A0   B1
 *
 *           0     1
 *           2     3
 *H7   4  5  6  7  8  9  10   C2
 *           11    12
 *G6   13 14 15 16 17 18 19   D3
 *           20    21
 *           22    23
 *
 *           F5    E4
 *
 */
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 24;

int n;
int q[N];   
int path[100]; //存储选择方案

int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},  //A0    
    {1, 3, 8, 12, 17, 21, 23},  //B1 
    {10, 9, 8, 7, 6, 5, 4},    
    {19, 18, 17, 16, 15, 14, 13},    
    {23, 21, 17, 12, 8, 3, 1},    
    {22, 20, 15, 11, 6, 2, 0},    
    {13, 14, 15, 16, 17, 18, 19},    
    {4, 5, 6, 7, 8, 9, 10},     //H7    
};
int opposite[] = {5, 4, 7, 6, 1, 0, 3, 2};  //每个步骤对应相反步骤的下标
int center[]   = {6, 7, 8, 11, 12, 15, 16, 17}; //中间8个位置

int f()
{
    int sum[4] = {0}; //sum[i]: 数字i在中间8个数字中出现的次数
    for ( int i = 0; i < 8; i ++ )  sum[ q[center[i]] ] ++ ;
    int s = 0;
    for ( int i = 1; i <= 3; i ++ ) s = max(s, sum[i]);
    return 8 - s;
}

void operate(int i)
{
    int *OP = op[i]; //操作下标
    int t = q[ OP[0] ];
    for ( int i = 0; i < 6; i ++ )
        q[ OP[i] ]   = q[ OP[i + 1] ];
    q[ OP[6] ]   = t;
}

//last: 上一步操作对应下标
bool dfs(int u, int depth, int last)
{
    if ( u + f() > depth )  return false;
    if ( !f() )     return true;

    for ( int i = 0; i < 8; i ++ ) //按字典序枚举8个步骤
    {
        if ( opposite[i] != last )
        {
            operate(i);
            path[u] = i;
            if ( dfs(u + 1, depth, i) )     return true;
            //path[u] = 
            operate(opposite[i]); //恢复现场
        }
    }
    return false;
}

int main()
{
    while ( cin >> q[0], q[0] )
    {
        for ( int i = 1; i < N; i ++ )  cin >> q[i];

        int depth = 0;
        while ( !dfs(0, depth, -1) )    depth ++ ;
        if ( !depth )   printf("No moves needed");
        else
        {
            for ( int i = 0; i < depth; i ++ )  printf("%c", path[i] + 'A');
        }
        printf("\n%d\n", q[6]);
    }
    return 0;
}