목차
1. 서론
2. 본론
(가) A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고, 균일비용 탐색이나 언덕오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라.
(1) A* 알고리즘
(2) 균일비용 탐색과의 비교
(3) 언덕오르기 탐색
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라.
3. 결론
4. 참고문헌
2. 본론
(가) A* 알고리즘의 주요 개념, 평가함수, 최소비용 탐색을 할 수 있기 위한 조건에 대하여 설명하고, 균일비용 탐색이나 언덕오르기 탐색과 어떠한 점에서 차이가 있는지 설명하라.
(1) A* 알고리즘
(2) 균일비용 탐색과의 비교
(3) 언덕오르기 탐색
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라.
3. 결론
4. 참고문헌
본문내용
함수로 사용한다. 이때, 시작 노드에서 노드 에 도달하는 비용은 고려되지 않는다. 따라서 시작 노드에서 대상 노드까지의 최적 경로를 검색하는 것은 보장되지 않는다.
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라.
[1단계]
[2단계]
[3단계]
[4단계]
3. 결론
A* 알고리즘은 주어진 출발점에서 목적지까지의 최단 경로를 찾도록 설계되었다. 최단 경로를 찾기 위해 일반적으로 사용되는 다익스트라 알고리즘과의 차이점은 A* 알고리즘이 최단 경로를 찾지 않고 최단 경로 근사치를 찾는 것을 목표로 한다는 것이다.
인접한 모든 노드를 순차적으로 방문하여 검색하는 다익스트라 알고리즘과 달리 A* 알고리즘은 적절한 휴리스틱 함수를 사용하여 숫자를 기준으로 현재 위치, 점수 및 검색을 추정한다. 정답을 포기하는 대신, 검색 속도는 다익스트라 알고리즘보다 훨씬 빠르다.
센서 노드의 컴퓨팅 성능이 A* 알고리즘과 같은 복잡한 알고리즘 연산을 수행하기에 여전히 부족하다. 그러나 기술이 발전하고 센서 노드가 컴퓨팅 파워를 높임에 따라 복잡한 알고리즘이 완전히 적용되고 더 나은 알고리즘으로 개발될 수 있다. 관련 기술은 계속 발전하고 있다. A* 알고리즘으로 적용할 경우 더 나은 성능을 얻을 수 있으며 관련 연구를 더욱 발전시킬 수 있다.
4. 참고문헌
김종석,이형옥,Kim Jong-Seok,and Lee Hyeong-Ok. \"An Algorithm for One-to-One Mapping Matrix-star Graph into Transposition Graph.\" 한국정보통신학회논문지 18.5 (2014): 1110-1115. (http://www.riss.kr/link?id=A101324902)
Kang Nam Kyu,Son Ho Joon,and Lee Soo-Hong. \"Modified A-star algorithm for modular plant land transportation.\" JOURNAL OF MECHANICAL SCIENCE AND TECHNOLOGY 32.12 (2018): 5563-5571. (http://www.riss.kr/link?id=A107435083)
Zhanying Zhang,and Ziping Zhao. \"A Multiple Mobile Robots Path planning Algorithm Based on A-star and Dijkstra Algorithm.\" International Journal of Smart Home 8.3 (2014): 75-86. (http://www.riss.kr/link?id=A100127950)
Skiena, Steven S. Programming challenges. 서울: 한빛미디어, 2004. (http://www.riss.kr/link?id=M9416441)
서우진. \"A* 알고리즘의 하드웨어 구조 설계.\" 국내석사학위논문 경북대학교 대학원, 2010. 대구 (http://www.riss.kr/link?id=T11972112)
(나) A* 알고리즘을 이용하여 최단길이 경로를 구하는 과정을 보여주는 탐색트리를 구하라.
[1단계]
[2단계]
[3단계]
[4단계]
3. 결론
A* 알고리즘은 주어진 출발점에서 목적지까지의 최단 경로를 찾도록 설계되었다. 최단 경로를 찾기 위해 일반적으로 사용되는 다익스트라 알고리즘과의 차이점은 A* 알고리즘이 최단 경로를 찾지 않고 최단 경로 근사치를 찾는 것을 목표로 한다는 것이다.
인접한 모든 노드를 순차적으로 방문하여 검색하는 다익스트라 알고리즘과 달리 A* 알고리즘은 적절한 휴리스틱 함수를 사용하여 숫자를 기준으로 현재 위치, 점수 및 검색을 추정한다. 정답을 포기하는 대신, 검색 속도는 다익스트라 알고리즘보다 훨씬 빠르다.
센서 노드의 컴퓨팅 성능이 A* 알고리즘과 같은 복잡한 알고리즘 연산을 수행하기에 여전히 부족하다. 그러나 기술이 발전하고 센서 노드가 컴퓨팅 파워를 높임에 따라 복잡한 알고리즘이 완전히 적용되고 더 나은 알고리즘으로 개발될 수 있다. 관련 기술은 계속 발전하고 있다. A* 알고리즘으로 적용할 경우 더 나은 성능을 얻을 수 있으며 관련 연구를 더욱 발전시킬 수 있다.
4. 참고문헌
김종석,이형옥,Kim Jong-Seok,and Lee Hyeong-Ok. \"An Algorithm for One-to-One Mapping Matrix-star Graph into Transposition Graph.\" 한국정보통신학회논문지 18.5 (2014): 1110-1115. (http://www.riss.kr/link?id=A101324902)
Kang Nam Kyu,Son Ho Joon,and Lee Soo-Hong. \"Modified A-star algorithm for modular plant land transportation.\" JOURNAL OF MECHANICAL SCIENCE AND TECHNOLOGY 32.12 (2018): 5563-5571. (http://www.riss.kr/link?id=A107435083)
Zhanying Zhang,and Ziping Zhao. \"A Multiple Mobile Robots Path planning Algorithm Based on A-star and Dijkstra Algorithm.\" International Journal of Smart Home 8.3 (2014): 75-86. (http://www.riss.kr/link?id=A100127950)
Skiena, Steven S. Programming challenges. 서울: 한빛미디어, 2004. (http://www.riss.kr/link?id=M9416441)
서우진. \"A* 알고리즘의 하드웨어 구조 설계.\" 국내석사학위논문 경북대학교 대학원, 2010. 대구 (http://www.riss.kr/link?id=T11972112)
소개글