I'm looking to streamline the comparison of single paths within a decision tree using a JavaScript function.
Currently, I can only compare nodes by adding them up, which limits my ability to analyze individual paths. Instead, I want to focus on one path at a time and then move on to the next one for comparison.
For instance, let's consider the following scenario: the next decision should fall within a range of -3, with the numbers provided as [9, 8, 6, 5, 3, 2, 0]. The sum of the list represents the value, and the target is to find the path with a length of 6 containing the highest value.
2 - 0
3 <
5< 0
/ 2 - 0
6
/ \ 2 - 0
3<
0
8 2 - 0
\ 3<
/ 5 < 0
2 - 0
9 2 - 0
3 <
5< 0
\ / 2 - 0
6
\ 2 - 0
3<
0
The paths to be compared are:
[9,6,3,0],
[9,6,3,2,0],
[9,6,5,2,0],
[9,6,5,3,0],
[9,6,5,3,2,0],
[9,8,6,3,0],
[9,8,6,3,2,0],
[9,8,6,5,2,0],
[9,8,6,5,3,0],
[9,8,6,5,3,2,0],
Is there a way to efficiently compare only two paths at a time instead of evaluating all paths simultaneously?
Edit 1 :
Here is the code I have so far:
const numbers = [9, 8, 6, 5, 3, 2, 0];
const starting_node = Math.max(...numbers) + 3;
const path = (current_node, memo ={}) => {
if (current_node in memo) return memo[current_node];
if (current_node == 0) return [[]];
let paths = [];
let tmp_nodes = [];
for (n of numbers) {
if (n >= current_node - 3 && n < current_node) {
tmp_nodes.push(n);
}
}
for (let tmp of tmp_nodes) {
const tmp_path = path(tmp);
const tmp_paths = tmp_path.map(way => [tmp, ...way]);
paths.push(...tmp_paths);
}
memo[current_node] = paths;
paths = paths.filter(x => x.length <= 6);
return paths;
};
const bestPath = all_paths => {
all_paths = all_paths.filter(x => (x.length = 6));
let bestValue = 0;
let bestPath = null;
for (let path of all_paths) {
let value = 0;
for (node of path) value += node;
if (value > bestValue) {
bestValue = value;
bestPath = path;
}
}
return bestPath;
};
const path_array = path(starting_node);
console.log(bestPath(path_array));
This code works well, but it runs into a stack overflow error when dealing with a large amount of data (e.g., over a thousand numbers). In reality, the range is -360 instead of -3.
Main Issue: Too much data causing performance issues
Potential Solution: Implement a method to compare only two paths at once during the calculation process
Question: What approaches can be used to compute only two paths for comparison at a time?