8 -puzzle with the algorithm a *

Posted 9 years ago
6757 Views
|
|
3 Total Likes
|
 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 algorithmand 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
 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