为AI课程解决灯光问题

Question

因此我得到了以下任务:假设打开5x5版游戏中的所有灯光,请使用UCS/A*/BFS/Greedy最佳搜索找到解决方案的算法.

我先做的是意识到UCS是不必要的,因为从一个状态移动到另一个状态的成本是1(按下一个翻转自己和相邻状态的按钮).所以我所做的就是用BFS写的.事实证明,它工作得太长并且填满了一个队列,即使我在完成它们时不注意去除父节点而不是溢出内存.它会工作大约5-6分钟然后因内存而崩溃.接下来,我所做的就是编写DFS(尽管它没有被提及作为可能性之一)并且它确实在123秒内找到了解决方案,深度为15(我使用深度优先限制,因为我知道深度有一个解决方案15).

我现在想知道的是我错过了什么吗？使用A*搜索尝试解决此问题是否有一些良好的启发式方法？当它是关于启发式的时候我完全没有想到,因为在这个问题中找到一个似乎并不重要.

非常感谢.期待你们的帮助

这是我的源代码(我认为它非常简单易懂):

struct state
{
    bool board[25];
    bool clicked[25];
    int cost;
    int h;
    struct state* from;
};

int visited[1<<25];
int dx[5] = {0, 5, -5};
int MAX_DEPTH = 1<<30;
bool found=false;

struct state* MakeStartState()
{
    struct state* noviCvor = new struct state();

    for(int i = 0; i < 25; i++) noviCvor->board[i] = false, noviCvor->clicked[i] = false;
    noviCvor->cost = 0;
    //h=...
    noviCvor->from = NULL;

    return noviCvor;
};

struct state* MakeNextState(struct state* temp, int press_pos)
{
    struct state* noviCvor = new struct state();

    for(int i = 0; i < 25; i++) noviCvor->board[i] = temp->board[i], noviCvor->clicked[i] = temp->clicked[i];
    noviCvor->clicked[press_pos] = true;

    noviCvor->cost = temp->cost + 1;
    //h=...
    noviCvor->from = temp;

    int temp_pos;

    for(int k = 0; k < 3; k++)
    {
        temp_pos = press_pos + dx[k];

        if(temp_pos >= 0 && temp_pos < 25)
        {
            noviCvor->board[temp_pos] = !noviCvor->board[temp_pos];
        }
    }

    if( ((press_pos+1) % 5 != 0) && (press_pos+1) < 25 )
        noviCvor->board[press_pos+1] = !noviCvor->board[press_pos+1];

    if( (press_pos % 5 != 0) && (press_pos-1) >= 0 )
        noviCvor->board[press_pos-1] = !noviCvor->board[press_pos-1];

    return noviCvor;
};

bool CheckFinalState(struct state* temp)
{
    for(int i = 0; i < 25; i++)
    {
        if(!temp->board[i]) return false;
    }

    return true;
}

int bijection_mapping(struct state* temp)
{
    int temp_pow = 1;
    int mapping = 0;

    for(int i = 0; i < 25; i++)
    {
        if(temp->board[i])
            mapping+=temp_pow;

        temp_pow*=2;
    }

    return mapping;
}

void BFS()
{
    queue<struct state*> Q;

    struct state* start = MakeStartState();
    Q.push(start);
    struct state* temp;
    visited[ bijection_mapping(start) ] = 1;

    while(!Q.empty())
    {
        temp = Q.front();
        Q.pop();
        visited[ bijection_mapping(temp) ] = 2;

        for(int i = 0; i < 25; i++)
        {
            if(!temp->clicked[i])
            {
                struct state* next = MakeNextState(temp, i);
                int mapa = bijection_mapping(next);

                if(visited[ mapa ] == 0)
                {
                    if(CheckFinalState(next))
                    {
                        printf("NADJENO RESENJE\n");
                        exit(0);
                    }
                    visited[ mapa ] = 1;
                    Q.push(next);
                }
            }
        }

        delete temp;
    }
}

PS.由于我不再使用map(切换到数组)来访问状态,我的DFS解决方案从123秒提高到54秒,但BFS仍然崩溃.

Answer 1

首先,您可能已经认识到在Lights Out中您不必多次翻转同一个开关,并且无论您翻转开关的顺序都无关紧要.因此,您可以通过两种不同的方式描述当前状态:根据哪些灯打开,或者根据哪些开关被翻转.后者与灯光的起始模式一起为您提供前者.

要使用图搜索算法来解决问题,您需要一个邻接的概念.从第二个特征可以更容易地得出结论:如果只有一个开关,则两个状态相邻,它们不同.该特征还直接编码到每个节点的路径长度(=已翻转的交换机的数量),并且它减少了考虑的每个状态需要考虑的后续移动的数量,因为到每个节点的所有可能路径以开关模式编码.

您可以相对容易地在广度优先搜索中使用它(这可能是您实际上尝试过的).在这种情况下,即使不使用显式优先级队列,BFS也相当于Dijkstra的算法,因为您将新节点排入队列以按优先级(路径长度)顺序进行探索.

您还可以通过添加合适的启发式将其转换为A*搜索.例如,由于每次移动最多关闭五个灯光,因此可以将每次移动后仍然亮起的灯数作为启发式除以5.虽然这有点粗糙,但我倾向于认为它会是一些帮助.但是,您确实需要一个真正的优先级队列.

就实现而言,要认识到您既可以表示当前打开的灯光模式,也可以表示已按下位矢量的开关模式.每个模式都适合32位整数,访问状态列表需要2 ²⁵位,这完全在现代计算系统的容量范围内.即使您使用那么多字节,您也应该能够处理它.此外,您可以使用按位算术运算符执行所有需要的操作,尤其是XOR.因此,这个问题(在给定的大小)应该可以相对快速地计算.

更新:

正如我在评论中提到的,我决定为自己解决这个问题 - 在我看来 - 非常成功.我使用各种技术来实现良好的性能并最​​大限度地减少内存使用,在这种情况下,这些技术大多是互补的.以下是我的一些技巧:

• 我用一个单独表示每个整个系统状态uint64_t.前32位包含一个位掩码,其中的开关已被翻转,而底部32包含一个位于其中的灯亮的位掩码.我将它们struct与一个指针一起包装在一起,将它们作为队列的元素链接在一起.可以将给定状态作为具有一个按位和操作以及一个整数比较的解决方案进行测试.

• 我创建了一个预先初始化的25位uint64_t掩码数组,表示每次移动的效果.在每个顶部32中的一个位设置表示被翻转的开关,并且在底部32中设置的3到5位之间表示作为结果切换的灯.然后可以简单地计算翻转一个开关的效果new_state = old_state ^ move[i].

• 我实现了普通的广度优先搜索而不是A*,部分原因是因为我试图快速将某些东西放在一起,特别是因为这样我可以使用常规队列而不是优先级队列.

• 我以一种自然避免两次访问同一州的方式构建我的BFS,而不必实际跟踪哪些州曾经入队过.这是基于对如何有效地生成不同的位模式而不重复的一些见解,其中那些在具有更多位设置之前生成的比特集更少.无论如何,BFS所需的基于队列的方法很自然地满足了后一个标准.

• 在从主队列中删除动态分配的队列节点后,我使用了第二个(普通)队列来回收动态分配的队列节点,以最大限度地减少对号码的调用malloc().

整体代码少于200行,包括空行和注释行,数据类型声明,I/O,队列实现(普通C,无STL) - 一切.

顺便提一下,请注意,标准Dijkstra和A*中使用的优先级队列主要是寻找正确的答案(最短路径),其次才是有效地做到这一点.从标准队列入队和出队都可以O(1),而优先级队列上的那些操作在队列中o(log m)的元素数量中.A*和BFS都具有O(n)状态总数的最坏情况队列大小上限.因此,BFS在问题规模上将比A*更好地扩展; 唯一的问题是前者是否可靠地给你正确答案,在这种情况下,它确实如此.