java - Solving 8 puzzle using A* algorithm and Manhattan Heuristic -
i have written program solve 8 puzzle using a* algorithm , manhattan heuristic programs doesn't seem work correctly ( minimum number of moves ) inputs , correct output, number of states expanded larger should be.
my program has 4 classes:
game state: represent game
astar: astar algorithm
astarlist: data structure representing open , closed lists. (i know data structure bad in terms of performance. improve later on)
utilities
here part of code:
(sorry large code size. suspect wrong astar algorithm. so, need not go through other classes.)
astar
public class astar { public static void solve(gamestate gamestatetosolve) { astarlist openlist = new astarlist(); astarlist closedllist = new astarlist(); openlist.add(gamestatetosolve); int iteration = 1; while (!openlist.isempty()) { system.out.println((iteration++)); gamestate current = openlist.getnext(); if (current.isgoalstate()) { current.print(); return; } gamestate children[] = current.expand(); closedllist.addwithoutduplication(current); (int = 0; < children.length; i++) { boolean presentinopenlist = openlist.ispresent(children[i]); boolean presentinclosedlist = closedllist.ispresent(children[i]); if (!presentinopenlist && !presentinclosedlist) { openlist.add(children[i]); } else if (presentinclosedlist && !presentinopenlist) { if (closedllist.getcostof(children[i]) > children[i].getmovementscount()) { closedllist.remove(children[i]); openlist.add(children[i]); } } else if (presentinopenlist && !presentinclosedlist) { if (openlist.getcostof(children[i]) > children[i].getmovementscount()) { openlist.remove(children[i]); openlist.add(children[i]); } } } } } public static void main(string[] args) { solve(new gamestate( new int[]{0,7,3,1,8,6,5,4,2}, new arraylist<integer>(), gamestate.numbers_array)); } } astarlist
public class astarlist { arraylist<gamestate> list; public astarlist() { list = new arraylist<>(); } public boolean ispresent(gamestate gamestate) { (int = 0; < list.size(); i++) { if (list.get(i).equals(gamestate)) { return true; } } return false; } public void remove(gamestate gamestate) { (int = 0; < list.size(); i++) { if (list.get(i).equals(gamestate)) { list.remove(i); } } } public void add(gamestate gamestate) { (int = 0; < list.size(); i++) { if (list.get(i).manhattandistance() > gamestate.manhattandistance()) { list.add(i, gamestate); return; } } list.add(gamestate); } public void addwithoutduplication(gamestate gamestate) { (int = 0; < list.size(); i++) { if (list.get(i).equals(gamestate)) { list.remove(i); list.add(i, gamestate); } if (list.get(i).manhattandistance() > gamestate.manhattandistance()) { list.add(i, gamestate); return; } } list.add(gamestate); } public boolean isempty() { return list.isempty(); } public gamestate getnext() { return list.remove(0); } public int getheuristicof(gamestate gamestate) { (int = 0; < list.size(); i++) { if (list.get(i).equals(gamestate)) { return list.get(i).manhattandistance(); } } throw new runtimeexception(); } public int getcostof(gamestate gamestate) { (int = 0; < list.size(); i++) { if (list.get(i).equals(gamestate)) { return list.get(i).getmovementscount(); } } return -1; } } gamestate
public final class gamestate1 { public gamestate1(gamestate gamestate) { // creates gamestate similar 1 passed } public gamestate1(int[] array, arraylist<integer> movements, int type) { //... } public int getmovementscount() { // returns number of movements made far } public int[] getpositionsarrayof(int[] numbersarray) { //... } public int[] getnumbersarrayof(int[] positionsarray) { //... } public void move(int direction) { //... } public gamestate getstateonmovement(int direction) { //... } public boolean movepossible(int direction) { //... } public int[] getpossiblemovements() { //... } public gamestate[] expand() { //.. } public boolean equals(gamestate anotherstate) { // returns true if board state same } public boolean isgoalstate() { // returns true if goal state } public void print() { //... } public int numberofinversions() { // returns number of inversions } public boolean issolvable() { //returns true if solvable } public int manhattandistance() { // returns manhattan distance } } sorry large code size. suspect wrong astar algorithm. s0, need not go through other classes.
i haven't read code exhaustively, think might because sort open list heuristic, not total cost function. i'm sure know...
f(x) = g(x) + h(x) where g(x) path cost far, , h(x) manhattan distance.
in method astarlist.add() try changing line
if (list.get(i).manhattandistance() > gamestate.manhattandistance()) { to
if (list.get(i).getcost() > gamestate.getcost()) { where gamestate.cost() is
public int getcost() { return getmovementscount() + manhattandistance(); } edit: noticed handling of neighboring nodes looks bit odd. should never removing closed list. firstly want discard neighbor (i.e. children[i]) if closed list contains same or shorter path node. second if neighbor new (i.e. not present in open list) or if have found shorter path same node on open list, add open list.
boolean presentinopenlist = openlist.ispresent(children[i]); boolean presentinclosedlist = closedllist.ispresent(children[i]); if (presentinclosedlist && children[i].getmovementscount() >= closedllist.getcostof(children[i])) { // ignore node continue; } if (!presentinopenlist || openlist.getcostof(children[i]) > children[i].getmovementscount()) { openlist.add(children[i]); } it might use map instead of list open/closed lists, want make sure have single unique entry each (x,y) coordinate; 1 lowest cost found far.
Comments
Post a Comment