我被分配了以下任务：给定一个5×5版本的游戏，所有灯都亮着，使用UCS / A* / BFS / Greedy best first search算法编写一个找到解决方案的算法。
我首先意识到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; }}附注：由于我不再使用map（切换到数组）来记录已访问的状态，我的DFS解决方案从123秒改善到54秒，但BFS仍然会崩溃。
回答：
首先，你可能已经认识到，在《Lights Out》游戏中，你永远不需要翻转同一个开关超过一次，而且翻转开关的顺序并不重要。因此，你可以用两种不同的方式来描述当前状态：要么是哪些灯亮着，要么是哪些开关已经被翻转。后者，连同灯的初始模式，可以给你前者。
为了使用图搜索算法解决这个问题，你需要一个邻接的概念。这从第二种描述中更容易得出：如果两个状态只在一个开关上有所不同，那么它们就是邻接的。这种描述还直接编码了到每个节点的路径长度（=已翻转的开关数量），并且减少了需要为每个考虑的状态考虑的后续移动数量，因为所有可能的路径到每个节点都被编码在开关的模式中。
你可以相对容易地在广度优先搜索中使用这种方法（这可能是你实际上尝试过的）。在这种情况下，BFS相当于Dijkstra算法，即使不使用显式的优先级队列，因为你按优先级（路径长度）顺序排队新的节点以供探索。
你也可以通过添加合适的启发式方法将其转换为A*搜索。例如，由于每次移动最多关闭五盏灯，可以将每次移动后仍亮着的灯的数量除以5作为启发式方法。虽然这有点粗糙，但我倾向于认为这会有所帮助。然而，你确实需要一个真正的优先级队列来实现这种替代方案。
就实现而言，请认识到你可以将当前亮着的灯的模式和已按下的开关的模式表示为位向量。每个模式都适合在一个32位整数中，而访问状态列表需要225位，这在现代计算系统的容量范围内。即使你使用同样多的字节，你也应该能够处理它。此外，你可以使用位运算操作符，特别是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)，m是队列中元素的数量。A*和BFS的队列大小最坏情况上限都是O(n)，n是总状态数。因此，BFS在问题规模上比A*扩展得更好；唯一的问题是前者是否可靠地给你正确答案，在这种情况下，它确实可以。
