search

aimacode / aima-java

Java implementation of algorithms from Russell And Norvig's "Artificial Intelligence - A Modern Approach"
MIT License
1.56k stars 795 forks source link

Getting QueueSize and MaxQueueSize for IterativeDeepeningSearch and DepthLimitedSearch #482

Open W2NJL opened 2 years ago

W2NJL commented 2 years ago

Hi, I've been working with the package specifically for the EightPuzzleDemo methods, including to get statistics to compare the efficiency of the various search algorithms. One thing we noticed was that IDS and DLS do not produce a QueueSize and MaxQueueSize in their respective Instrumentation metrics. I was just wondering if anyone had maybe found a way to get this information? I've tried to adapt the code from QueueSearch, but the problem is that IDS and DLS do not use the Frontier implementation, which appears to be the way the metrics are set for QueueSize.

Any insight anyone might have is sincerely appreciated!

RuedigerLunde commented 2 years ago

Hi, DLS and IDS implement a kind of DFS recursively. They do not use any queue. So, space consumption only depends on the stack size of the VM. Of course, a queue-based DFS variant could be used/implemented instead. In this case, every node should store its depth. Otherwise, the needed depth test would have a negative impact on time complexity. To add such an implementation to the existing library, one could create an own NodeFactory by subclassing the existing one and use an own node class with an additional attribute depth.

Best regards, Rüdiger