修道士野人問題のpython解

54675 ワード

人工知能

修道士野人問題のpython解

問題説明

状態空間表示

プログラム設計

実行結果

ソースコード(Python 3.5)

問題の説明
修道士(Missionaries)と野人(Cannibals)の問題修道士の野人が川を渡る問題は人工知能分野の典型的な問題であり、その経典は以下のように記述されている.川の左岸にはN人の宣教師(M)、N人の野人(C)と1隻の船(Boat)があり、修道士たちはこの船で全員を川に運びたいと思っていますが、以下の条件があります.

修道士と野人は船を漕ぐが、船は毎回K人しか運べない.

岸辺の野人の数は修道士を超えてはいけません.そうしないと、修道士は野人に食べられます.上記の制約は、1 M≧Cのいつでも両岸、船上で宣教師の人数が野の人数より少なくないこと(M=0の場合を除き、宣教師もいない);2 M+C≦K船上の人数がK以内に制限されていることを表すことができる.
じょうたいくうかんひょうげん
(一)状態空間この問題の解の中で、三元グループ(M,C,S)を用いて問題の状態を表すことを選択し、式中Mは開始岸修道士の人数を表し、Cは開始岸野人の人数を表し、Sは0-1変数で、船の位置を表し、Sが0の場合は船が開始岸で、1の場合は船が終点岸であることを表す.(0,3,0)開始岸には3人の野人がいて、修道士がいなくて、船は開始岸にいます.
そこで修道士野人問題は、(3,3,0)から(0,0,1)への状態転換として記述できる.この問題の状態空間には32種類の状態があり、そのうち12種類の不合理な状態がある:(1,0,1)右岸に2つのM,3つのCがあることを説明する.4種類の不可能な状態:(3,3,0)すべてのMとCが左岸にあり、船が右岸にあるので利用可能な状態は16種類あり、合理的な状態空間を構成する.可能な問題状態は、(0,0,0,1)、(0,1,1,1)、(0,2,1)、(1,1,0,1)、(1,1,1,0)、(1,1,1,1,1)、(1,2,2,0)、(1,2,2,1)、(1,3,3,0)、(2,3,0)、(2,1)、(2,1,1,1,1,1)、(2,1,1,1,(2,1,1,1,0)、(2,2,2,2,2,0)、(2,(2,2,2,2,2,0,2,1),(2,3,0),(3,1,0),(3,2,0), (3, 3, 0).
(二)操作セットこの問題種でOperation操作演算子を定義し、二元グループを用いる(M,C)は、式中Mは1回のボート漕ぎ中に船上の修道士の数を表し、Cは野人の数を表す.また、問題状態を操作演算するたびに、問題状態のSを変更しなければならない.すなわち、船は1岸から別岸に向かわなければならない.例えば、初期問題状態(3,3,0)に(1,1)演算子を使用すると、問題状態は(2,2,1),これは1人の修道士と1人の野人がボートを漕いで終点岸に着くと,船が重点岸に留まることを示す.左右の両岸や着用によっても野人の数が修道士の数より大きいという制約が現れず,利用可能な操作演算子は5種類あり,(0,1),(0,2),(1,1),(2,0),(2,0),(2)である.
プログラミング
(一)記憶構造1.基本問題状態と操作演算子はリスト記憶を用いる.本問題は簡単なデータ挿入、抽出などの機能のみを用いる必要があるため、Pythonが提供する基本データ構造を選択してリストを完成させることができる.使用リストが問題を表す状態空間は、[[0,0,1],[0,1],[0,1],[0,1],[1,1,1,[1,0],[1,1,[1,2,0],[1,2,1],[1,2,1]である., [1, 3, 0], [2, 0, 1], [2, 1, 0], [2, 1, 1], [2, 2, 0], [2, 2, 1], [2, 3, 0], [3, 1, 0], [3, 2, 0], [3, 3, 0]];操作セットは、[[0,1],[0,2],[1,0],[1,1],[2,0]];
2.ノード関係はディクショナリを使用して保存されます.ターゲットノードを見つけたら、開始ノードから現在のノードへのパスを遡及する必要があります.これは、ノード間の関係を格納する必要があります.ここでは、辞書を使用してノード間の親族関係を格納します.サブノードはキーで、親ノードは値です.
(二)アルゴリズム基本思想1.まず問題初期状態(initial_state)ノードをOPENテーブルに入れる(一時記憶用);2.OPENテーブルからヘッダノードを取り出し、ターゲットノードであるか否かを判定する.ターゲットノードであればタスク完了、結果出力;ターゲットノードでなければ次へ;3.OPENテーブルから取り出したターゲットノードではない現在のノードに対して拡張性判定を行い、その後使用した探索ポリシーに従ってそのサブノードをOPENテーブルに格納する;現在のノードが拡張できない場合、プログラムは終了し、問題は解決しません.
(三)探索戦略今回は広さ優先アルゴリズム、境界深さ優先アルゴリズム、グローバル啓発探索アルゴリズムを用いてそれぞれ問題を解いた.ここで、グローバル啓発探索アルゴリズムで使用される啓発関数はf(n)=d(n)+w(n)、d(n)は現在の節点深さ、w(n)は未渡河人数である.境界深さ優先アルゴリズムは、深さしきい値を25に設定します.
(四)関数設計と呼び出し関係1.関数設計このプログラムを設計し、10個のカスタム関数に使用する.(1)create_vertex()とcreate_edges()は、問題条件を初期化し、対応するノードとエッジを生成するために使用されます.(2)move()は、問題状態に対してオペレータを実行し、移動中の各状態の妥当性(不合理な状態を回避し、船の状態を制御するなど)を制御するために用いられ、(3)wheter_expandable()は、現在のノードが拡張可能であるか否かを判断するために用いられる.(4)get_d(), get_w()とsearch_Heuristic()は共同で啓発的な検索を実現する.get_d()現在のノードの深さを取得するために、get_w()現在のノードからターゲットノードまでの距離を計算するために使用されます.すなわち、まだ川を渡っていない人が何人いるかを計算します.(5)search_depth()深さ優先探索アルゴリズム;(6)search_breadth()広さ優先探索アルゴリズム;(7)heap_adjust(), heap_create()とheap_sort()は、生成されたサブノードをソートするためのスタックソート機能を実現するために使用される.
2.関数呼び出しリレーションシッププログラムにおける関数呼び出しリレーションシップ:(1)main()->create_vertex(), create_edges()、検索アルゴリズム(3つの選択肢);(2)search_breadth()->wheter_expandable()->move(); (3) search_ depth ()->whether_expandable()->move(); (4) search_heuristic()->whether_expandable()->move(); search_heuristic()->get_d(), get_w(); search_heuristic()->heap_sort()->heap_adjust(), heap_create().
実行結果
(一)ヒント検索で利用可能な操作演算子は、[[0,1],[0,1],[0,2],[1,0,[1,[1,1],[2,1,[2,0]]出現可能な頂点が16種類あり、それぞれ、[[[[0,0,1],[0,1,[0,1,1,1,1,[0,1,[0,1,[1,1,[1,1,[1,1,1,[1,[1,1,[1,[1,[1,1,[1,[1,[1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,1.,[2,3,0],[3,1,0],[3,2,0],[3,3,0]]渡河成功!経路は、[3,3,0]->[2,2,1]->[3,2,0]->[3,0,1]->[3,1,0]->[1,1]->[2,2,0]-[0,2,1]-[0,1]-[0,3,0]-[0,1]-[1,1,1,0]-[0,0,0]
(二)広さ優先探索に利用可能な操作演算子は、[[0,1],[0,1,[1,2],[1,0,[1,1,[1,1],[2,0]]が出現する可能性のある頂点が16種類あり、それぞれ、[[[[0,0,0,1],[0,1,1,1,1,1,1,[0,1,1,1,1,[1,1,1,1,[1,1,[1,1,[1,1,[1,[1,[1,[1,[1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,[2,1,[2,1,[2,1,[2,1,[2,3,0],[3,1,0],[3,2,0],[3,3,0]]渡河成功!経路は、[3,3,0]->[3,1,1]->[3,2,0]->[3,0,1]->[3,1,0]->[1,1]->[2,2,0]->[0,2,1]-[0,1]-[0,3,0]-[0,1]-[0,2,0]-[0,0,1]
(3)境界深さ探索に利用可能な演算子は,[[0,1],[0,1,[0,2],[1,0,[1,1,[1,1],[2,0]]出現可能な頂点が16種類あり,それぞれ,[[[0,0,0,1,[0,1,[0,1,1,1,1,1,1,[0,1,1,[1,1,[1,1,1,[1,1,[1,1,[1,[1,1,[1,[1,[1,[1,[1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,1,[2,[2,[2,1,[2,1,[2,1,[,[2,3,0],[3,1,0],[3,2,0],[3,3,0]]渡河成功!経路は、[3,3,0]->[3,1,1]->[3,2,0]->[3,0,1]->[3,1,0]->[1,1]->[2,2,0]->[0,2,1]-[0,1]-[0,3,0]-[0,1]-[0,2,0]-[0,0,1]
ソースコード(Python 3.5)
(一)mainファイル

from initial import create_edges
from initial import create_vertex
from search_breadth import search_breadth
from search_depth import search_depth
from search_heuristic import search_heuristic

capacity = 2  #      ，           
Missionaries = 3  #       
Cannibals = 3  #     
init_state = [Missionaries, Cannibals, 0]    #       ，       、            
layer = 25  #             
set_of_operation = create_edges(capacity)  #           ，       
set_of_vertex = create_vertex(Missionaries, Cannibals)  #            ，        

# search_breadth(init_state, set_of_operation)  #           
# search_depth(init_state, set_of_operation, layer)   #           
search_heuristic(init_state, set_of_operation)   #

(二)initialファイル

def create_vertex(missionary, cannibal):  #             ，     

    init_state = [missionary, cannibal, 0]  #     
    set_of_state = []  #         
    count = 0
    for i in range(missionary+1):  #          ，     

        for j in range(cannibal+1):

            if init_state[0] == 0 or init_state[0] >= init_state[1]:
                if i != 0 and j != 0:
                    set_of_state.append([i, j, 0])
                if i != missionary and j != cannibal:
                    set_of_state.append([i, j, 1])
                count += 1
    print('        ', count, ' ,    ：', set_of_state)


def create_edges(capacity):  #         ，  
    set_of_operation = []  #         
    for i in range(capacity + 1):
        for j in range(capacity + 1):
            if i + j <= capacity and (i >= j or i == 0):
                if i == 0 and j == 0:
                    continue
                set_of_operation.append([i, j])
    print('        ：', set_of_operation)
    return set_of_operation

(三)moveファイル

def move(vertex, edge, init_missionary=3, init_cannibal=3):
    if vertex[2] == 1:
        missionary = vertex[0] + edge[0]
        cannibal = vertex[1] + edge[1]
        state_of_boat = 1 - vertex[2]
    else:
        missionary = vertex[0] - edge[0]
        cannibal = vertex[1] - edge[1]
        state_of_boat = 1 - vertex[2]
    if missionary != 0 and missionary < cannibal:
        return False
    elif (init_missionary - missionary) != 0 and ((init_missionary - missionary) < (init_cannibal - cannibal)):
        return False
    elif missionary < 0 or cannibal < 0 or (init_missionary - missionary) < 0 or (init_cannibal - cannibal) < 0:
        return False
    else:
        return [missionary, cannibal, state_of_boat]

(四)heap_sortファイル

def heap_adjust(lists, pos, length):  #    (    ，     )：
    max_ = pos
    lchild = 2*pos+1  #   lists   0  ，         2*pos+1,2*pos+2
    rchild = 2*pos+2
    if max_ < length // 2:  #      
        if lchild < length and lists[lchild][3] > lists[max_][3]:
            max_ = lchild
        if rchild < length and lists[rchild][3] > lists[max_][3]:
            max_ = rchild
        if max_ != pos:  #   max_     ，       
            lists[max_], lists[pos] = lists[pos], lists[max_]
            heap_adjust(lists, max_, length)  #     


def heap_create(lists, length):
    for i in range(length // 2)[::-1]:
        heap_adjust(lists, i, length)


def heap_sort(lists):
    length = len(lists)
    heap_create(lists, length)
    for i in range(length)[::-1]:
        lists[0], lists[i] = lists[i], lists[0]  #       ，            
        heap_adjust(lists, 0, i)  #      ，    -1（         ，      -1）

(五)search_breadthファイル

from whether_expandable import whether_expandable


def search_breadth(init_state, set_of_operation):  #         
    open_list = []
    relation = {}
    open_list.append(init_state)
    while 1:
        if open_list == []:  #   open     
            print("  ！open   ，       ,  。")
            return
        vertex = open_list[0]
        open_list = open_list[1: -1]  #   open 
        if vertex == [0, 0, 1]:  #          ，    
            result = []  #       
            result.append(vertex)
            res = []   #           
            print("    ！   ：")
            while res != init_state:
                res = relation[str(result[-1])]
                if res:
                    result.append(res)
                else:
                    break
            for i in result[::-1]:
                if i != result[0]:
                    print(i, '->', end='')
                else:
                    print(i)
            
            return
        else:  #            
            if vertex != init_state:
                sons = whether_expandable(vertex, set_of_operation, relation[str(vertex)])
            else:
                sons = whether_expandable(vertex, set_of_operation, [0, 0, 0])
            if sons:  #            
                for i in sons:
                    relation[str(i)] = vertex  #              ，     ，     
                    open_list.append(i)

(六)search_depthファイル

from whether_expandable import whether_expandable


def search_depth(init_state, set_of_operation, layer):  #         
    open_list = []
    relation = {}
    open_list.append(init_state)
    layer_count = 0
    while 1:
        layer_count += 1
        if layer_count > layer:  #   layer       ，         ，    
            print("        （%d），    ！", layer)
            break
        if open_list == []:  #   open     
            print("  ！open   ，       ,  。")
            return
        vertex = open_list[0]
        open_list = open_list[1: -1]  #   open 
        if vertex == [0, 0, 1]:
            result = []  #       
            result.append(vertex)
            res = []  #           
            print("    ！   ：")
            while res != init_state:
                res = relation[str(result[-1])]
                if res:
                    result.append(res)
                else:
                    break
            for i in result[::-1]:
                if i != result[0]:
                    print(i, '->', end='')
                else:
                    print(i)
            return
        else:
            if vertex != init_state:
                sons = whether_expandable(vertex, set_of_operation, relation[str(vertex)])
            else:
                sons = whether_expandable(vertex, set_of_operation, [0, 0, 0])
            if sons:  #            
                for i in sons:
                    relation[str(i)] = vertex  #              ，     ，     
                    open_list.insert(0, i)

(七)search_heuristicファイル

from whether_expandable import whether_expandable   #      f(n) = d(n) + w(n), d(n)       ，w(n)      
from heap_sort import heap_sort


def get_d(vertex, init_state, relation):  #            
    result = []  #       
    result.append(vertex)
    res = []  #           
    d = 0
    # print("    ！   ：")
    while res != init_state:
        d += 1
        res = relation[str(result[-1])]
        if res:
            result.append(res)
        else:
            break
    return d


def get_w(vertex):  #                  ，          
    return vertex[0] + vertex[1] + 1 - vertex[2]


def search_heuristic(init_state, set_of_operation):
    open_list = []
    relation = {}
    open_list.append(init_state)
    while 1:
        if open_list == []:  #   open     
            print("  ！open   ，       ,  。")
            return
        vertex = open_list[0]
        open_list = open_list[1: -1]  #   open 
        if vertex == [0, 0, 1]:
            result = []  #       
            result.append(vertex)
            res = []  #           
            print("    ！   ：")
            while res != init_state:
                res = relation[str(result[-1])]
                if res:
                    result.append(res)
                else:
                    break
            for i in result[::-1]:
                if i != result[0]:
                    print(i, '->', end='')
                else:
                    print(i)
            return
        else:
            if vertex != init_state:
                sons = whether_expandable(vertex, set_of_operation, relation[str(vertex)])
            else:
                sons = whether_expandable(vertex, set_of_operation, [0, 0, 0])
            if sons:  #            
                sort_list = []
                for i in sons:
                    relation[str(i)] = vertex  #              ，     ，     
                    i.append(get_d(i, init_state, relation) + get_w(i))  #                  ，               
                    sort_list.append(i)
                heap_sort(sort_list)
                for i in sort_list:
                    i = i[:-1]
                    open_list.append(i)

(八)whether_expandableファイル

from move import move


def whether_expandable(vertex, set_of_operation, pre_vertex):  #            
    sons = []
    for operation in set_of_operation:
        m = move(vertex, operation)
        if m:
            if m != pre_vertex:  #                     ，       
                sons.append(m)
    if sons == []:
        return False
    else:
        return sons

rails 管理者が全Userの投稿削除をする（備忘録）

LVSポーリングサーバセット