Do in Javascript //Perform breadth-first search from initial state, using define

Question

Do in Javascript

//Perform breadth-first search from initial state, using defined "is_goal_state"

//and "find_successors" functions

//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 breadth_first_search(initial_state) {

var open = []; //See push()/pop() and unshift()/shift() to operate like stack or queue

//https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array

var closed = new Set(); //https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set

/***Your code for breadth-first search here***/

/*

Hint: In order to generate the solution path, you will need to augment

the states to store the predecessor/parent state they were generated from

and the action that generates the child state from the predecessor state.

For example, make a wrapper object that stores the state, predecessor and action.

Javascript objects are easy to make:

var object={

member_name1 : value1,

member_name2 : value2

};

Hint: Because of the way Javascript Set objects handle Javascript objects, you

will need to insert (and check for) a representative value instead of the state

object itself. The state_to_uniqueid function has been provided to help you with

this. For example

var state=...;

closed.add(state_to_uniqueid(state));

if(closed.has(state_to_uniqueid(state)) { ... }

*/

/***Your code to generate solution path here***/

return {

actions : /*array of action ids*/,

states : /*array of states*/

};

//OR

//No solution found

return null;

}

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 Breadth_FirstSearch( start ) {
var List_ToExplore = [ start ];

nods[ start ].visited = true;

while ( List_ToExplore.length > 0 ) {
var node_Index = List_ToExplore.shift();
nods[ node_Index ].links.forEach( function( Child_Indexx ) {
if ( !nods[ Child_Indexx ].visited ) {
nods[ Child_Indexx ].visited = true;
List_ToExplore.push( Child_Indexx );
}
} );
}
};

Breadth_FirstSearch( 0 );

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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