Write in Javascript //Perform breadth-first search from initial state, using def

Question

Write 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 astar_search(initial_state) {

var open = new FastPriorityQueue(function(a,b) { return a.estimated_total_cost < b.estimated_total_cost; });

var closed = new Set();

var fixed_step_cost = 1; //Assume action cost is constant

/***Your code for A* search here***/

/*

Hint: A* is very similar to BFS, you should only need to make a few small modifications to your BFS code.

You will need to add values to your augmented state for path cost and estimated total cost.

I suggest you use the member name "estimated_total_cost" so that the above priority queue code will work.

Call function calculate_heuristic(state) (provided for you) to calculate the heuristic value for you.

See (included) FastPriorityQueue.js for priority queue usage example.

*/

//No solution found

return null;

}

Explanation / Answer

var Nodess = [
{
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_First_search( start ) {
var list_To_explore = [ start ];

Nodess[ start ].visited = true;

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

breadth_First_search( 0 );

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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