BFS is equivalent to Dijkstra's algorithm in that case, even without using an explicit priority queue, because you enqueue new nodes to explore in priority (path-length) order. You could use that in a breadth-first search relatively easily (and this may be what you in fact tried). That characterization also directly encodes the length of the path to each node (= the number of switches that have been flipped), and it reduces the number of subsequent moves that need to be considered for each state considered, since all possible paths to each node are encoded in the pattern of switches. That follows more easily from the second characterization: two states are adjacent if there is exactly one switch about which they they differ. To employ a graph-search algorithm to solve the problem, you need a notion of adjacency. The latter, together with the starting pattern of lights, gives you the former.
You can thus describe the current state in two distinct ways: either in terms of which lights are on, or in terms of which switches have been flipped. As I am not using map anymore(switched to array) for visited states, my DFS solution improved from 123 secs to 54 secs but BFS still crashes.įirst of all, you may already recognize that in Lights Out you never have to flip the same switch more than once, and it doesn't matter in which order you flip the switches. Struct state* next = MakeNextState(temp, i) Int bijection_mapping(struct state* temp) Struct state* noviCvor = new struct state() įor(int i = 0 i board = temp->board, noviCvor->clicked = temp->clicked įor(int k = 0 k = 0 & temp_pos board = !noviCvor->board Struct state* MakeNextState(struct state* temp, int press_pos) Int visited = false, noviCvor->clicked = false Here is my source code(I think it's pretty straightforward to follow): struct state Looking forward to some help from you guys What I am wondering now is am I missing something? Is there some good heuristics to try to solve this problem using A* search? I figured out absolutely nothing when it's about heuristics, because it doesn't seem any trivial to find one in this problem. Next, what I did is write DFS(even though it was not mentioned as one of possibilities) and it did find a solution in 123 secs, at depth 15(I used depth-first limited because I knew that there was a solution at depth 15). It would work for around 5-6mins and then crash because of memory. It turned out that it works too long and fills up a queue, even though I was paying attention to removing parent nodes when I was finished with them not to overflow the memory. What I did first was realize that UCS would be unnecessary as the cost from moving from one state to another is 1(pressing a button that flips itself and neighbouring ones).
So I was given the following task: Given that all lights in a 5x5 version of a game are turned on, write an algorithm using UCS / A* / BFS / Greedy best first search that finds a solution.
0 kommentar(er)
