Write in Javascript //Perform depth-limited search from initial state, using def

Question

Write in Javascript

//Perform depth-limited search from initial state, using defined "is_goal_state"
//and "find_successors" functions
//Will not examine paths longer than "depth_limit" (i.e. paths that have "depth_limit" states in them, or "depth_limit-1" actions in them)
//Returns: null if no goal state found
//Returns: object with two members, "actions" and "states", where:
// actions: Sequence(Array) of action ids required to reach the goal state from the initial state
// states: Sequence(Array) of states that are moved through, ending with the reached goal state (and EXCLUDING the initial state)
// The actions and states arrays should both have the same length.
function depth_limited_search(initial_state,depth_limit) {

/***Your code for depth-limited search here!***/
  
/***DO NOT do repeated state or loop checking!***/
  
/*
Hint: You may implement DLS either iteratively (with open set) or recursively.
  
In the iterative case, you will need to do similar to breadth-first search and augment
the state. In addition to predecessor and action, you will also need to store depth.
(You should be able to re-use your BFS code and only make a small amount of changes to
accomplish this. Be sure to remove repeat checking!)

In the recursive case, you don't need the above. Building the solution path is a little
trickier, but I suggest you look into the Array.unshift() function.
*/
}

Explanation / Answer

var Nods = [
{
links: [ 1 ], // node 0 is linked to node 1
visited: false
}, {
links: [ 0, 2 ], // node 1 is linked to node 0 and 2
path: [],
visited: false
},
...
];

function B_F_S( start ) {
var List = [ start ];

Nods[ start ].visited = true;

while ( List.length > 0 ) {
var Index_Node = List.shift();
Nods[ Index_Node ].links.forEach( function( Index_Child ) {
if ( !Nods[ Index_Child ].visited ) {
Nods[ Index_Child ].visited = true;
List.push( Index_Child );
}
} );
}
};

B_F_S( 0 );

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.