일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 러스트기초
- vue기초
- 계정추상화
- multicall
- 티스토리챌린지
- SBT표준
- 컨트렉트 동일한 함수이름 호출
- 스마트컨트렉트 함수이름 중복 호출
- 오블완
- 러스트 기초
- ethers websocket
- 스마트 컨트렉트 함수이름 중복
- Vue
- rust 기초
- ethers typescript
- 스마트컨트렉트테스트
- 머신러닝기초
- erc4337
- 컨트렉트 배포 자동화
- ethers type
- 러스트 기초 학습
- 스마트컨트렉트 예약어 함수이름 중복
- erc4337 contract
- ambiguous function description
- ethers
- git rebase
- Vue.js
- ethers v6
- 체인의정석
- chainlink 설명
- Today
- Total
체인의정석
A* 에이스타 (Best First Search)와 발견적 탐색(휴리스틱 서치, Heuristic) 본문
휴리스틱 탐색 (발견적 탐색)
Informed Search 현재 위치에서 목적까지 가는데 유용한 서치
휴리스틱이라고도 부른다. 휴리스틱 탐색의 예시로서
교수님께서는 딱 하나만 설명을 해주셨다. A* 에이스타 이다.
노드 확장의 순서가 주요 요지이다.
평가 함수를 가지고 제일 좋은 평가를 통해 갈 경로를 선택 : 만약 현재 상태가 g와 h 사이에 존재한다면 g와 h의 비용을 각각 계산해서 더 좋은 경로를 선택하게 된다.
이러한 f를 계속 반복해서 진행을 시켜주는 것이 Best first Seach 즉 에이스타 알고리즘이다.
이러한 f라는 함수를 지정해주기 때문에 인위적을 지정해주는 휴리스틱 함수가 포인트가 된다. 그외에도 그리디 탐색법도 설명해 주셨다.
Greedy best-first search
- 현재 상황에서 가장 좋은 것만을 찾기 때문에 최적화는 안된다.
- 한부분에서만 빠질 수 있기에 완전성은 없다.
- 시간복잡도는 DFS의 최악의 케이스지만 휴리스틱을 잘 쓰면 드라마틱하게 잘 찾게 된다.
- 공간복잡도는 모든 노드들을 다 들고 있어야 해서 크다.
- 시간, 공간 : O(b^m)
A *
각각 휴리스틱 함수인 F(n)을 전반적으로 다 돌려보고 최적을 찾아간다.
그리디와는 다르게 확장을 더 많이 해서 점프를 통해 다른 브랜치까지 왔다갔다하면서 전반적으로 추정되는 가중치를 다 고려한다.
현 시점에서 도착점 까지의 가중치를 매번 계산해서 추정치를 휴리스틱하게 계산한 후에 탐색하는 방법이다.
에이스타의 한계
에이스타의 경우에는 퀄리티를 보장하지는 않는다. addmisable (자격이 있어야)해야 나오기 때문이다.
만약 특정 점이 더 최적이고 그걸 거친 이후에 가는 결과인 optimal goal G가 있고 좀 더 비싸지만 먼 나중에 갑자기 추가가 된 suboptimal goal G2가 있다면 일단 규칙에 따라 특정 점으로만 가기 때문에 이런 경우에는 퀄리티가 보장이 되지 않는다. G2위의 단계가 있다면 거기서 고려가 되겠지만 그렇지 않다면 고려가 되지 않는다.
* 여기서 sub optimal goal 이란? 차선의 선택 값을 의미한다. 차선책을 더 빨리 선택할 수 있는 상황이라면? 중간 경로가 없다면 무조건 최선책만 탐색이 되게 된다.
해결책
여기에 따른 해결책은 2가지가 있다.
1. Extra Book Keeping : 현재 상태를 고려할 때 나중에 추가 된 것을 Extra book keeping을 통해서 같이 탐색하는 방법.
2. Consistency : 선택적 함수(휴리스틱 함수)를 만들 때 지속성을 보고 판단한다. 휴리스틱이 지속적이면 된다.
그럼 Consistency는 무엇일까? 이는 삼각형 정의와 유사한 수식이 하나 있는데
중간에 n'를 거쳐가는 길이 있고 바로 가는 길이 있다고 했을 때
중간에 거쳐가는 비용이 무조건 더 크다. (삼각형에서 거쳐가는 거리는 직선거리보다 짧을 수 없다는 것과 동일한 이치)
이 경우 지속성이 있다고 한다. 그럴 때 A*s는 그래프 서치를 해도 항상 최적의 선택을 하게 된다.
이렇게 되면 중간에 다른 선택지가 생기게 되면 이걸 그냥 날리는 식으로 처리하는 것이다.
결론
Admissable 과 Consisitency가 중요 개념
Consistent하면 Admissable한 것은 100%다.
그러나 그 반대의 경우는 100%는 아니다.
하지만 대부분의 경우에서는 Admissable 할 경우에는 지속성이 보장되는 경우가 많다고 한다.
이에 따라서 pathmax eqation을 쓰면 증진 될 수 있는데 이는 결국 휴리스틱 함수를 만들 때 양쪽 (중간 지점 포함된, 포함 안된 경로) 사이를 자체적인 계산을 통해서 최대한 비슷하게 맞춰주는 것을 의미힌다.
만약 그것조차 안되는 상황이라면 Extra Book Keeping을 해주어야 한다.
완전성 : O
최적 : O => optimally efficient : 쓸데 없는 일은 하지 않는다는 의미에서 최적이 성립니다.
시간 복잡도 : A*를 써도 exponential 한 시간 복잡도를 가진다.
공간복잡도 : 메모리에 모든 노드들 다 저장해서 사실상 가장 큰 단점이다.
결국 에이스타는 휴리스틱 알고리즘을 잘 짠다면 매우 빠르고 좋지만 문제는 메모리를 많이 잡아먹으므로 메모리에 여유가 많을 때 쓰는 것이 좋다. 또한 최적 경로가 100% 보장이라기 보다는 효율성을 기준으로 봤을때는 최적을 잘 찾아주는 느낌이다.
가중치가 부여된 A* 탐색
일반적인 휴리스틱 함수에 가중치를 두어서 하는 것인데 당연히 상황에 따라 가중치를 준다면 다른 결과가 나오게 되며 더 좋은 결과가 나올 수도 있다. 그러나 역시 여기서의 문제는 메모리 사용양이 더 늘게 된다.
그래서 RBFS와 같은 메모리의 한계를 극복하려는 여러 알고리즘이 더 나오고 있다고 한다.
'빅데이터&인공지능 > 인공지능' 카테고리의 다른 글
강화학습 알고리즘 (Two-ply game tree , Alpha-Beta purning, Monte Carlo Tree Search) (0) | 2023.10.07 |
---|---|
인공지능의 탐색방법 - Local Search (Hill Climbing Search, Simulated Annealing Search, Local Beam Search, Genetic Algorithm) (0) | 2023.09.23 |
대표적인 그래프 탐색(BFS - UCS, DFS - IDS)과 각 탐색에 대한 평가 (0) | 2023.09.16 |
머신러닝 스터디 02-선형모델(분류 편)- 다중 클래스 분류용 선형 모델 (0) | 2020.08.10 |
머신러닝 스터디 02-선형모델(회귀 편)선형회귀,릿지회귀,라쏘회귀 (0) | 2020.07.12 |