Algorithm/알고리즘 이론

알고리즘 #1_Missionaries and cannibals problem(선교사와 식인종 문제)_[python을 통한 DFS Algorithm]

Tigercow.Door 2017. 10. 13. 17:39

많은 사람들에게 유명한
missionaries and cannibals problem
(선교사와 식인종 문제)

강의 왼쪽에 선교사 3명과 식인종 3명이 있고 모두를 강 오른쪽으로 건너게끔 해야한다.
1. 강의 왼쪽이나 오른쪽에서 선교사의 수보다 식인종의 수가 많으면 안된다.
2. 보트에는 최대 2명이 탑승할 수 있으며 최소1명이 탑승해야 움직일 수 있다.

학교 AI시간에 각 state와 action에 대해서 제출하라는 과제가 있었는데 그것을 통해 DFS algorithm을 응용하여 python으로 구현해보았다.
분명히 잘못된 부분이나 부족한 부분이 있을 것 같은데
일단 포스팅을 진행하고 천천히 더 공부해야 겠다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
import copy
# 전역변수 선언
state = [1,[3,3],[0,0]]
action = [1,0,0]
goal = [2,[0,0],[3,3]]
visited = []
stack = []
temp = []
 
# 함수선언
# 왼쪽에서 오른쪽으로 가는 움직임 반환
def LtoRaction():
  return [[1,1,1],[1,1,0],[1,2,0],[1,0,1],[1,0,2]]
 
# 오른쪽에서 왼쪽으로 가는 움직임 반환
def RtoLaction():
  return [[2,1,1],[2,1,0],[2,2,0],[2,0,1],[2,0,2]]
 
# 스테이트와 액션에 맞게 움직이기
def move(state,action):
  after_state = [0,[0,0],[0,0]]
  after_state = copy.deepcopy(state)
  if (action[0== state[0]):
    # 보트가 왼쪽에서 오른쪽으로 움직이는 행동
    if (after_state[0]==1):
      after_state[0= 2      
      after_state[1][0= after_state[1][0- action[1]
      after_state[1][1= after_state[1][1- action[2]
      after_state[2][0= after_state[2][0+ action[1]
      after_state[2][1= after_state[2][1+ action[2]
    # 보트가 오른쪽에서 왼쪽으로 움직이는 행동
    elif (after_state[0]==2):
      after_state[0= 1            
      after_state[1][0= after_state[1][0+ action[1]
      after_state[1][1= after_state[1][1+ action[2]
      after_state[2][0= after_state[2][0- action[1]
      after_state[2][1= after_state[2][1- action[2]
 
    return after_state
 
  else:
    print("@ @ @ 보트의 위치와 action의 시작 위치가 맞지 않습니다.@ @ @")
    return 0
 
# 올바른 움직임 인지 체크
def check(after_state):
  left = after_state[1]
  right = after_state[2]
  # 선교사 또는 식인종의 수가 음수이면 잘못된 것
  if (left[0]<0)or(left[1]<0)or(right[0]<0)or(right[1]<0):
    return -1
  # 선교사 또는 식인종의 수가 4를 넘으면 잘못된 것
  elif (left[0]>=4)or(left[1]>=4)or(right[0]>=4)or(right[1]>=4):
    return -1
  # 왼쪽, 오른쪽 모두 선교사의 숫자가 식인종보다 크거나 많아야함
  elif (left[0]>=left[1]) and (right[0]>=right[1]):
    return 1
  # 왼쪽 선교사의 숫자가 0일때 오른쪽의 선교사의 숫자가 3이면 정상
  elif (left[0]==0and (right[0]==3):
    return 2
  # 왼쪽 선교사의 숫자가 3일때 오른쪽의 선교사의 숫자가 0이면 정상
  elif (left[0]==3and (right[0]==0):
    return 2
  else:
    return -3
 
# 목표에 도달했을때 과정 출력
def done(list):
  print("끝!",list)
  temp = []
  num = -1
  while list:
    temp = list.pop(0)
    num += 1
    if (temp[0]==1):
      print("Moon.B.W   * * * * * 현재상태 * * * * *",num,"번째 움직임")
      print(" --------------------------------------------------")
      print("|                  ||~~~~~~~~~~||                  |")
      print("|   선교사 : %d명   ||~~~~~~~~~~||   선교사 : %d명   |"%(temp[1][0],temp[2][0]))
      print("|                  ||<->~~~~~~~||                  |")    
      print("|   식인종 : %d명   ||~~~~~~~~~~||   식인종 : %d명   |"%(temp[1][1],temp[2][1]))
      print("|                  ||~~~~~~~~~~||                  |")
      print(" --------------------------------------------------")
    
    elif (temp[0]==2):
      print("Moon.B.W   * * * * * 현재상태 * * * * *",num,"번째 움직임")
      print(" --------------------------------------------------")
      print("|                  ||~~~~~~~~~~||                  |")
      print("|   선교사 : %d명   ||~~~~~~~~~~||   선교사 : %d명   |"%(temp[1][0],temp[2][0]))
      print("|                  ||~~~~~~~<->||                  |")
      print("|   식인종 : %d명   ||~~~~~~~~~~||   식인종 : %d명   |"%(temp[1][1],temp[2][1]))
      print("|                  ||~~~~~~~~~~||                  |")
      print(" --------------------------------------------------")
  print("움직인 횟수 :",num,"번")
 
# 깊이 우선 탐색으로 솔루션 찾기
def DFS():
  global stack, visited, goal
  while stack:
    none = 0
    # 하나의 노드를 꺼내서 탐색 시작
    now_state = stack.pop()
    state = copy.deepcopy(now_state)
    # 기록
    visited.extend([now_state])
    # 보트가 왼쪽에 있는 상태
    if (now_state[0]==1):
      if (now_state == goal):
        print("탐색 성공!")
        done(visited)
        return 0
      else:
        available_action = LtoRaction()
        while(available_action):
          action = available_action.pop()
          after_state = move(now_state,action)
          can = check(after_state)
          if (can>0):
            if after_state not in visited:
              none = 1
              stack.extend([after_state])
          else:
            pass
        if (none==0):
          visited.pop()
 
    # 보트가 오른쪽에 있는 상태
    elif (now_state[0]==2):
      if (now_state == goal):
        print("탐색 성공!")
        done(visited)
        return 0
      else:
        available_action = RtoLaction()
        while(available_action):
          action = available_action.pop()
          after_state = move(now_state,action)
          can = check(after_state)
          if (can>0):
            if after_state not in visited:
              none = 1
              stack.extend([after_state])
          else:
            pass
        if (none==0):
          visited.pop()
 
# 실행
stack.extend([state])
DFS()
cs



728x90