Use only Java, or C++ for implementation . The A* search can be used to solve th
ID: 3749840 • Letter: U
Question
Use only Java, or C++ for implementation.
The A* search can be used to solve the 8-puzzle problem. There are two candidate heuristic functions:
h1 = the number of misplaced tiles
h2 = the sum of the distances of the tiles from their goal positions
You are to implement the A* using both heuristics and compare their efficiency in terms of depth of the solution and search costs. To test your program and analyze the efficiency, you should generate random problems (>1000 cases) with a variety of solution depths. Collect the data on the different solution depths that you have tested, with their corresponding search cost (# of nodes generated); and average the search costs by depth. A good testing program should test a range of possible cases (2 <= d <= 24).
Note that the average solution depth for a randomly generated 8-puzzle instance is approximately 22. A* Search Costs (nodes generated) d h1 h2 2 6 6 4 13 12 6 20 18 8 39 25 10 93 39 12 227 73 14 539 113 16 1301 211 18 3056 363 20 7276 676 22 18094 1219 24 39135 1641 Comparison of the average search costs for the A* algorithm using heuristics h1 and h2 . This data was averaged over 100 instances of the 8-puzzle for each depth.
User Interface: Provide at least two menu options for your program:
1) An option to generate a solvable random 8-puzzle problem (generated by your program) then solve it using both heuristics. It should output the optimal sequence of states that result from the search, the solution depth and the search cost for each heuristic.
2) An option to input a specific 8-puzzle configuration. The input will contain the configuration for only one puzzle, in the following format (where 0 represents the empty tile and the digits are separated by a space): 1 2 4 0 5 6 8 3 7 This option should solve the entered puzzle and output the optimal sequence of states that result from the search, the solution depth and the search cost for each heuristic. Your program must test the puzzle to be sure that it is solvable. You must handle the input/output gracefullyhandle exceptions.
Explanation / Answer
import orbital.algorithm.template.*;
import orbital.logic.functor.Function;
import orbital.logic.functor.MutableFunction;
import orbital.math.*;
import java.util.*;
public class EightPuzzle implements GeneralSearchProblem {
public static final int maxsteps = 12;
public static void main(String arg[]) {
Function h = create_Heuristic();
GeneralSearch se;
se = new AStar(h);
State solution = (State) se.solve(new EightPuzzle(8));
System.out.println("Found solution: " + solution);
}
protected static final Function create_Heuristic() {
return new Function() {
public Object apply(Object n) {
State o = (State) n;
int[][] se = o.slides;
int position[] = o.tileMoved;
if (position == null)
return Values.getDefaultInstance().valueOf(0);
else
return Values.getDefaultInstance().valueOf(manhattan(position, se[position[0]][position[1]]));
}
};
}
private static int manhattan(int[] position, int tile) {
int[] dest = new int[] {
(tile - 1) % siz, (tile - 1) / siz
};
return Math.abs(dest[0] - position[0]) + Math.abs(dest[1] - position[1]);
}
public static final int L = 0;
public static final int R = 1;
public static final int UP = 2;
public static final int DOWN = 3;
public static final int maxmove = DOWN;
public static final int EMPTY = 0;
private static int siz;
private int[][] goall;
public EightPuzzle(int tiles) {
EightPuzzle.siz = (int) Math.ceil(Math.sqrt(tiles + 1));
if (tiles != siz * siz - 1)
throw new IllegalArgumentException("no such n-puzzle with n=" + tiles + " which is not a k^2-1");
this.goall = goalState(siz);
}
public Object getInitialState() {
State r = new State(shuffle(goalState(siz)), null, 0.0);
System.out.println(r + " to be solved ");
return r;
}
public boolean isSolution(Object n) {
int[][] se = ((State) n).slides;
System.out.println(n + " ");
for (int i = 0; i < se.length; i++)
for (int j = 0; j < se[i].length; j++)
if (se[i][j] != goall[i][j])
return false;
return true;
}
public Iterator actions(Object n) {
State se = (State) n;
int empty[] = indexOf(se.slides, EMPTY);
List ex = new LinkedList();
for (int dir = 0; dir <= maxmove; dir++) {
int[] position = nextOf(empty, dir);
if (position != null)
ex.add(position);
}
return ex.iterator();
}
public Iterator states(Object action, Object n) {
State se = (State) n;
int empty[] = indexOf(se.slides, EMPTY);
int[] position = (int[]) action;
return Collections.singletonList(new State(swap(se.slides, empty, position), empty)).iterator();
}
public TransitionModel.Transition transition(Object action, Object state, Object statep) {
return new Transition(action, 1);
}
public MutableFunction getAccumulatedCostFunction() {
return _accumulatedCostFunction;
}
private static final MutableFunction _accumulatedCostFunction = new MutableFunction() {
public Object apply(Object state) {
return ((State)state).accumulatedCost;
}
public Object set(Object state, Object newAccumulatedCost) {
Object old = ((State)state).accumulatedCost;
((State)state).accumulatedCost = (Real)newAccumulatedCost;
return old;
}
public Object clone() {
throw new UnsupportedOperationException();
}
};
static int[] indexOf(int[][] se, int tile) {
int e[] = new int[2];
for (e[0] = 0; e[0] < se.length; e[0]++)
for (e[1] = 0; e[1] < se[e[0]].length; e[1]++)
if (se[e[0]][e[1]] == tile)
return e;
return null;
}
static int[][] swap(int[][] se, int[] i, int[] j) {
int[][] n_s = new int[se.length][];
for (int k = 0; k < se.length; k++)
n_s[k] = (int[]) se[k].clone();
n_s[i[0]][i[1]] = se[j[0]][j[1]];
n_s[j[0]][j[1]] = se[i[0]][i[1]];
return n_s;
}
static int[] nextOf(int[] i, int direction) {
int[] r = (int[]) i.clone();
switch (direction) {
case L:
r[0]--;
break;
case R:
r[0]++;
break;
case UP:
r[1]--;
break;
case DOWN:
r[1]++;
break;
default:
throw new IllegalArgumentException();
}
return 0 <= r[0] && r[0] < siz && 0 <= r[1] && r[1] < siz ? r : null;
}
private static int[] anyOf(int[] i) {
List dirs = new ArrayList(4);
for (int dir = 0; dir <= maxmove; dir++) {
int[] t = nextOf(i, dir);
if (t != null)
dirs.add(t);
}
int chosen = (int) (Math.random() * dirs.siz());
return (int[]) dirs.get(chosen);
}
private static int[][] shuffle(int[][] r) {
int[] e = indexOf(r, EMPTY);
for (int i = (int) (maxsteps / 2 + Math.random() * maxsteps / 2); i >= 0; i--) {
r = swap(r, e, e = anyOf(e));
}
return r;
}
private static int[][] goalState(int siz) {
int[][] r = new int[siz][siz];
for (int i = 0; i < r.length; i++)
for (int j = 0; j < r[i].length; j++)
r[i][j] = i * siz + j + 1;
r[r.length - 1][r[r.length - 1].length - 1] = EMPTY;
return r;
}
static class State {
int[][] slide;
Real accumulatedCost;
int[] tileMoved;
public State(int[][] slide, int[] tileMoved) {
this(slide, tileMoved, Values.getDefault().NaN());
}
public State(int[][] slide, Real accumulatedCost) {
this(slide, null, accumulatedCost);
}
private State(int[][] slide, int[] tileMoved, Real accumulatedCost) {
this.slide = slide;
this.tileMoved = tileMoved;
this.accumulatedCost = accumulatedCost;
}
private State(int[][] slide, int[] tileMoved, double accumulatedCost) {
this(slide, tileMoved, Values.getDefaultInstance().valueOf(0));
}
Real getAccumulatedCost() {
return accumulatedCost;
}
public String toString() {
return MathUtilities.format(slide) + "(" + getAccumulatedCost() + ")";
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.