オオカミとヤギとキャベツをVB.NETで解く(2)

前回の続きになります。

探索

次のようにゴールを探索することにします。

1. 初期状態をキューに格納する
2. キューから状態をひとつ取り出し今の状態とする
3. 今の状態が失敗なら2に戻る
4. 今の状態が過去にチェックした状態と同じなら2に戻る
5. 今の状態がゴールなら終了する
6. 今の状態から移れる状態を全てキューに格納する
7. 今の状態をチェック済みリストに加える
8. 2に戻る

次のようなコードになりました。

Module Module1
    Sub Main()
        Dim SearchQueue As Queue(Of State) = New Queue(Of State)    '未探索の状態を格納するキュー
        Dim SearchedList As List(Of State) = New List(Of State)     '探索済みの状態を格納するリスト
        Dim NowState As State = State.StartState()                  '現在調べている状態
        Dim NextState As State                                      '次の状態
        SearchQueue.Enqueue(NowState)
        While SearchQueue.Count > 0
            NowState = SearchQueue.Dequeue()

            If NowState.IsFailure() Then Continue While '失敗なら他の状態を探索

            If SearchedList.IndexOf(NowState) >= 0 Then Continue While '探索済みなら他の状態を探索

            If NowState.IsGoal() Then   'ゴールなら終了
                Exit While
            End If

            For Each Operation As Operate In [Enum].GetValues(GetType(Operate)) '現在の状態から移れる状態を生成してキューに格納
                NextState = NowState.MakeNext(Operation)
                If NextState IsNot Nothing Then SearchQueue.Enqueue(NextState)
            Next

            SearchedList.Add(NowState)  '探索済みに追加

        End While
        Console.ReadLine()
    End Sub

End Module

過去にチェックした状態と同じか判定するためにState同士を比較できるようにします。Equalsメソッドをオーバーライドし、農夫、オオカミ、ヤギ、キャベツの状態が同じであれば同じ状態となるようにします。

'メンバーが同じなら等価とする
Public Overloads Function Equals(ByVal obj As State)
    Return Me.Farmer = obj.Farmer AndAlso Me.Wolf = obj.Wolf AndAlso Me.Goat = obj.Goat AndAlso Me.Cabbage = obj.Cabbage
End Function

'メンバーが同じなら等価とする
Public Overrides Function Equals(obj As Object) As Boolean
    'どちらかがNothingまたは型が違えば等価ではない
    If obj Is Nothing OrElse Me Is Nothing OrElse Me.GetType() IsNot obj.GetType() Then
        Return False
    Else
        Return Equals(CType(obj, State))
    End If
End Function

'EqualsがTrueの時に同じ値を返す
Public Overrides Function GetHashCode() As Integer
    Return -(CInt(Me.Farmer) * 8 + CInt(Me.Wolf) * 4 + CInt(Me.Goat) * 2 + CInt(Me.Cabbage))
End Function

最後に探索した結果を確認できるように結果を出力する部分を作っていきます。
状態を表すStateクラスは1つ前の状態を覚えているため、再帰的に前の状態をたどることで初期状態からゴールまでの状態を出力できそうです。

まず1つ前の状態にアクセスできるようStateにプロパティを用意します。

'1つ前の状態を取得
Public ReadOnly Property ParentState As State
    Get
        Return Me.Parent
    End Get
End Property

次にStateに今の状態を出力する関数を作ります。

'状態を出力
Public Sub Print()

    If Me.Operation <> Operate.Start Then
        Dim OnBoat As String = ""
        Select Case Me.Operation
            Case Operate.Solo
                OnBoat = "F "
            Case Operate.WithWolf
                OnBoat = "FW"
            Case Operate.WithGoat
                OnBoat = "FG"
            Case Operate.WithCabbage
                OnBoat = "FC"
        End Select
        If Me.Farmer Then
            OnBoat = "---" & OnBoat & "-->"
        Else
            OnBoat = "<--" & OnBoat & "---"
        End If
        Console.WriteLine(Space(6) & OnBoat)
    End If

    Dim West As String = ""
    Dim East As String = ""

    If Farmer Then
        East &= "F"
    Else
        West &= "F"
    End If

    If Wolf Then
        East &= "W"
    Else
        West &= "W"
    End If

    If Goat Then
        East &= "G"
    Else
        West &= "G"
    End If

    If Cabbage Then
        East &= "C"
    Else
        West &= "C"
    End If

    Console.WriteLine(West.PadRight(5) & "～～～～～" & East.PadLeft(5))

End Sub

アルファベットF,W,G,Cはそれぞれ農夫、オオカミ、ヤギ、キャベツを表していて、それぞれどっちに移動したか、どっちに居るかを表現しています。

Module1内に次の関数を付け足します。再帰的に前の状態をたどり、初期状態から順番に状態を出力します。

'前の状態をたどって結果を出力
Private Sub Result(ByVal NowState As State)
    If NowState.ParentState IsNot Nothing Then Result(NowState.ParentState)
    NowState.Print()
End Sub

ゴールしたら結果を出力するようにMainのゴール判定の部分で関数Resultを呼びます。

If NowState.IsGoal() Then   'ゴールなら結果を出力して終了
 Result(NowState)
 Exit While
End If

結果

作ったプログラムを実行すると次のような結果が出力されました。

FWGC ～～～～～
      ---FG-->
WC   ～～～～～   FG
      <--F ---
FWC  ～～～～～    G
      ---FW-->
C    ～～～～～  FWG
      <--FG---
FGC  ～～～～～    W
      ---FC-->
G    ～～～～～  FWC
      <--F ---
FG   ～～～～～   WC
      ---FG-->
     ～～～～～ FWGC

文章にすると、手順は

1. ヤギを運ぶ
2. 農夫だけ戻る
3. オオカミを運ぶ
4. ヤギを戻す
5. キャベツを運ぶ
6. 農夫だけ戻る
7. ヤギを運ぶ

という結果になりました。

次の記事で今回作ったコードを載せておきます。