python - 3. 선형/이진/깊이우선/너비우선 탐색, A*

 

DNA 탐색하기

어제 글에서 DNA는 뉴클레오타이드로 구성되고 A, C, G, T가 있다고 했는데

뉴클레오 3개를 모은걸 코돈이라하고 이 코돈찾는걸 하는 내용

 

뉴클레오타이드 - 인트이넘

코돈 - 이넘3개 튜플

유전자 - 코돈 리스트

 

 

한번 출력하면 잘 나온다.

 

코돈 선형탐색

선형탐색 처음부터 끝까지 존재하는지 순서대로 매칭

ACG 코돈은 있지만 GAT 코돈은 없댄다

 

 

코돈 이진 탐색

이진탐색

1. 이진탐색 일단 탐색할 요소가 이미 정렬되어있는 상태여야하고,

2. 구성 요소의 중간과 탐색 값을 비교 탐색값이 작으면 중간 왼쪽들과, 크면 오른쪽들과 다시 수행

3. 왼쪽 혹은 오른쪽 녀석들의 중간값과 탐색 요소 크기 비교 쭉쭉죽..

 

 

 

 

 

미로를 이용한 탐색

이번에는 깊이/너비우선 탐색, A* 등 탐색 알고리즘을 다루는데,

우선 미로부터 만들자.

미로 한칸 한칸인 셀을 Enum으로 만들고

미로 상 위치를 나타내는 메이즈 로케이션 클래스를 네임드 튜플로 만들자.

 

미로 클래스를 만들고

한번 출력시켜보면 이쁘게 나온다.

 

 

추가로 미로의 골인지, 현재 위치에서 이동가능한 곳을 반환하는 메서드를 만들자

 

 

 

깊이우선 탐색

아래로 쭉쭉 가다가 막히면 한칸 올라와서 다시 탐색하는 방법. 스택을 쓴덴다.

 

 

잠깐 파일을 바꿔서 generic_search.py에 스택 구현

 

위 코드를 보면 @property 데코레이터가 있는데 개념은

자바에서 배운적있는 게터 세터같은거라고 한다.

@property를 쓰면  get_empty 대신 그냥 empty로 개터 역활을 하는거란다.

 

여기 블로그 내용이 좀 이해하기 쉬웠다.

https://cocook.tistory.com/103

[Python] @property 너 누구야? 후아유

 

 

 

스택에 이어서 노드 클래스도 구현하자.

Optional은 매개변수가 있으면 해당 타입 값을 쓰고 없으면 None이 들어갈수도 있다? 라고한다.

여기서 노드는 메이즈 로케이션을 감싸는 레퍼인데, 코스트와 휴리스틱 값을 가지고 있으며

상태 변화를 추적하기 위해서 필요하다는데 아직은 잘 모르겠다.

 

 

잠깐 찾아봤는데

Optional, Callable 등 타이핑 모듈에 있는 메서드들 잘 설명한 글이 있어서 링크 가져왔다.

https://www.daleseo.com/python-typing/

[파이썬] typing 모듈로 타입 표시하기

 

 

 

중간에 자꾸 에러나서 왜그런가 찾아보다가

from __future__ import annotations을 빠트린게 문제였다.

그와 관련된 내용을 여기서 잘 설명해주고 있다.

 

https://ryanking13.github.io/2018/07/12/python-37-whats-new.html

파이썬 3.7의 새로운 기능들

 

dfs 함수와 node_to_path 함수 정의하고

 

 

 

 

 

maze 클래스에 mark, clear 함수와

메인 루틴 구현, 오타 고치고 돌리면

 

결과가 잘나오긴 한데 경로가 조금 이상한거같다.

 

dfs 함수부터 보면.. 시작점 위치(MazeLocation)와 메이즈로케이션을 인자로받아 불리언을 반환하는 goal_test(), 메이즈로케이션 인자로받아 이 자료구조의 리스트를 반환하는 석세서 함수를 인자로받아. 노드를 리턴해준다고하는데..

 

방문한 장소 frontier 스택을 만들어 초기 장소 노드 푸시

스택이 안비워져 있으니 프론티어 팝으로 노드 꺼내고,

현재 노드 상태도 가져오고 current_state 

골테스트도 하고

아니면 현재 상태에서 석세서스로 가능한 곳있나 보고

-이미 방문한곳은 pass

-explored는 쓸때없어 보이긴한데 추가하고.

-프론티어에 자식(메이즈 로케이션)과 현재 노드 상태(지금 메이즈로케이션)  푸시

다시 와일문으로 돌아가서 쭉쭉하면 지금 결과가 나오는거같다.

 

 

 

다시 왜 이런 결과가 나왔는지 생각해보니

 

 

 

석세서스에서 아래-위-우-좌 순으로 리스트가 만들어져서

스택에 넣으면 좌-우-위-아래 순이 되어 이렇게 팝 시켜서 탐색하다보니

G 까지 빠른 경로가 아니라 자꾸 좌측으로 끝까지 갔다가 아래로 내려가는 모습을 보인거같다.

 

잠깐 보면 최대한 우측이나 왼쪽 끝에 갔다가 내려가는 모습을 보이는데, 내가 석세서스를 잘못이해한거같기도하고..

 

 

 

 

 

 

너비우선 탐색

dfs에선 스택을 썻지만 bfs에선 큐를 사용한다고 한다.

 

bfs 함수도 dfs의 stack 대신 Queue로만 바꾸면 된다.

 

dfs 돌릴떄와 마찬가지로 구현해서 돌리면

 

 

생각해보니까 옆으로 돌려서 봤어야 했더라.

dfs는 이름그대로 깊이방향으로 계속 가고,

dfs도 이름 그대로 너비(옆)방향으로 가면서 경로를 찾아내었다.

그렇다고 아까 dfs한거를 옆으로봐도

이 결과는 이해되질 않는다.

가아니라..

깊이 방향 우선이니 이럴수도 있겠다 싶네.

 

 

 

이번에는 astar 알고리즘

- 비용함수 g(n)와 휴리스틱 함수 h(n)로 가장 가능성 있는 경로 중심으로 탐색한다.

- 비용함수 g(n)는 특정지점까지 도달하는데 걸리는 비용

- 휴리스틱 함수 h(n)는 해당 위치에서 목표지까지 비용

=> 총 비용 f(n) = g(n) + h(n)

인데 현재 위치까지 오는데 비용이랑 목표까지 비용을 합친게 f(n)이 되겠다.

그리고 다음 경로 석세서스를 선정할때 f(n)이 가장 낮은걸 고른다.

 

 

astar 알고리즘 구현하기 위해 우선순위 큐 사용.

큐다보니 순서데로 가긴하는데.

우선순위 큐라 순서가 같은 경우 우선순위가 높은것 부터 꺼내서 쓴다.

 

이 우선순위 큐를 리스트와 힙큐로 만드는데..

힙큐 링크

 

https://littlefoxdiary.tistory.com/3

[Python] 힙 자료구조 / 힙큐(heapq) / 파이썬에서 heapq 모듈 사용하기

힙큐 푸시와 힙큐 팝을 할때

Node 클래스의 __lt__() 메서드로 비교해서 푸시, 팝이 이뤄진다고한다.

 

 

이번에는 휴리스틱 함수 만드는데

비용 함수는 현재 지점까지 비용

휴리스틱은 현재지점에서 목표지까지 비용.

미로 찾기 예제에서 휴리스틱 함수로 맨해탄거리랑 유클리드 거리를 쓰는데 여기선 맨해탄 거리 쓴다.

 

이제 에이스타 함수를 보자

dfs, bfs랑 거의 동일한데 아직 방문하지 않은 곳, 탐색하려는 곳을 담는 변수 프론티어를 우선순위 큐로 쓰는데..

프론티어 팝으로 가장 우선순위가 높은 곳을 꺼낼것이고.

석세서스로 우선순위 높은 곳에서 갈 곳을 루프 돌며 보는데.. 

다음 장소 비용은 현재 장소 + 1하고,

탐색하지 않은 장소 child가 있거나 이미 탐색했더라도 갈수있는 장소의 새 코스트가 크다면(?)

익스플로드 추가하고,

다음 으로 갈 노드(자식 노드, 현재 노드, 새 비용, 자식노드기준 휴리스틱함수)를 프론티어에 푸시한다. 

우선순위 큐 프론티어가 비워질때까지 계속 반복하다가 목적지 오면 끝

 

 

잠깐 Node 클래스를 다시보면

lt에서 총 비용 = 비용 + 휴리스틱 값을 기준으로

우선순위 큐에서 푸시 팝 한다.

총 비용함수를 이용한 우선순위 큐 자료구조를 써서 a* 알고리즘을 구현한 결과

dfs처럼 깊이방향으로 오르락 내리락도

bfs로 쭉 좌우 하지도 않고,

가장 적당하게 빠른길을 찾아간다.

 

분량은 길지 않은데

진짜 진행하기 힘드네