解决 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。由于我不再使用地图（切换到数组）访问状态，我的 DFS 解决方案从 123 秒改进到 54 秒但 BFS 仍然崩溃。

Answer 1

首先，您可能已经认识到，在 Lights Out 中，您永远不必多次拨动同一个开关，而且拨动顺序无关紧要开关。因此，您可以用两种不同的方式描述当前状态：根据哪些灯亮着，或者根据哪些开关已打开。后者与灯光的起始模式一起为您提供前者。

要使用图形搜索算法来解决问题，您需要邻接的概念。从第二个特征中更容易得出这一点：如果两个状态恰好有一个开关不同，则它们是相邻的。该特征还直接编码到每个节点的路径长度（= 已翻转的开关数），并且它减少了需要为每个考虑的状态考虑的后续移动的数量，因为到每个节点的所有可能路径以开关模式编码。

您可以相对轻松地在广度优先搜索中使用它（这可能是您实际尝试过的）。在这种情况下，BFS 等同于 Dijkstra 算法，即使不使用显式优先级队列，因为您按优先级（路径长度）顺序排列新节点以进行探索。

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

就实现而言，请认识到您可以将当前点亮的灯的模式和已按下的开关模式表示为位向量。每个模式适合一个 32 位整数，访问状态列表需要 2²⁵ 位，这完全在现代计算系统的能力范围内。即使你使用那么多字节，你也应该能够处理它。此外，您可以使用按位算术运算符执行所有需要的运算，尤其是 XOR。因此，这个问题（在给定的规模下）应该可以相对快速地计算出来。

更新：

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

我用一个 uint64_t 来表示整个系统的每个状态。前 32 位包含一个位掩码，其中开关已被翻转，而后 32 位包含一个位掩码，其结果是灯亮了。我将它们与指向 link 的单个指针一起包装在 struct 中，将它们一起作为队列的元素。一个给定的状态可以作为一个按位与运算和一个整数比较的解决方案来测试。
我创建了一个包含 25 个 uint64_t 位掩码的预初始化数组，代表每一步的效果。每个顶部 32 位中设置的一位表示翻转的开关，底部 32 位中设置的 3 到 5 位之间的位表示因此切换的灯。按下一个开关的效果可以简单地计算为 new_state = old_state ^ move[i].
我实现了 plain 广度优先搜索而不是 A*，部分原因是我试图快速组合一些东西，特别是因为那样我可以使用常规队列而不是优先队列。
我构建我的 BFS 的方式自然地避免访问相同的状态两次，而不必实际跟踪哪些状态曾经被排队。这是基于对如何在不重复的情况下有效地生成不同的位模式的一些见解，在那些具有更多位设置的模式之前生成更少的位模式。 BFS 无论如何都需要基于队列的方法来相当自然地满足后一个标准。
我使用第二个（普通）队列来回收从主队列中删除的动态分配的队列节点，以最大限度地减少对 malloc().[=18= 的调用次数]

整体代码略少于 200 行，包括空白行和注释行、数据类型声明、I/O、队列实现（纯 C，无 STL）——一切。

请注意，顺便说一句，标准 Dijkstra 和 A* 中使用的优先级队列主要是关于 找到正确答案（最短路径），其次才是做如此高效。标准队列的入队和出队都可以是 O(1)，而优先级队列上的那些操作在队列中的元素数量上是 o(log m)。 A* 和 BFS 在状态总数中都有 O(n) 的最坏情况队列大小上限。因此，BFS 在问题规模方面比 A* 更好；唯一的问题是前者是否可靠地为您提供了正确的答案，在这种情况下，确实如此。

解决 AI 课程的熄灯问题

Solving Lights out for AI Course

artificial-intelligence

dijkstra

depth-first-search

a-star