Message Boards Message Boards

1 Reply
3 Total Likes
View groups...
Share this post:

8 -puzzle with the algorithm a *

Posted 10 years ago

I hope everyone is well, today I am writing to ask for your help with the following problem, I have seen in wikipedia the following pseudocode for the algorithm a *.

A*_search algorithm

and I have programmed it in mathematica in the following manner, my doubt arises when interpreting the if, i would like to comment on me if well-written are the if in my code.

astar[start_List] := Module[{goal, inter, closedset, openset, camefrom, gscore, , minimum, current, neighbornodes, k,tentativegscore},
  goal = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
  closedset = {};
  openset = {start};
  camefrom = {};
  gscore[start] := 0;
  fscore[start_] := gscore[start] + manhattan[start];
  While[openset != {},
   inter = fscore /@ start;
   minimum = Position[inter, Min[inter]];
   current = openset[[minimum]];
   If[current == goal,
    reconstructpath[camefrom, goal];
    openset = DeleteCases[openset, current];
    AppendTo[closedset, current];
   (*neighbor_nodes(current) for me it is the same as mutacion[current] then*);
   neighbornodes = mutacion[current];
   For[k = 1, k <= Length[neighbornodes], k++,
    (*line 18*)
    If[FreeQ[closedset, neighbornodes[[k]], Infinity], 
     tentativegscore = 
      gscore[current] + 
       ManhattanDistance[current, neighbornodes[[k]]]]; 
    If[FreeQ[openset, neighbornodes[[k]], Infinity] \[Or] 
      tentativegscore < gscore[neighbornodes[[k]]], 
     camefrom[neighbornodes[[k]]] = current;
     gscore[neighbornodes[[k]]] = tentativegscore;
     fscore[neighbornodes[[k]]] = 
      gscore[neighbornodes[[k]]] + manhattan[neighbornodes[[k]]] ;
     If[FreeQ[openset, neighbornodes[[k]], Infinity], 
      AppendTo[openset, neighbornodes[[k]]]]]

Thanks in advance

POSTED BY: Luis Ledesma

I am not certain about what is going on here, but there are some issues with the code which are making things unnecessarily complicated.

  inter = fscore /@ start;
   minimum = Position[inter, Min[inter]];
   current = openset[[minimum]];

This is giving you unwanted nesting, and possibly more than one minimum. Position[list, minimum] returns the list of positions of all occurrences of minimum. One possibility is to use RandomChoice, another is Position[list,minimum][[1]]

Nesting of lists is not in the pseudo-code so your code will be closer to what is on the wikipedia.

About your question in specific, the Wolfram Language function If works the way you would expect. It doesn't do anything funny.

Aside, I don't see the equivalent of " remove current from openset" or "add current to closedset"

The modern way to approach these sorts of problems is to take advantage of a builtin function like FindShortestPath

POSTED BY: Todd Rowland
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
or Discard

Group Abstract Group Abstract