Timeline for A way to leverage machine learning to reduce DFS/BFS search time on a tree graph?
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2021 at 5:57 | comment | added | JungleBird | I also edited my post to include a better picture of a graph I'd be dealing with. Each branch represents a cluster/sub-cluster. And it would reduce my search time exponentially if I could just "prune" the first few major branches and contain my DFS/BFS in a sub-cluster. The best way to do that would be keep some memory about where previous nodes ended up. At first the associations would be weak but grow stronger with more nodes being placed, and stronger associations would translate to greater confidence in which path a node should take. | |
| Jan 6, 2021 at 5:31 | comment | added | JungleBird | Thank you guys for answering my question! I didn't know that kind of search algorithm was called the A* search algorithm. But nbro has a point since it seems like the A* algorithm requires a destination to work towards. This problem is a real head-scratcher because the data isn't discrete; it's like drawing lines in the sand to mark how far the waves reach into the beach. Using a heuristic has it's merits but it breaks down when that heuristic comes down to a razor's margin at a fork in the road. | |
| Jan 5, 2021 at 16:27 | comment | added | nbro | In any case, I'm still not sure whether A* is the right tool to solve OP's problem. Maybe you should try to explain more in detail how A* should be applied in the OP's case. | |
| Jan 5, 2021 at 16:22 | comment | added | nbro | The reason why I think "prune" may not be the most appropriate term here is that, if there's no goal and the graph is finite, for instance, A* should explore all nodes, so, in that case, it doesn't prune anything. However, you're right that it may not visit certain parts of the search space if all paths that lead to the goal from a start node have already been explored, so, in those cases, we can think of certain parts of the search space being pruned. So, I was a bit imprecise in my previous comment, so your description was right (but not applicable in all cases). | |
| Jan 5, 2021 at 16:17 | comment | added | Alina Barnett | I would say that within the search space branches are "pruned" if they are never explored. Is there other terminology for that you would look for? | |
| Jan 5, 2021 at 16:16 | history | edited | Alina Barnett | CC BY-SA 4.0 |
added 55 characters in body
|
| Jan 5, 2021 at 3:24 | history | edited | Alina Barnett | CC BY-SA 4.0 |
added 26 characters in body
|
| Jan 4, 2021 at 21:57 | comment | added | nbro | A* does not really prune branches, but it explores branches according to the admissible heuristic, so, more intuitively, we could say that it explores branches based on how promising they are, but it doesn't really discard any branch. I'm not sure if A* is really the solution the problem. | |
| Jan 4, 2021 at 20:19 | history | answered | Alina Barnett | CC BY-SA 4.0 |