장거리 최적경로탐색을 위한 부분탐색기법 연구

배상훈(Bae Sanghoon) 대한토목학회 2006 대한토목학회논문집 D Vol.26 No.3D

실시간 여행경로에 대한 정보를 제공하기 위해 동적 최적경로탐색 시스템은 실시간 경로 탐색을 통해 대다수 사용지의 요구를 충족시키는 최적경로정보를 제공한다. 따라서 동적 최적경로탐색 시스템은 주기적으로 최적경로를 갱신하여야 하므로 짧은 시간에 최적경로를 탐색하여야 한다. 이를 위해 본 논문에서는 제한적인 탐색영역 설정기법을 사용하여 빠르고 효율적인 동적 경로탐색을 가능하게 하였다. 또한 본 연구에서는 저사양의 하드웨어로도 동적 경로탐색이 가능한 기법을 개발하였다. 대표경로를 사용한 탐색영역 설정 기법으로 갱신 주기에 따른 유효 탐색영역에 대한 최적해와 대표경로를 조합한 부분해를 사용하는 부분 탐색영역 설정기법을 제안하였다. 가상의 도로망에 적용한 결과 기존의 방법에 비해 최대 50% 정도의 좁은 탐색영역으로도 최적의 경로를 탐색할 수 있었다. 또한 이동거리에 상관없이 안정적인 탐색영역을 설정할 수 있어서 단거리 이동경로 탐색이 가능한 정도의 하드웨어 성능으로도 장거리 최적경로를 탐색할 수 있었다. It is widely known that the dynamic optimal path algorithm, adopting real-time pathfinding, can be supporting an optimal route with which users are satisfied economically and accurately. However, this system has to search optimal routes frequently for updating them. The proposed concept of optimizing search area lets it reach heuristic optimal path rapidly and efficiently. Since optimal path should be increased in proportion to an distance between origin and destination, tremendous calculating time and highly efficient computers are required for searching tong distance journey. In this paper, as a result of which the concepts of partial solution and representative path are suggested. It was possible to find an optimal route by decreasing a half area in comparison with the previous method. Furthermore, as the size of the searching area is uniform, comparatively low efficient computer is required for long distance trip.

최단경로 탐색영역 축소 알고리즘 개발

유영근 한국ITS학회 2013 한국ITS학회논문지 Vol.12 No.2

탐색영역 제한에 의한 정의역 최소화 기법을 이용한 고속 프랙탈 영상복원

정태일,강경원,문광석,권기룡,김문수 한국융합신호처리학회 2001 융합신호처리학회 논문지 (JISPS) Vol.2 No.2

기존의 프랙탈 영상복원은 모든 치역 블럭에 대해 반복축소변환을 수행하므로 복원시 많은 계산량이 요구되었다. 이를 개선하기 위해 각 치역 블럭마다 반복축소변환이 필요한 영역과 필요하지 않은 영역으로 구분하는 방법이 제시된 바 있다. 반복축소변환이 필요 없는 영역을 데이타 의존영역이라 하고, 데이타 의존영역이 확장될수록 반복축소변환 영역은 줄어든다. 그래서 본 논문에서는 정의역 블록의 탐색 영역을 치역과 비슷한 영역으로 제한하여, 정의역 블럭이 더 많이 중복되도록 부호화하여 데이타 의존영역을 최대화 즉, 반복축소변환 영역을 최소화한다. 반복축소변환 영역이 최소가 되는 정의역을 정의역 최소화 기법으로 정의한다. 그래서 정의역 최소화 기법을 이용하여 프랙탈 영상 복원시 화질에 거의 영향을 미치지 않고, 반복축소변환에 필요한 계산량을 감소시켜 고속 복원이 가능하다. The conventional fractal decoding was required a vast amount computational complexity, since every range blocks was implemented to IFS(iterated function system). In order to improve this, it has been suggested that each range block was classified to iterated and non-iterated regions. Non-iterated regions is called data dependency region, and if data dependency region extended, IFS regions are contractive. In this paper, a searched region of the domain is limited to the range regions that is similar with the domain blocks, and the domain region is more overlapped. As a result, data dependency region has maximum region, that is IFS regions can be minimum region. The minimizing method of domain region is defined to minimum domain(MD) which is minimum IFS region. Using the minimizing method of domain region, there is not influence PSNR(peak signal-to-noise ratio). And it can be performed a fast decoding by reducing the computational complexity for IFS in fractal image decoding.

어린이집 만 2세 학급의 조작·탐색영역 활성화를 위한 실행연구

김희성(Kim Hee Sung),김정미(Kim Jeong Mee) 한국유아교육·보육복지학회 2016 유아교육·보육복지연구 Vol.20 No.3

The purpose of this study is to conduct the action research on manipulation and exploration area for 2year old class in the kindergarten and review the impact to the teacher and infant. Also, the ultimate purpose is to suggest an example of effective operation through the improvement in manipulation and exploration area. In this study of manipulation and exploration area, three teachers in charge of Flower class at G kindergarten participated from March 10th to July 11th, 2014. To make an improvement in the manipulation and exploration area, re-organized the physical environment of class, made a variable options of training tools to get attraction of infants, and changed the assigned time for free play class. Also, interacted with the teaching method to lead to affirmative direction and expanded the interest of infant on a specific training tool to more variable training tools, which resulted in a favorable change. The result of study First, class room is no longer a place just for stay but changed to an environment getting infant s attraction and helping infant focus on. Could observe that the infants showed their interest on manipulation and exploration area every day and willingness to participate in. Second, regarding the change of individual teacher; Teacher A was a little bit passive at the beginning of this study but became aggressive to participate in this study. Teacher B was passive in the teaching method but became self-driven in the teaching method. Lastly, I used to taking a teacher oriented teaching method but changed to infant oriented teaching method. Third, observed a change in the infant that they keep showing a curiosity on manipulation and exploration area and aggressively asking questions. Especially, infant A preferred only one teaching tool at the beginning of this study but changed to be very aggressive which also gave a good synergy impact to other infants. The study of improvement in manipulation and exploration area for 2year old infant has its meaning to draw the attraction of infants through the change of physical environment of class, effective time allocation, and interaction between teacher and infant. Also, resulted in a good change of teacher s behaviour in the teaching method. The value of this study is to suggest a basic model of the improvement in manipulation and exploration area. 본 연구는 어린이집 만 2세 학급의 조작·탐색영역의 활성화를 위한 실행연구로 조작·탐색영역의 활성화 과정을 통한 교사와 영아의 변화 양상과 교육과정 운영의 변화를 알아보고 영아에게 효과적인 운영사례에 관한 자료를 제공하는데 그 목적이 있다. 조작·탐색영역의 활성화를 위해서 2014년 3월 10일부터 2014년 7월 11일까지 총 19주 동안 G어린이집의 만 2세반 담임을 맡고 있는 3명의 교사와 만 2세영아 14명과 함께 실행연구를 실시하였다. 현장관찰, 교사면담 및 교사-연구자 협의, 교사저널, 영아 관찰일지, 사진 및 활동녹화자료, 문서자료 등을 중심으로 수집된 자료는 코딩과 범주화과정을 거쳐 분석이 이루어졌다. 연구 결과는 첫째, 형식적이었던 교실의 물리적 환경을 영아들이 집중할 수 있는 환경으로 재배치하여 영아들의 집중을 이끌어 내었다. 둘째, 조작·탐색영역의 활성화를 위해 실시한 교사면담, 교사-연구자 협의 등을 통해 교사들의 변화를 이끌었다. A교사는 소극적인 모습에서 능동적으로 연구하는 교사의 모습으로 B교사는 자신감이 없는 수동적인 태도에서 적극적으로 교수방법을 고민하는 교사로 변화하였으며 연구자는 교사 주도식 교수방법에서 영아 주도식 교수방법을 시도하는 모습으로 변화하였다. 셋째, 영아는 조작·탐색영역에 대해 스스로 탐색하고 활기차게 관심을 갖는 모습으로 변화하고 한가지 교구만 선호하던 영아도 긍정적인 변화가 이루어졌다. 본 연구는 만 2세 조작·탐색영역의 활성화 방안을 실행연구로 진행하여 교육과정운영, 교사와 영아의 변화를 긍정적으로 이끌어 내었으며 조작·탐색영역의 활성화 방안에 대한 효과적인 운영사례를 제시해 주었다는데 그 의의가 있다.

만2세 일일보육계획안의 감각 · 탐색영역 내용분석을 통한 담임교사의 반성적 사고와 인식의 변화

박수정(Park, Soo-Jung),배지현(Bae, Jee-Hyun) 한국영유아보육학회 2019 한국영유아보육학 Vol.0 No.118

본 연구의 목적은 만 2세 일일보육계획안에 나타난 감각·탐색영역의 내용을 분석하고, 분석결과를 제공하여 담임교사의 반성적 사고와 인식의 변화를 돕는 것이다. 만 2세 교사6인의 일일보육계획안을 분석한 결과, 첫째, 만 2세 일일보육계획안 감각 · 탐색영역의 오감별 분석결과는 ‘시각’이, 주제별로는 ‘신나는 여름’이, 활동유형별로는 ‘수 · 조작’활동이 가장 다수로 나타났다. 둘째, 일일보육계획안 분석결과를 본 만 2세반 교사 6인들은 감각 · 탐색영역을 수 · 조작 교구를 비치해주는 공간 정도로 생각하고 있었던 점, 오감중심의 감각교육이라 하면서도 시각, 촉각활동만을 사용하였던 점 등을 반성하였다. 또한 다양한 개선방안을 스스로 마련하고 반성적 교수를 수행하였다. 본 연구의 시사점은 교사의 일일보육계획안의 분석결과가 의미있는 반성적 인식과 교수 자료로 활용될 수 있다는 점, 현장의 감각 · 탐색영역 운영상의 편중과 개선방안을 밝힌 점이다. This research aims to analyze contents in the ares of sensory and exploration presented in the daily nursery care daily teaching plan for two-year-old children and assists the reflective thinking of childcare teachers. The findings of the study are as follows: First, an analysis of the daily teaching plan for six childcare teachers with two-year-old children suggested that ‘visions’ including ‘exciting summer’ rated the most while the activity type included ‘number and operation’ activity rated the most. Second, the six childcare teachers with children reflected the areas of sensory and exploration as a mere space that presents teaching aid for the number and the operation, and used only visionary and touch sensation despite the sensory education of five senses. Third, the six childcare teachers performed reflective teaching by coming up with various improvements by themselves. This study contributes to the literature by utilizing the results of daily nursery care programing as meaningful reflective consciousness and teaching material and revealing the overvaluation of the areas of sensory and exploration in a field operation.

어린이집 만 2세 학급의 조작․탐색영역 활성화를 위한 실행연구

김희성(Kim, Hee Sung),김정미(Kim, Jeong Mee) 한국유아교육·보육복지학회 2016 유아교육·보육복지연구 Vol.20 No.3

본 연구는 어린이집 만 2세 학급의 조작․탐색영역의 활성화를 위한 실행연구로 조작․탐색영역의 활성화 과정을 통한 교사와 영아의 변화 양상과 교육과정 운영의 변화를 알아보고 영아에게 효과적인 운영사례에 관한 자료를 제공하는데 그 목적이 있다. 조작․탐색영역의 활성화를 위해서 2014년 3월 10일부터 2014년 7월 11일까지 총 19주 동안 G어린이집의 만 2세반 담임을 맡고 있는 3명의 교사와 만 2세영아 14명과 함께 실행연구를 실시하였다. 현장관찰, 교사면담 및 교사-연구자 협의, 교사저널, 영아 관찰일지, 사진 및 활동녹화자료, 문서자료 등을 중심으로 수집된 자료는 코딩과 범주화과정을 거쳐 분석 이 이루어졌다. 연구 결과는 첫째, 형식적이었던 교실의 물리적 환경을 영아들이 집중할 수 있는 환경으로 재배치하여 영아들의 집중을 이끌어 내었다. 둘째, 조작․탐색영역의 활성화를 위해 실시한 교사면담, 교사-연구자 협의 등을 통해 교사들의 변화를 이끌었다. A교사는 소극적인 모습에서 능동적으로 연구하는 교사의 모습으로 B교사는 자신감이 없는 수동적인 태도에서 적극적으로 교수방법을 고민하는 교사로 변화하였으며 연구자는 교사 주도식 교수방법에서 영아 주도식 교수방법을 시도하는 모습으로 변화하였다. 셋째, 영아는 조작․탐색영역에 대해 스스로 탐색하고 활기차게 관심을 갖는 모습으로 변화하고 한 가지 교구만 선호하던 영아도 긍정적인 변화가 이루어졌다. 본 연구는 만 2세 조작․탐색영역의 활성화방안을 실행연구로 진행하여 교육과정운영, 교사와 영아의 변화를 긍정적으로 이끌어 내었으며 조작․탐색영역의 활성화 방안에 대한 효과적인 운영사례를 제시해 주었다는데 그 의의가 있다. The purpose of this study is to conduct the action research on manipulation and exploration area for 2year old class in the kindergarten and review the impact to the teacher and infant. Also, the ultimate purpose is to suggest an example of effective operation through the improvement in manipulation and exploration area. In this study of manipulation and exploration area, three teachers in charge of Flower class at G kindergarten participated from March 10th to July 11th, 2014. To make an improvement in the manipulation and exploration area, re-organized the physical environment of class, made a variable options of training tools to get attraction of infants, and changed the assigned time for free play class. Also, interacted with the teaching method to lead to affirmative direction and expanded the interest of infant on a specific training tool to more variable training tools, which resulted in a favorable change. The result of study First, class room is no longer a place just for stay but changed to an environment getting infant’s attraction and helping infant focus on. Could observe that the infants showed their interest on manipulation and exploration area every day and willingness to participate in. Second, regarding the change of individual teacher; Teacher A was a little bit passive at the beginning of this study but became aggressive to participate in this study. Teacher B was passive in the teaching method but became self-driven in the teaching method. Lastly, I used to taking a teacher oriented teaching method but changed to infant oriented teaching method. Third, observed a change in the infant that they keep showing a curiosity on manipulation and exploration area and aggressively asking questions. Especially, infant A preferred only one teaching tool at the beginning of this study but changed to be very aggressive which also gave a good synergy impact to other infants. The study of improvement in manipulation and exploration area for 2year old infant has its meaning to draw the attraction of infants through the change of physical environment of class, effective time allocation, and interaction between teacher and infant. Also, resulted in a good change of teacher’s behaviour in the teaching method. The value of this study is to suggest a basic model of the improvement in manipulation and exploration area.

A^* 알고리즘의 최단경로 탐색 정확도 향상을 위한 역방향 적용방법에 관한 연구

유영근,박용진,Ryu, Yeong-Geun,Park, Yongjin 한국ITS학회 2013 한국ITS학회논문지 Vol.12 No.6

The studies on the shortest path algorithms based on Dijkstra algorithm has been done continuously to decrease the time for searching. $A^*$ algorithm is the most represented one. Although fast searching speed is the major point of $A^*$ algorithm, there are high rates of failing in search of the shortest path, because of complex and irregular networks. The failure of the search means that it either did not find the target node, or found the shortest path, witch is not true. This study proposed $A^*$ algorithm applying method that can reduce searching failure rates, preferentially organizing the relations between the starting node and the targeting node, and appling it in reverse according to the organized path. This proposed method may not build exactly the shortest path, but the entire failure in search of th path would not occur. Following the developed algorithm tested in a real complex networks, it revealed that this algorithm increases the amount of time than the usual $A^*$ algorithm, but the accuracy rates of the shortest paths built is very high. Dijkstar 알고리즘에 기초하는 최단경로 탐색 알고리즘의 탐색속도 향상에 관한 많은 연구들이 지속되어 왔다. 그 대표적인 알고리즘이 $A^*$ 알고리즘이다. 빠른 탐색속도는 $A^*$ 알고리즘의 장점이지만, 복잡하고 불규칙한 가로 네트워크에서 실제의 최단경로 탐색이 실패할 확률이 높다. 탐색실패란 목적노드를 탐색하지 못한 경우와 최단경로가 아닌 경로를 구축하는 것을 의미한다. 본 연구는 $A^*$ 알고리즘의 최단경로 탐색 성공확률을 높이기 위한 방법으로 일차적으로 출발노드와 목적노드 간 연결 관계를 정리하고, 목적노드에서 출발노드까지 정리된 경로에 따라 $A^*$ 알고리즘을 역으로 적용한 것이다. 이 방법은 네트워크 및 경로 부하량 특성에 따라 실제의 최단경로가 아닌 경로를 최단경로로 구축하는 경우가 발생할 수는 있으나, 경로구축의 완전한 실패는 발생시키지 않는다. 이 방법을 실제 복잡한 네트워크에 적용하여 유효성을 검증한 결과, 통상적인 $A^*$ 알고리즘의 적용보다 탐색 소요시간은 약간 증가하나, 정확성은 상당히 높아지는 것으로 분석되었다.

동일 특성 노드 제거를 통한 추상 그래프 기반의 경로 탐색 알고리즘

김지수,이지완,조대수 한국공간정보시스템학회 2009 한국공간정보시스템학회 논문지 Vol.11 No.4

Generally, Path-finding algorithms which use heuristic function may occur a problem of the increase of exploring cost in case of that there is no way determined by heuristic function or there are 2 way more which have almost same cost. In this paper, we propose an abstract graph for path-finding with dynamic information. The abstract graph is a simple graph as real road network is abstracted. The abstract graph is created by fixed-size cells and real road network. Path-finding with the abstract graph is composed of two step searching, path-finding on the abstract graph and on the real road network. We performed path-finding algorithm with the abstract graph against A* algorithm based on fixed-size cells on road network that consists of 106,254 edges. In result of evaluation of performance, cost of exploring in path-finding with the abstract graph is about 3~30% less than A* algorithm based on fixed-size cells. Quality of path in path-finding with the abstract graph is, However, about 1.5~6.6% more than A* algorithm based on fixed-size cells because edges eliminated are not candidates for path-finding. 일반적으로 휴리스틱을 이용한 알고리즘에서는 탐색 비용이 증가하는 문제가 발생할 수 있다. 휴리스틱에 의해 결정된 추정 경로에 실제 경로가 존재하지 않을 경우, 휴리스틱 가중치 값이 비슷한 2가지 이상의 경로가 존재할 경우 탐색 비용이 증가한다. 이 논문에서는 탐색 비용 증가 문제점을 해결하기 위해 추상 그래프를 제안한다. 추상 그래프는 실제 도로를 단순화한 그래프로서, 전체 지도를 고정된 크기의 그리드 셀로 나누고, 셀과 도로 정보를 기반으로 생성된다. 경로 탐색은 추상 그래프 탐색, 실제 도로 네트워크 탐색 순으로 2단계로 수행된다. 106,254개의 간선으로 이루어진 실제 도로 네트워크 데이터에 대해서 성능 평가 실험을 수행한 결과 탐색 비용 측면에서 그리드 셀 크기에 따라 그리드 기반 A*알고리즘에 비해 최소 3%에서 최대 35% 좋은 성능을 보였다. 반면에 유효 셀을 제외한 영역에 대한 탐색이 이루어지지 않기 때문에, 생성된 경로의 이동 비용은 1.5~6.6% 증가하였다.

계층적 이분트리를 활용한 이진 이미지 탐색 기법

김성완 ( Sung Wan Kim ) 한국창의정보문화학회 2020 창의정보문화연구 Vol.6 No.1

공간 데이터를 표현하고 처리하기 위해 사분트리 또는 이분트리 등의 계층형 자료 구조가 사용되고 있다. 이분 트리를 선형적으로 표현하기 위해 기존에 제안된 S-트리는 이진 영역 이미지 데이터를 선형적인 이진 비트열로 표현하여 저장 공간을 크게 압축할 수 있는 장점이 있으나, 이미지의 해상도가 높아질수록 이진 비트열의 길이가 길어져 저장 공간이 늘어나고 탐색 성능이 저하되는 문제점이 발생한다. 본 논문에서는 포화 이진 트리 구조를 갖는 여러 개의 분할 이분트리를 계층적으로 구성하고 각 분할 이분트리를 2개의 선형적 이진 비트열로 표현하여 이미지 탐색에 필요한 범위를 축소하는 한편 이진 비트열 경로를 직접 탐색하지 않고 간단한 숫자 변환을 통해 수행하도록 하여 전체적인 탐색 성능을 개선하였다. 최악의 시공간 복잡도 분석에 의한 성능 평가를 통해 제안 방법이 기존의 방법에 비해 우수한 검색 성능과 공간 효율성을 보이는 것으로 분석되었다. In order to represent and process spatial data, hierarchical data structures such as a quadtree or a bintree are used. Various approaches for linearly representing the bintree have been proposed. S-Tree has the advantage of compressing the storage space by expressing binary region image data as a linear binary bit stream, but the higher the resolution of the image, the longer the length of the binary bit stream, the longer the storage space and the lower the search performance. In this paper, we construct a hierarchical structure of multiple separated bintrees with a full binary tree structure and express each bintree as two linear binary bit streams to reduce the range required for image search. It improves the overall search performance by performing a simple number conversion instead of searching directly the binary bit string path. Through the performance evaluation by the worst-case space-time complexity analysis, it was analyzed that the proposed method has better search performance and space efficiency than the previous one.

저전력 병렬탐색기법을 이용한 UWB시스템의 동기 획득

김상인,조경록 한국콘텐츠학회 2007 한국콘텐츠학회논문지 Vol.7 No.1

In this paper, we propose a new parallel search algorithm to acquire synchronization for UWB(Ultra Wideband) systems that reduces computation of the correlation. The conventional synchronization acquisition algorithms check all the possible signal phases simultaneously using multiple correlators. However it reduces the acquisition time, it makes high power consumption owing to increasing of correlation. The proposed algorithm divides the preamble signal to input the correlator into an m-bit bunch. We check the result of the correlation at first stage of an m-bit bunch data and predict whether it has some synchronization acquisition information or not. Thus, it eliminates the unnecessary operation and save the number of correlation. We evaluate the proposed algorithm under the AWGN and the multi-path channel model with MATLAB. The proposed parallel search scheme reduces number of the correlation 65% on the AWGN and 20% on the multi-path fading channel. 본 논문은 초광대역(Ultra Wideband: UWB) 신호 동기 획득을 위한 새로운 저전력 병렬 탐색기법을 제안한다. 기존의 병렬 탐색 방식은 다수의 상관기를 사용하여 동시에 탐색을 수행하기 때문에 고속의 동기 획득이 가능하지만 다수의 상관기를 사용하므로 연산량이 증가되고, 이로 인해 소비전력이 증가하는 단점이 지적되고 있다. 본 논문에서 제안된 저전력 병렬 탐색기는 상관기의 입력 신호를 일정한 간격으로 나누어 구간별로 연산을 진행한다. 구간별 연산의 결과로 다음 구간에 대한 추가연산의 진행 여부를 판단하여 시스템의 불필요한 연산 처리 과정을 제거함으로써 연산량을 최소화 한다. 제안된 병렬 탐색기와 기존의 탐색구조는 MATLAB을 이용하여 모의실험을 수행하였고, 일반적인 채널 환경과 옥내 다중 경로 페이딩 환경에서 성능을 검증하였다. 실험 결과 AWGN환경에서 약 65%, 잡음이 인가된 다중 경로 환경에서 약 20%의 연산량 감소를 확인하였다.