A*: open and close lists in Rust
I'm learning Rust and I have troubles figuring out what structure I should use for a N-Puzzle solver using A*.
In this project I use a tree to compute and choose the best way to solve a N-Puzzle. A typical tree looks like this :
The number in each node is the computed f score, it represents the minimum number of move we can hope to do before getting to the final state.
Grey nodes are already explored nodes, they are in the "close set".
Green nodes are potential steps to the solution, it's the "open set".
At each iteration we explore the green node with the lowest f score. To optimise the search of this node in the open set, I need to store a mutable reference of all the green nodes in a vector/list/array..
What is the best way to have both a tree and a list of the same mutable nodes ?
Please notice that I would like to use multiple threads later.
After some research about interior mutability, threads and a few other things for the project, I found a more elegant solution.
The goal of the algorithm is to compute childs until you find the target, then you go back all your graph by a system of parents and track all the moves you did from the beginning. I found a way to do it without having a graph representation but only openlist and closelist. No need for multiple mutable references in this case. If, in each child, you store the index of its parent in the close list, which won't change, you can go back to beginning without mutability.
The answer I asked is not solving my problem, I did research on the algorithm again and did everything again. Anyway, thank you for your answers, I learned new things about Rust.