농부가 늑대와 염소, 배추가 강의 오른편에 있다. 배를 이용하여 강의 왼편으로 건너야 하는데, 항상 농부가 타고 늑대나, 염소, 배추 중에서 하나만 실을 수 있습니다. 그런데 농부가 없을
때는 늑대가 염소를, 염소는 배추를 먹는다.
그렇다면 코딩 테스트로 나왔을 때는 컴퓨터가 이 조건에 따라서 코드를 만들고 DFS를 통해 이 문제를 해결해보고자 한다. DFS는 Stack을 활용하여 경우의 수들을 저장했다가 경우의 수가 여러 개 나온다면 일단 마지막으로 넣은 것부터 확인하고 막히면 다시 stack에서 아직 빼지 않은 경우의 수로 돌아가 확인해보는 식으로 짠다.
위 그림과 다르게 본인은 node를 생성하기 전에 조건에 맞는지 유무부터 확인하는 알고리즘을 넣었기 때문에 빨간 줄에서 발산되는 선들은 없애고 보면 편하다.
우선 Stack을 그냥 list로 쓰고 pop, append를 쓰면 되지만
그래도 구현해보는 연습도 해볼 겸 만들어본다.
class Stack: def __init__(self): self.items = [] def stackPush(self,node): self.items.append(node) def stackPop(self): if self.isEmpty!=False: return self.items.pop() else: return def isEmpty(self): if len(self.items) == 0 : return True else: return False
Node 클래스다. 노드가 굳이 필요한 이유는 stack과 무관하게 그 path가 이어온 길을 이어줄 필요가 있기 때문이다. 처음에 DFS는 stack만 이용하면 된다고 배우게 되면 stack을 통해서 path를 만들어보려고 애쓰는데, 목표지점에 도달했을 때 다시 복기하는 역할은 node가 한다. 이걸 백트래킹이라고 하는데, 백트래킹은 다시 말하지만 stack이 아니라 node의 parent를 역으로 트래킹하면서 하는 것이다.
class Node: def __init__(self,s,
p, d): self.state = s self.parent = p self.depth = d def solutionPath(self): path = self.state print(path) #reorganized in order to hide returning None not a path if self.parent.depth == 0: return self.parent.state else: return self.parent.solutionPath()
굳이 필요한 클래스는 아니지만, 교수님께서.... 뭐 어쨋든 divide and conquer가 좋으니까.. 나라면 DFS 클래스에 넣었을 것 같다..
( + 인공지능개론 수업이어서 problem 에 대한 클래스 정의가 필수다... 왜냐하면 나중에 problem 과 같은 상황을 규정해야 heuristic 알고리즘들을 실행할 수 있기 때문이다. 고전적인 알고리즘이라면 필요없지만 인공지능 알고리즘에서 쓰기 위해 DFS
를 재사용하기 위해서 규정한다)
class Problem: def __init__(self, i, g): self.initState = i self.goalState = g def isGoal(self, s): if self.goalState == s: return True else: return False
가장 중요한 DFS 클래스는 하나씩 설명하면서 보겠다. 우선 여기서 가장 중요한 내용은 Stack()을 생성해서 frontier 라는 곳에 넣어서 언제든지 DFS 내에서
stack을 사용할 수 있도록 한다.
class DFS: def __init__(self, p): self.numberGeneratedNodes = 0 self.prob = p self.frontier = Stack()
그 후 DFS 기본은 stack에 먼저 초기화 값이 되는 root node를 넣어야 한다.
그 후는 root에서 갈라져 나올 수 있는 node들을 tree 형태 처럼 stack에 넣은 후에 마지막으로 확인한 node가 또 다시 갈라져 나올 수 있는 node들을 생성하면서 stack에 넣는 일을 루프도 돌린다. stack이 전부 빌때까지 혹은 goal 상태에 들어갔을 때 return으로 끝난다.
def solution(self): #1. root node with initial state root = Node(self.prob.initState, None, 0) #2. add the root node to frontier Stack self.frontier.stackPush(root) # while queue is not empty while not self.frontier.isEmpty(): # pop a node parent = self.frontier.stackPop() # if the node is goal, return the node if self.prob.isGoal(parent.state): return parent # expand and add them to the stack childrens = self.expand(parent) for i in childrens:
self.frontier.stackPush(i) return
갈라져 나오는 일, 즉 expand도 다른 함수로 만들어서 경우의 수를 다 children으로 만든 후 parent와 연결시킨 노드로 생성하여 stack에 넣는 일을 한다.
본인은 여기서 farmer는 무조건 움직여야하므로 farmer와 다른 동/생물 혹은 farmer가 혼자 지나가는 경우의 수들을 전부 구하고, 조건에 맞게 안전한지 혹은 이미 갔다와본 길인지를 확인하면서 node를 생성한다.
def expand(self, parent): children = [] # [0]: farmer [1]: cabbage [2]:goat [3]:wolf #check if farmer can cross with another life for i in range(1, len(parent.state)): candidate=parent.state[:] #call by value if candidate[0] == candidate[i]: candidate[0] = not
candidate[0] candidate[i] = not candidate[i] if self.isSafe(candidate) and not self.visited(candidate, parent): children.append(Node(candidate, parent, parent.depth+1)) # if the farmer can to cross by himself candidate=parent.state[:] #call by value candidate[0] = not candidate[0] if self.isSafe(candidate) and not self.visited(candidate, parent): children.append(Node(candidate, parent, parent.depth+1)) self.numberGeneratedNodes += len(children) return children def isSafe(self,node): # [0]:
farmer [1]: cabbage [2]:goat [3]:wolf if node[1] == node[2] and node[0] != node[1]: return False if node[2] == node[3] and node[0] != node[2]: return False return True def visited(self, state, parent): if not parent.parent: return False node=parent while node.parent: if node.parent.state == state: return True node = node.parent return False
이를 토대로 다음과 같이 위의 문제처럼 전부 옮기는 경우 말고도, 조건을 성립하면서도 전부 같은 자리에 안 있을 경우에도 답이 나올 수 있다.
class Stack: def __init__(self): self.items = [] def stackPush(self,node): self.items.append(node) def stackPop(self): if self.isEmpty!=False: return self.items.pop()
else: return def isEmpty(self): if len(self.items) == 0 : return True else: return False class Node: def __init__(self,s, p, d): self.state = s self.parent = p self.depth = d def solutionPath(self): path = self.state print(path) #reorganized in order to hide returning None not a path if self.parent.depth == 0: return self.parent.state else: return self.parent.solutionPath() class Problem: def __init__(self, i, g): self.initState = i self.goalState = g def isGoal(self, s): if self.goalState == s:
return True else: return False class DFS: def __init__(self, p): self.numberGeneratedNodes = 0 self.prob = p self.frontier = Stack() def expand(self, parent): children = [] # [0]: farmer [1]: cabbage [2]:goat [3]:wolf #check if farmer can cross with another life for i in range(1, len(parent.state)): candidate=parent.state[:] #call by value if candidate[0] == candidate[i]: candidate[0] = not candidate[0] candidate[i] = not candidate[i] if self.isSafe(candidate) and not self.visited(candidate,
parent): children.append(Node(candidate, parent, parent.depth+1)) # if the farmer can to cross by himself candidate=parent.state[:] #call by value candidate[0] = not candidate[0] if self.isSafe(candidate) and not self.visited(candidate, parent): children.append(Node(candidate, parent, parent.depth+1)) self.numberGeneratedNodes += len(children) return children def isSafe(self,node): # [0]: farmer [1]: cabbage [2]:goat [3]:wolf if node[1] == node[2] and node[0] != node[1]: return False if node[2]
== node[3] and node[0] != node[2]: return False return True def visited(self, state, parent): if not parent.parent: return False node=parent while node.parent: if node.parent.state == state: return True node = node.parent return False def solution(self): #1. root node with initial state root = Node(self.prob.initState, None, 0) #2. add the root node to frontier Stack self.frontier.stackPush(root) # while queue is not empty while not self.frontier.isEmpty(): # pop a node parent =
self.frontier.stackPop() # if the node is goal, return the node if self.prob.isGoal(parent.state): return parent # expand and add them to the stack childrens = self.expand(parent) for i in childrens: self.frontier.stackPush(i) return prob = Problem([False, False, False, False], [True, True, True, True] ) dfs = DFS(prob) goalNode = dfs.solution() print(goalNode.state, str(goalNode.depth) + " times boat crossed") print(dfs.numberGeneratedNodes, "nodes generated") print(goalNode.solutionPath())
print() prob2 = Problem([False, True, False, True], [True, False, True, True] ) dfs2 = DFS(prob2) goalNode2 = dfs2.solution() print(str(goalNode2.depth) + " times boat crossed") print(dfs2.numberGeneratedNodes, "nodes generated") print(goalNode2.solutionPath())
이건 GeeksForGeeks에 나온 더 간단한 코드다.
########################################################### # wgcf.py # # wolf, goat, cabbage, farmer # at each step check to see if the wolf and goat or the # goat and cabbage are left alone this is an unsafe state. # # Allan Collins #
########################################################### initial = ['W', 'W', 'W', 'W'] goal = ['E', 'E', 'E', 'E'] stack = [] stack.append(initial) ''' given a state, returns True and appends to stack if state is goal and false otherwise. ''' def nextState(state): if state == goal: return False farmer = state[3] print(farmer) #loop thru characters of state if on same side as #farmer test to see if farmer and it can be brought #across. for i, s in enumerate(state): if s == farmer: tryState =
makeState(state, i) if testState(tryState) and isUnique(tryState): stack.append(tryState) return True return False ''' returns a new state. This may be an unsafe state. The farmer always crosses and first tries to bring an item from W to E. The farmer will only bring an from east to west to avoid an item being eaten. ''' def makeState(s, i): t = [] for x in s: t.append(x) #farmer always crosses t[3] = 'E' if t[3] == 'W' else 'W' #only bring something back across the river to #avoid an unsafe
state. if t[3] == 'W': if not testState(t): t[i] = 'E' if t[i] == 'W' else 'W' else: t[i] = 'E' if t[i] == 'W' else 'W' return t ''' returns True if nothing is eaten in state s. ''' def testState(s): #check to see if something gets eaten if s[0] == s[1] and s[3] != s[0]: return False if s[1] == s[2] and s[3] != s[1]: return False return True ''' returns True if state, s is not in the stack. ''' def isUnique(s): #check to see if this state is unique. ie check for loops if s in stack: return False
return True while nextState(stack[-1]): pass for i, x in enumerate(stack): print i, x
