2
私はグリッドにあり、セル(i,j)から始まり、セル(x,y)に行きたいというSMLの練習をしています。これをシミュレートするために、すべてのセルは状態(i,j,move)として扱われ、前のセルからどのように移動したかを示します。それから、単純なトラバーサルアルゴリズム（もっとdfsに似ています）を書いて、目的のものが見つかるまで状態の検索を開始します。タプルをSMLにキーとしてORD_MAPを作成
トラバーサル関数では、私は訪問先の状態を追跡するために状態をインデックスとして取るMap-Dictionaryを使用することに注意してください。
コード：
val startp = (0,0)
val endp = (3,0)
val (N,M) = (4,4)
(*Define the Basic structures tht will be used*)
datatype movement = RIGHT | DOWN | LEFT | UP
type State = int * int * movement
val firstState = (#1 startp,#2 startp,UP): State
structure STATES_KEY: ORD_KEY =
struct
type ord_key = State
val compare = fn (s1:State, s2:State) =>
if (#1 s1 = #1 s2) andalso (#2 s1 = #2 s2)
then EQUAL
else if (#1 s1 > #1 s2) then GREATER
else LESS
end
structure StatesMap = SplayMapFn(STATES_KEY)
fun convert_ij id = (id div M, id mod N)
fun getNextStates ((i,j,_):State): State list =
[ (i,j+1,RIGHT),
(i+1,j,DOWN),
(i,j-1,LEFT),
(i-1,j,UP)]
fun getPrevState ((i,j,move):State): State =
case move of
RIGHT => (i,j-1,UP)
| LEFT => (i,j+1,UP)
| UP => (i+1,j,UP)
| DOWN => (i-1,j,UP)
(*True -> Invalid State*)
fun checkInvalidState ((i,j,_):State) =
if (i < 0 orelse i > N-1 orelse j < 0 orelse j > M-1)
then true
else false
fun checkEnd ((i,j,_):State) =
if (i = #1 endp andalso j = #2 endp)
then true
else false
fun traversal [] visited = visited
| traversal (h::t) visited =
if (checkEnd h) then visited
else if (checkInvalidState h) then traversal t visited
else if (StatesMap.find (visited, h) = NONE)
then
let
val [s1,s2,s3,s4] = getNextStates h
in
traversal (s1::s2::s3::s4::t) (StatesMap.insert (visited, h, h))
end
else traversal t visited
val it = traversal [firstState] StatesMap.empty
私はプログラムを実行するとトラバース機能を実行する際に、それが無限ループに入りました。それは状態：(1,0)->(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(3,3)
から続きます。そこからは、(3,3)と(3,2)の間に進みます。また、トラバース関数が状態(3,2)にあり、状態(3,3)が存在するときにマップ構造体をチェックしました。つまり、それをもう一度見て、他の状態のチェックを続けるべきではありません。
私はそれが動作し、このループを引き起こすと思うように正確に何が動作しないのですか？