Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ParallelIDAStar does not mimic IDA* expanded and generated nodes at the last layer #74

Open
lior8 opened this issue Dec 16, 2023 · 0 comments

Comments

@lior8
Copy link
Contributor

lior8 commented Dec 16, 2023

The current version of ParallelIDAStar attempts to mimic the work done by IDA* but get the speedup of parallelization. That is evident in the termination condition which was explored a bit in PR #73.
For all layers except the last, the generated and expanded will be the same as both algorithms expand all of the nodes. But, in the last layer, they will probably expand less than all of them as a solution is found.
When looking at the way that the number of nodes expanded/generated (link), all the nodes that were expanded in the last layer are added, even those that were done by threads which are expanding nodes that would have not been reached by IDA*.
Now, these are indeed generated and expanded nodes that should be accounted for, but it might create a difference in results when trying to only get a speedup and not change the behavior of IDA*.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant