Disciplined use of the Deque #1

New Issue

glen · 2021-04-19T04:21:36Z

glen commented

2021-04-19 04:21:36 +00:00

Set up and maintain a convention that items on the deque are nodes that have been visited (i.e. plotted) but that have a list of potential children that may need to be explored.

That way, the workflow is always to grab the rightmost item on the deque, find its first (up to) N children that should be generated (N is a parameter), remove the item from the deque if that exhausts the children, plot the selected children, and push them onto the deque, each with their own list of (grand)children that need exploring.

In this workflow it will be easy to avoid having an apparent child that just goes back to the position of the parent as the first version with the deque did.

In the future, may need to add a step of clearing deque items all of whose children are now disallowed by the nodes that are actually plotted. (Only comes up if we want to try a strategy like "middle-aged search.")

Set up and maintain a convention that items on the deque are nodes that have been visited (i.e. plotted) but that have a list of potential children that may need to be explored. That way, the workflow is always to grab the rightmost item on the deque, find its first (up to) N children that should be generated (N is a parameter), remove the item from the deque if that exhausts the children, plot the selected children, and push them onto the deque, each with their own list of (grand)children that need exploring. In this workflow it will be easy to avoid having an apparent child that just goes back to the position of the parent as the first version with the deque did. In the future, may need to add a step of clearing deque items all of whose children are now disallowed by the nodes that are actually plotted. (Only comes up if we want to try a strategy like "middle-aged search.")

Sign in to join this conversation.

No Label

No Milestone

No project

No Assignees

1 Participants

Notifications

Due Date

The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: glen/polytree#1