1
$\begingroup$

As part of an assignment for an AI class that I'm taking, I'm need to solve a puzzle on a 4x4 grid using breadth-first search (each element can take on 12 different values). There is a maximum of 4 moves for each state. Needless to say, after 30-or-so moves, the number of nodes (each representing a state) in the queue gets too large for most (any?) computer to handle, since many nodes are duplicates.

The solution, as far as I know, is to add all visited nodes to a "visited list." This makes it possible to compute without running out of memory, but it takes forever. Why? Because for each node that I add, I have to make sure that it's not in the list of visited nodes. For a somewhat complex puzzle, this list can get really long. Let's say the list gets to 500000 nodes, which is feasible. That means that for every new node I add to the queue, it needs to be compared to 500000 nodes to make sure that it isn't identical to any node in that list. This takes a really long time to compute. It solves the problem, but I'm pretty sure I have the wrong idea about how to approach this to actually make it efficient.

I know BFS usually isn't a very good approach to these kinds of problems, but it's part of the assignment. It's only about actually solving the puzzle, but I'm interested in knowing if there is a way to make it more efficient. In general, I mean. I'm sure that I could tailor the program to make it solve this specific puzzle much faster, but what I want to know if there's some idea that could be applied to all problems.

Any help is greatly appreciated!

$\endgroup$
2
$\begingroup$

Use a hash table to store the visited list. Searching the list should take $O(1)$.

$\endgroup$
  • $\begingroup$ Wow, that's so obvious now that you mention it. I can't believe I didn't think of that (I also can't believe I misspelled "visited" three times...). Thanks a lot. Very much appreciated.. $\endgroup$ – Lobs001 Sep 23 '17 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.