User Tools

Site Tools


λ Iterative deepening depth-first search

======= Algorithm ======= <syntax js> function iterativeDeepeningDepthFirstSearch(node) { // Repeatedly depth-first search up-to a maximum depth of 6. for (var maxDepth = 1; maxDepth < 6; maxDepth++) { depthFirstSearch(node, maxDepth); } } function depthFirstSearch(node, maxDepth) { // If reached the maximum depth, stop recursing. if (maxDepth <= 0) { return; } // Recurse for all children of node. for (var i=0, c=node.children.length; i<c; i++) { depthFirstSearch(node.children[i], maxDepth-1); } } </syntax> ======= Support ======= <syntax js> function run(root) { return iterativeDeepeningDepthFirstSearch(root); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Iterative deepening depth-first search", "height":"290px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style> g.node { font-family: Verdana, Helvetica; font-size: 12px; font-weight: bold; } circle.node-dot { fill: lightsalmon; stroke: red; stroke-width: 1px; } g.selected circle.node-dot { fill: #6495ED; stroke: blue; } g.current circle.node-dot { fill: #FFF; stroke: blue; } path.link { fill: none; stroke: gray; } body {margin:0px} </style> <script src="http://d3js.org/d3.v2.js"></script> <script> var maxNodes = 10; var treeData; function newTree() { treeData = {data:Math.floor(Math.random()*20), children:[]}; var allNodes = [treeData]; // generate a random tree for (var i=0; i<maxNodes; i++) { var child = {data:Math.floor(Math.random()*20), children:[]}; var parent = allNodes[Math.floor(allNodes.length*Math.random())]; parent.children.push(child); allNodes.push(child); } buildTree("#tree-container"); reset(); } var layoutRoot = null; function buildTree(containerName) { // size of the diagram var size = { width:300, height: 250}; var tree = d3.layout.tree() .sort(null) .size([size.width, size.height-40]) .children(function(d) { return d.children; }); var nodes = tree.nodes(treeData); var links = tree.links(nodes); // root if (!layoutRoot) { layoutRoot = d3.select(containerName) .append("svg:svg").attr("width", size.width).attr("height", size.height) .append("svg:g") .attr("class", "container") .attr("transform", "translate(0,20)"); } else { layoutRoot.selectAll("path.link").remove(); layoutRoot.selectAll("g.node").remove(); } // Edges between nodes as a <path class="link" /> var link = d3.svg.diagonal(); layoutRoot.selectAll("path.link") .data(links) .enter() .append("svg:path") .attr("class", "link") .attr("d", link); layoutRoot.selectAll("path.link").each(function(d) {d.link = this;}); // nodes var nodeGroup = layoutRoot.selectAll("g.node") .data(nodes) .enter() .append("svg:g") .attr("class", "node") .attr("transform", function(d) { return "translate(" + d.x + "," + d.y + ")"; }); nodeGroup.append("svg:circle") .attr("class", "node-dot") .attr("r", 15); nodeGroup.append("svg:text") .attr("dy", 4) .text(function(d) { return d.data; }) .attr("text-anchor", "middle"); } window.onload = function() { newTree(); }; function update(n, x, isRunning, duration, $prev) { if (x.stack.length < 1 && !x.hasOwnProperty('returnedValue')) { d3.selectAll("g.node").classed("selected", false); } var newPrev = $prev; var node = x.lookupInScope("node"); var d3Node = node? d3.selectAll("g.node").filter(function(d) {return d===node;}) : null; if (node && d3Node) { var unselectedNode = d3Node.filter(":not(.selected)"); unselectedNode.classed("selected", true); newPrev = function(prev) { unselectedNode.classed("selected", false); prev(); }.bind(undefined, newPrev); } d3.selectAll("g.node").classed("current", function(d) {return d===node;}); return newPrev; } function args() { return treeData; } </script> </head> <body> <div id="tree-container" style="position:relative"> <button onclick="newTree()" style="position:absolute;left:0px;top:0px">New Tree</button> </div> </body> </html></syntax>

algorithm/iterative_deepening_depth-first_search.txt · Last modified: 2015/02/02 08:28 (external edit)