Hi. I have a 8-puzzle solver that is done using breadth-first search. I need to
ID: 3537682 • Letter: H
Question
Hi. I have a 8-puzzle solver that is done using breadth-first search. I need to convert it into a A* search and need to take into consideration manhattan distance. I'm not sure where to make the modifications.
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class Puzzle {
Queue<String> agenda = new LinkedList<String>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> stateDepth = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes
Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor
public static void main(String args[]){
String str="087465132"; // Input the Board State as a String with 0 as the Blank Space
Puzzle e = new Puzzle(); // New Instance of the EightPuzzle
e.add(str, null); // Add the Initial State
while(!e.agenda.isEmpty()){
String currentState = e.agenda.remove();
e.up(currentState); // Move the blank space up and add new state to queue
e.down(currentState); // Move the blank space down
e.left(currentState); // Move left
e.right(currentState); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String newState, String oldState){
if(!stateDepth.containsKey(newState)){
int newValue = oldState == null ? 0 : stateDepth.get(oldState) + 1;
stateDepth.put(newState, newValue);
agenda.add(newState);
stateHistory.put(newState, oldState);
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String currentState){
int a = currentState.indexOf("0");
if(a>2){
String nextState = currentState.substring(0,a-3)+"0"+currentState.substring(a-2,a)+currentState.charAt(a-3)+currentState.substring(a+1);
checkCompletion(currentState, nextState);
}
}
void down(String currentState){
int a = currentState.indexOf("0");
if(a<6){
String nextState = currentState.substring(0,a)+currentState.substring(a+3,a+4)+currentState.substring(a+1,a+3)+"0"+currentState.substring(a+4);
checkCompletion(currentState, nextState);
}
}
void left(String currentState){
int a = currentState.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String nextState = currentState.substring(0,a-1)+"0"+currentState.charAt(a-1)+currentState.substring(a+1);
checkCompletion(currentState, nextState);
}
}
void right(String currentState){
int a = currentState.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String nextState = currentState.substring(0,a)+currentState.charAt(a+1)+"0"+currentState.substring(a+2);
checkCompletion(currentState, nextState);
}
}
private void checkCompletion(String oldState, String newState) {
add(newState, oldState);
if(newState.equals("123456780")) {
System.out.println("Solution Exists at Level "+stateDepth.get(newState)+" of the tree");
String traceState = newState;
while (traceState != null) {
System.out.println(traceState + " at " + stateDepth.get(traceState));
traceState = stateHistory.get(traceState);
}
System.exit(0);
}
}
}
Explanation / Answer
To implement A* algorithm you need to implement it through sets and not Queue. You need to keep two sets, open set and closed set. Closed set contains those nodes which are in the optimal path at any point. The f_value and g_value are the distances of a node from the source node and estimated distance of the node from the goal node. Initially source node is kept in the open set. The algorithm is as follows:- Take a node from the open set which has the minimum f_value. Add this node to the closed set and add all its neighbours in the openset. The code is as follows:- import java.util.ArrayList; import java.util.Map; import java.util.TreeSet; /** * * @author utkarsh */ public class AStar { TreeSet closedset; TreeSet openset; public AStar() { } public ArrayList AStarAlgo(Node start, Node goal) { int parentPointerRedirection = 0; closedset = new TreeSet(); openset = new TreeSet(); openset.add(start); // The set of tentative nodes to be evaluated, initially containing the start node start.setGVal(0); // Estimated total cost from start to goal through y. start.setHVal(start.heuristic_cost_estimate(goal)); //f_score.put(start, start.getGScore() + heuristic_cost_estimate(start, goal)); while(!openset.isEmpty()){ // while openset is not empty Node current = getAndRemoveMinFVal(); // the node in openset having the lowest f_score[] value if(current.equals(goal)){ return reconstruct_path(current); } openset.remove(current); closedset.add(current); // add current to closedset ArrayList currentNeighbours = current.neighbourNodes(); current.setNeighbourNodes(currentNeighbours); for (Node neighbour : currentNeighbours) { int tentative_g_val = current.getGVal() + dist_between(current, neighbour); if(closedset.contains(neighbour)){ // neighbor in closedset Node similarNeighbour = getNodeFromSet(closedset, neighbour); if(similarNeighbour.getGVal() > tentative_g_val) { similarNeighbour.setGVal(tentative_g_val); closedset.remove(similarNeighbour); openset.add(similarNeighbour); } continue; } if( !openset.contains(neighbour) || tentative_g_valRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.