*민* 스토어

*민*

개인인증

팔로워0 팔로우

소개

등록된 소개글이 없습니다.

전문분야 등록된 전문분야가 없습니다.

판매자 정보

학교정보

입력된 정보가 없습니다.

직장정보

입력된 정보가 없습니다.

자격증

입력된 정보가 없습니다.

판매지수

판매중 자료수

17개
전체 판매량

176개
최근 3개월 판매량

0개
자료후기 점수

평균A
자료문의 응답률

-

전체자료 17개

ITS(지능형교통시스템) 관련 업무 지원 자기소개서

자 기 소 개 서성 명 :■ 성장과정2남중 첫째로 서울에서 태어나 지금까지 본인의 책임을 다하는 마음가짐과 노력을 게을리 하지 않는 것을 아주 중요시 하시는 부모님의 교육하에 자랐습니다. 학교 재학시절 학급 임원과 동아리 회장직을 맡으면서 그 책임감에 대하여 몸소 느끼고 배웠으며, 다른 사람들과의 융화과정 및 협동하는 노력과 기술 등등을 배웠습니다. 또한 여러사람과 대외활동을 하면서 다른 사람을 배려하며 살펴볼 수 있는 마음가짐들도 배우면서 학교생활을 보냈습니다.가족들과는 대화를 가장 중요시 하시는 어머님의 교육방침으로 인하여 서로 섭섭하고 속상한 마음까지도 솔직히 이야기하고 소통할 수 있는 시간을 종종 가지고 있으며, 현재는 서로의 일상으로 바쁘고 힘든 와중이지만 1~2주에 한번은 가족들과의 이야기 시간을 가지면서 서로의 생각과 마음을 소통하고 있습니다.■ 성격 및 생활신조매우 활동적이고 사교적인 편이며, 사람들 앞에 나서는 일도 자신있지만 리더를 적절히 보조하고 지원하는데 뛰어난 편이며, 상황에 따라 적당히 사람들을 집중하여 융화시키는 것에 저의 성격과 장점이 있습니다. 사진동호회나 여행동호회 등의 사회활동도 주기적으로 참여하면서 가족과 회사생활 뿐이 아닌 사회구성원으로서의 활동도 활발히 하고 있습니다.사람들과의 어울림 또는 회사에서 업무를 진행할때 내가 현재상황에서 제일 잘 할 수 있는 것이 무엇인가, 그리고 내가 어떻게 무엇을 해야하는가를 먼저 파악하고 행동으로 옮기고 있습니다. 무조건 목적에 따른 결과만을 생각하는것이 아니냐는 질문도 받지만, 본인의 생각을 행동으로 옮기기 위함과 동시에 구성원으로 본인이 소속된 단체가 원활히 운영되기 위해서 필요한것은 명확한 상황판단과 그에 따른 행동의 추진력이 저는 가장 중요하다고 생각합니다. 따라서 회사조직, 동호회 모임등에서 제가 할수있는 상황판단과 행동력으로 지금까지 그렇게 진행하여 왔습니다.■ 특기사항학부때 해외탐방 지원을 시작으로 하여 현재까지 국내외로 많은 여행을 다녀온 경험이 저의 제일 장점이라고 할 수 있겠습니다. 우리나라같이 작은 국토에서 수도권에만 집중된 인구 및 기반시설에 대하여 최적의 대안을 낼 수 있는 방법중에 하나로서 국내외 많은 교통시설 및 환경을 보고 느끼는 것도 중요하다고 생각합니다. 많은 경험은 아니겠지만, 그간의 저의 경험을 바탕으로 여러 가지 많은 대안을 제시할 수 있을 것이라 생각합니다.또한, 사진을 찍는 저의 취미생활이 일상의 세세한 모습에서부터 넓은 모습의 풍경까지 많은 부분을 볼 수 있는 시선을 가지게 되어, 회사에서 업무를 진행할때에나 기타 다른 일을 추진함에 있어서 작은 부분과 넓은 부분을 동시에 볼 수 있는 시각과 마음가짐으로 일을 진행 할 수 있다고 자부합니다.■ 지원동기 및 향후계획고등학교 2학년때 심시티라는 게임으로 도시공학과라는 학문을 처음 접하게 되면서 대학을 진학하였고, 시뮬레이션 분석툴을 다루면서 교통공학으로 대학원 진학을 결정하게 되었습니다. 대학원에서 교통운영 및 ITS 관련 수업을 수강하면서 많은 시뮬레이션 분석을 해보았으며, 교수님과의 연구과제를 진행하면서 설계 및 교통전략 부분에서도 적지 않은 경험을 해보았습니다. 이로인해 도로, 차량, 철도 등의 시설위주가 아닌 운영위주의 교통분야를 접하게 되었고, 제가 설계하고 운영하는 교통시스템을 꼭 한번 구축하여 보고 싶은 욕심과 목표가 생겼습니다.

취업| 2013.12.30| 2페이지| 3,000원| 조회(114)

교통, IT, ITS, 지능형교통

미리보기

닫기
신도시개발의 특징 및 문제점

신도시개발1. 시대별 신도시개발 특징)시 기신 도 시주 요 특 징제1기(1972 - 1981)안산, 구미, 창원, 여천?산업기반 구성의 목표?수도권, 대구권, 부산권, 광주권 4대 권역에 대규모 신공업도시 건설제2기(1982 - 1991)목동신시가지, 상계신시가지, 분당, 일산, 중동, 평촌, 산본?주택부족문제 해소?정주환경 개선 목표?대단위 주택단지 건설제3기(1992 - 현재)판교, 화성, 김포, 파주 신도시?지방 신도시 건설?국토 난개발 해소?국토의 균형발전, 수도권의 분산화?남북 교튜협력지대의 조성2. 신도시개발의 문제점)① 자족성의 결여? 대학, 산업단지 등 고용 촉진 자족시설유치 미흡? 도시 특성화 산업 개발 미흡② 기반시설의 부족? 교통시설(도로, 철도, 지하철 등) 충분치 못한 공급이 교통체증문제 발생? 광역교통개선대책 수립 요구③ 고밀화된 획일적 주거환경? 고층, 고밀의 아파트로만 구성? 단조롭고 획일적인 주거환경3. 신도시개발 계획기준)분 류계 획 항 목계 획 목 표경제적 지속성도시경제의 발전?고용창출 및 도시경제의 활성화미래 개발공간 설정?미래도시의 개발수요 대처도시안전방재?자연재해예방을 위한 유수지 조성환경적 지속성지속가능한 토지이용?지속가능한 밀도 설정접근성제고?차량이용 최소화 및 보행성 향상자연순응형 개발?기존지형보존 최대화?보전경사지역선정?자연순응형 경관계획교통 및 통신체계대중교통체계 확립?대중교통시스템구축(녹색교통)?모도시와 개발지역을 공공교통중심으로연계하여 개발보행친환경적인 공간구조?보행친화적 환경구축?초등학교/대중교통시설/도시중심지까지 보행?접근성 확보?차량속도 저감환경친화적 주차계획?Car Free Zone 설정?다양한 주차시설 계획(지상주차비율 저감방법)지속가능한 통신체계구축?지능형 교통/통신 시스템 구축지속가능한 에너지 및 자원 이용에너지 절약?에너지 절약적인 도시조성자연에너지 이용?CO2 저감, 지구온난화방지수자원의 효율적이용?수자원 절약 및 순환폐기물 재활용?자원 절약 및 순환생태적 환경조성공원녹지 확충계획?공원녹지 확보 및 녹지축 구축자연환경보존?생태적 공원조성?생태복원 및 녹화?생물서식공간 조성?생태연결로 확보청정환경조성?오폐수 처리?대기질 저감대책?정온환경의 조성4. 신도시개발 시 필요한 점① 단계적이고 순차적인 개발의 필요: 신도시개발은 범위가 큰 개발임으로 하나의 큰 마스터플랜 하에 순차적으로 개발을 지속적으로 해야 함.② 지역주민과의 교류를 통한 개발의 필요: 신도시개발은 새로운 하나의 개발이기는 하나 지역 내 살고 있는 주민들의 의견 수렴을 통한 개발이 되어야함.③ 획기적인 테마를 이용한 개발의 필요

공학/기술| 2007.05.07| 3페이지| 1,000원| 조회(742)

신도시, 문제점, 계획, 특징, 필요성

미리보기

닫기
정책적 측면을 고려한 신도시개발

Report정책적 측면을 고려한 신도시개발과 목 명 :신도시 개발학 번 :이 름 :제 출 일 :담당교수 :Ⅰ. 서 론정책적 측면을 살펴보기 전 한국의 신도시개발의 성과와 현재 신도시 개발의 문제점(과제)에대하여 간단히 살펴본 후 향후 신도시가 나아가야 할 방향을 제시해 보고 본인이 생각하는신도시에 대하여 기술하는 방향으로 진행Ⅱ. 신도시 개발의 성과 및 문제점1. 신도시 개발의 성과가. 산업화 추진의 공업도시건설에서 부터 1980년대 중반 이후 주택부족 등 대도시가직면하는 도시문제를 해결하기 위한 수단으로 새롭게 전개나. 수도권 5개 신도시가 비록 침상도시(bed town)적인 면이 많다고 하더라도 수도권공간구조에 많은 영향을 미쳤으며, 앞으로도 공간구조 재편에 기여할 것으로 기대다. 2000년대에 들어와 수도권 인구분산과 국가균형발전을 위한 수단으로 그 활용성이더욱 기대됨라. 1980년대 후반에 수도권의 5개 신도시 건설을 경험한 후 2000년대에 들어와 추진하는신도시에 대해서는 자족성 확보 및 쾌적성 제고를 위한 노력을 특히 강조2. 신도시 개발의 해결과제가. 신도시개발의 부정적 사회효과에 대한 근본적 대책 필요(1) 개발자의 개발이익에 대한 공공환수- 신도시개발의 사업시행자가 개발과정에서 이루어지는 기존 토지에 대한 용도변경에대해 제 3자적 입장에 있는 일반 시민들이나 시민단체는 이를 통해 개발사업 시행자가특혜를 누리는 것이 아닌가 하는 의구심을 갖는 것이 일반적- 8.31대책으로 부활되는 개발부담금제가 개발이익환수의 법적 근거는 되나 개발이익산정에 대한 합의는 여전히 용의치 않음(2) 일반적으로 개발 사업지구 주변의 토지는 토지가격 상승으로 개발이익을 누리게되는데 이는 사회 형평성에 저해됨- 이는 주변지역이 앞으로 개발행위허가나 사업인가가 추가로 이루어질 가능성이 높고주변지역의 현재 토지이용상황에서 보더라도 신도시개발 지구의 도시기반시설을무임승차로 이용할 수 있기 때문(3) 대도시 주변에 개발계획이 여기 저기 수립되면서 주변의 모든 토지에 개발 기대심리가확산되며, 이에 따른 광범위한 지가상승은 필연적으로 경제활동의 생산비용을 증가시킴- 특히 부지를 많이 사용하거나 영세한 제조업체 일수록 공장용지의 부담이 늘어나생산 활동에 어려움을 겪게 됨나. 자족성 및 삶의 질 제고와 정주체계 형성기여에 소극적(1) 직주균형의 도시개발이 이루어지지 않아 직주 불균형이 심화- 통근권이 서울 도심에서 50㎞ 가까이로 확대되고 있음- 기존의 공장들은 택지개발에 편입 수용되어 버리고, 공장들은 마땅히 수용할 만한곳도 부족함- 복합기능의 신도시 개발을 만들어가는 데 있어 제조업체에 대한 용지공급 및 확보는매우 중요하나 택지와 함께 제조업 관련 용지를 조성하여 적정가격으로 공급하는 것이용이하지 않음(2) 주변과 단절된 형태로 개발되고, 전면매수 방식에 의한 지구계 설정은 기존 취락을배제하며, 지역일원을 고려치 않고 단위 지구별의 중심지 개발(3) 공급자 편의 위주로 신도시가 개발- 사업자 입장에서 가처분 용지를 최대한 많이 확보하고, 매각하기 편하게 부지를획일적으로 분할하여 보행동선도 직선으로 단조롭게 되며, 용적률 등도 매각을용이하게 하는데 초점다. 계획적 개발체제가 미약(1) 현재 운용되고 있는 계획적 개발체제의 근간은 도시기본계획 → 도시관리계획 →도시개발사업의 형태로 수직 하향적 접근을 기본- 도시기본계획 : 수립 초기부터 시가화예정용지 등 개발 가능토지에 거품가격을 일으킴- 도시관리계획 : 개발할 수 있는 행위의 범위를 정하여 토지이용을 잘 관리하는 것이본래의 역할이지만 구체적 행위가 계획되기도 전에 허용범위를 완화하게 되면 지가상승으로 토지소유자에 우발이득 발생을 초래하게 된다.- 도시기본계획과 개발계획과의 관계, 도시관리계획과 개발계획과의 관계 재정립이 필요(2) 계획과정에서 지자체나 관계기관과 협의하는 체제가 미흡- 광역차원의 지자체간 협의 부재로 신도시 개발 사업에 차질- 곳곳의 택지개발사업이 진입로, 농지전용협의, 환경문제 등으로 마찰을 받고 있음- 이러한 문제에도 불구하고 광역도시계획 관점의 신도시 개발에 대한 방침이 결여(3) 신도시 개발 사업을 10~20년 이상 장기적으로 경영하는데 미숙함- 협의과정이 길어지면 개발계획은 점차 장기화되어 갈 수밖에 없음(4) 전면매수의 토지취득 방식의 개선이 필요함- 도시를 만들어가는 데는 항상 협력이라는 원칙을 생각하는 것이 중요하므로 전면매수와환지방식의 적절한 절충이 필요함라. 문제점 종합(1) 신도시건설은 광역적 효과가 있는 정책수단임에 불구하고도 실제에 있어서는 광역도시계획을 통해 신도시 건설을 추진한 경험은 별로 없음(2) 성장 가능성에 대한 대비도 미흡하고. 기반시설 무임승차에 대한 주변지역 관리체제도 허약(3) 도시계획에 의한 우발이익과 우발손실의 발생은 지역공동체의 형평성을 훼손하고다음 세대에 토지비 부담을 증대시킴Ⅲ. 향후 신도시 개발이 나아가야 할 방향1. 사회구조를 고려한 신도시 개발방향 설정가. 다원화 된 사회에서 도시용지를 공급하는 것에서 벗어나 삶의 질을 중시하는 가치관변화와 자연생태 및 사회?문화자원을 조사, 분석하여 합리적 계획과정을 통하여 개발을추진해가는 개발체제가 필요2. 우발이득 발생방지와 개발이익 환수가. 개발권의 개념을 명확히 하여 개별토지의 토지용도 및 건축물 용도의 변경, 개발연면적증대 등은 사회적인 것임을 인식나. 이를 전제로 개발자에게 계획을 인허가 할 경우 개발이익 추정과 개발부담금, 기반시설부담금 부과의 규칙이 설정되어야 함다. 개발자의 개발이익환수 방식이 공론화 되고, 마련되어 공공과 민간이 협력자로 도시개발을추진할 수 있어야 함3. 삶의 질 제고와 정주체계 형성가. 고밀도 도시형에서 저밀도 농촌형 등의 주거양식의 다양화나. 기존의 주민공동체와 인근의 개발 지구를 포함하여 지역 커뮤니티 차원의 네트워크

공학/기술| 2007.05.07| 5페이지| 1,000원| 조회(319)

개발, 신도시, 수도권, 신도시개발, 공간구조

미리보기

닫기
최단경로 Moore Tree 알고리즘

Shortest Path - Moore Tree algorithm -교 과 목 : 교통체계분석제 출 일 : 2006년 6월 26일Ⅰ 서론1. 개요최단경로탐색 알고리즘(Shortest Path Finding Algorithm)은 교통수요 분석은 물론 경로 안내 시스템에서 가장 중요한 요소 중의 하나로서, 출발지와 목적지 사이에서 가장 경제적이고 실현 가능한 경로를 찾고자 하는 것이다.이와 같은 최단경로탐색 문제는 이미 1950년대 Ford(1956)와 Bellman(1957)의 알고리즘을 기반으로 하여 Moore(1957)와 Dijkstra(1957)에 의해 그 기틀이 다져졌으며, 그 이후 많은 휴리스틱(heuristic)한 알고리즘들이 제안되어왔다.2. Tree & Vine building AlgorithmTree building Algorithm은 출발 node부터 다른 node들로 경로를 전개할 때 한 개의 이전 경로(predecessor link)에 대한 정보만을 이용하는 방법을 말하는데 그 구조에서 loop)형태를 볼 수 없는 것으로 크게 Moore, Dijkstra, D'Esopo Algorithm이 있다.이러한 Tree building Algorithm은 표지정정기법(label-correcting method))의 일종이며 주어진 기점에서 네트워크상의 모든 도달 가능한 node까지의 최단경로를 찾아내게 된다.Vine Building Algorithm은 Tree에서의 전노드()의 단계를 확장하여 전전노드()까지 고려함으로서, 임의의 노드까지 여러 개의 경로를 허용하게 하게 하는 최단경로 탐색알고리즘으로, 도시가로망에서 존재할 수 있는 좌회전 금지, U-turn, P-turn 등을 반영한 정확한 최적경로의 탐색이 가능하다.[ 표 1-1 ] Tree와 Vine의 비교구 분Tree Building AlgorithmVine Building Algorithm특 징출발노드로부터 임의의 다른 노드까지 단 1개의 경로만을 허용 (최단경로상의 모든 노드의 유입차수가 알고리즘을 통해 각 종점까지 연결되는 단 하나의 경로만 존재할 경우, 이를 최소비용수형망(minimal cost tree) 또는 간간히 수형망(tree)이라 하 고 이런 종류의 알고리즘을 tree building algorithm이라 한다.최단경로 탐색시 전노드만을 고려하는 것으로 이는 링크비용만이 고려된다?h (home) : 기점이 되는 시점 node (origin node)?Next : 판단단계에서의 분석의 중심 대상이 될 node?Working table L : tree building 과정에 따라 해당하는 node를 진입시키는데 사용하는 table을 말하며 loose-ends table이라고도 한다.?Tree table R : network에 있는 모든 node에 대한 선행노드 번호, 시점부터 해당 node 까지의 비용 등에 대한 값을 담고 있는 table?network table A : network를 구성하는 모든 link에 대한 기?종점 node 번호 및 비용 등에 대한 값을 담고 있는 table?predecessor link (선행링크) : node,,가 서로 연결되어 있을 때, link(,)를 link (,)의 predecessor link 라고 한다.?predecessor node (선행노드) : link(,)에서 node를 node의 predecessor node라고 한다.?: 시점부터 node까지의 최소비용?: 시점부터 node까지의 잠정적인 최소비용, 최종적인값은와 같다.?: node의 선행 node?C next k : next 노드에서노드까지의 링크 비용3) 진행방법○ 1단계 ( Step 1 : 초기화 Initialization )- tree table R에서 모든 node에 대해서=0,=로 그리고=0 로 초기화 한다.여기서에는 h에서 다른 node까지 가능한 실제 비용보다 훨씬 큰 수를 넣는다.- L을 초기화하고 출발노드 h를 등록시킨다.- Next를 출발노드 h로 설정한다. (next는 2단계에서 진행될 tree 구축과정에서 고려)= 0 + 6 = 6이때 R에서 next =[ Tree-table, R ]Node #, kPredecessor nodeCost10∞0201∞630∞40∞50∞60∞② (1, 3)= 0 + 2 = 2이때 R에서 next =[ Tree-table, R ]Node #, kPredecessor nodeCost10∞0201∞6301∞240∞50∞60∞ⅱ) k를 L에 등재시킨다.Next nodeLoose-Ends, LInitial entry , h1123- 여기서 L이 비어있지 않으므로 위에서부터 차례대로 next값을 취한다.Next nodeLoose-Ends, LInitial entry , h1123233. 이제 next node가 2와 3인 node에 대해서 step 2부터 고려ⅰ)로 설정,로 둔다.① (2, 4)= 6 + 1 = 7이때 R에서 next =[ Tree-table, R ]Node #, kPredecessor nodeCost10∞0201∞6301∞2402∞750∞60∞② (3, 2)= 2 + 3 = 5이때 R에서 next =[ Tree-table, R ]Node #, kPredecessor nodeCost10∞02013∞65301∞2402∞750∞60∞ⅱ) k를 L에 등재시킨다.Next nodeLoose-Ends, LInitial entry , h11232432- 여기서 L이 비어있지 않으므로 위에서부터 차례대로 next값을 취한다.Next nodeLoose-Ends, LInitial entry , h11232432424. 이제 next node가 4와 2인 node에 대해서 step 2부터 고려ⅰ)로 설정,로 둔다.① (4, 5)= 7 + 2 = 9이때 R에서 next =[ Tree-table, R ]Node #, kPredecessor nodeCost10∞02013∞65301∞2402∞7504∞960∞② (4, 6)= 7 + 1 = 8이때 R에서 next =[ Tree-table, R ]Node #, kPredecessor nodeCost10∞020try , h*************5-6-456- 여기서 L이 비어있지 않으므로 위에서부터 차례대로 next값을 취한다.Next nodeLoose-Ends, LInitial entry , h*************5-6-4565-6-6. L이 비어있으므로 4단계로 진행하여 최종적인와를 구한다.node 1로 부터의 최적경로CostDestination nodePredecessor nodes*************542317642314. Programming1) 디렉토리명칭 : shortest2) 구성① preamble - 변수, 배열선언과 프로그램의 환경설정② main - 배열의 크기를 잡아주고 초기 값을 설정③ process in - program에서 사용할 변수들을 Dos에서 불러들임④ process mtree - Moore Tree Algorithm의 진행⑤ process report - 결과물의 출력3) 진행① 네트워크정보 입력 - forward star algorithm 사용? locatableㄱㄴㄷㄹa1126b2332c3441d4523e5752f6761?locatble 의 구성방식예를 들어 (a,ㄱ)은 node의 번호를, (a, ㄴ)은 그 노드와 연결된 노드의 번호가 위치하는 셀인 (a,ㄷ)의 위치를 알려주는 pointer이며 (a,ㄹ)의 연결비용을 의미함.?program에서의 이용방법dos editor로 작성하여 이 것을 일정 이름의 파일로 저장 한 후 프로그램을 실행할 때 불러들여 사용함.?Input되는 형태input 형식1 1 2 62 3 3 23 4 4 14 5 2 35 7 5 26 7 6 1?programming② Moore tree algorithm 진행for i = locatable(nextnode,2) to (locatable(nextnode+1,2)-1) dok = locatable(i,3)ltable(k,2) = kcost = treetable(nextnode,2) + locatable(i,4)if cost < treetable(k, i = 1 to n.nodetreetable(i,2) = 10000for i = 1 to n.node dofor j = 1 to 2ltable(i,j) = 0looptreetable(1,1) = 1treetable(2,1) = 2treetable(3,1) = 3treetable(4,1) = 4treetable(5,1) = 5treetable(6,1) = 6activate a in nowstart simulationend?process inopen 1 for input, file name is "loca.txt"use 1 for inputlet eof.v = 1for i = 1 to n.node dofor j = 1 to 4read locatable(i,j) as (10) i (4) loopactivate a mtree nowend?process mtreenextnode = 1treetable(ininode, 2) = 0'100'for i = locatable(nextnode,2) to (locatable(nextnode+1,2)-1) dok = locatable(i,3)ltable(k,2) = kcost = treetable(nextnode,2) + locatable(i,4)if cost < treetable(k,2)treetable(k,2) = costtreetable(k,3) = nextnodeendifloopif nextnode = 4go to 200endiffor i = 1 to n.nodewith ltable(i,2) > 0find nextnode = ltable(i,2)ltable(i,2) = 0go to 100'200'activate a report nowend?process reportfor i = 1 to n.node dofor j = 1 to 3write treetable(i,j) as (10) i (4) loopstopendⅢ 결론최단경로를 찾는 알고리즘에는 여러 가지가 있지만 그 중에서 모든 알고리즘의 기본이 되는 MOORE-TREE A말함

공학/기술| 2007.03.13| 8페이지| 2,500원| 조회(967)

알고리즘, c, 최단경로, Moore Algorithm

미리보기

닫기
[공학]최단경로 탐색을 위한 Dijkstra Tree Algorithm

교통체계분석-The Shortest PathDijkstra Tree AlgorithmThe Shortest Path - Dijkstra Tree Algorithm과 목 : 교통체계분석제출일 : 2006 . 6 . 261. 서론1.1 개요교통모형 기법에 이용되는 최단경로 탐색 알고리즘은 각 노드로의 누적시간과 전 노드를 개선하는 하나의 고유한 방법으로 도출 되었다. 이들의 차이는 개선과정에 있어서 자료구조를 어떻게 변화시키는가에 따라 정의될 수 있다.최단경로 문제는 1950년대 Ford(1956)와 Bellman(1975)의 알고리즘을 기반으로 하여 Moore(1975)와 Dijkstra(1957)의 의해 그 기틀이 다져졌으며, 그 이후 많은 알고리즘들이 제안되어 왔다.1.2 경로선택 알고리즘 개요경로선택 알고리즘들은 노드에 부여되는 라벨의 관리방법에 따라서 라벨고정 방식과 라벨 수정방식으로 구분할 수 있다. 라벨 고정방식에서 모든 노드들은 일시적으로 라벨된 상태나 영구적으로 라벨 된 상태를 갖는다. 경로계산 알고리즘에서 반복되는 루틴을 행할 때마다 하나의 노드가 영구적으로 라벨되며, 그것은 시작노드부터 그 노드까지 최적의 경로를 갖는다는 것을 의미한다. 라벨 수정방식은 경로계산이 끝날 때까지 어떠한 노드도 영구적으로 라벨되지 않는다. 인접한 어떤 노드에 의해 더 좋은 비용으로 수정된 노드는 라벨집합의 큐(queue)에 들어가 다시 경로계산 반복에 사용될 노드로 선택될 수 있다. 한번 경로계산 반복 과정에서 사용된 노드일지라도 다른 노드에 의해서 라벨이 수정되어 또 다시 경로계산의 반복에 사용될 노드로 선택될 수 있다.? 연속되는 링크들은 경로(path), 순환(loop), 연쇄(chain)를 형성한다.- 경로(path) : 한 링크를 한번이상 통과하지 않는 연쇄- 순환(loop) : 임의의 노드에서 출발하여 다시 자기 자신으로 연결되는 연쇄- 연쇄(chain) : 한 노드와 다른 노드들을 연결하는 링크의 연속적인 연결? 표지(Label)영구표지(parament label) : 출발노드 h 에 대하여 노드 h 로부터 특정노드까지 최종적으로 결정된 최단거리를 나타내는 노드에 표시되는 표지.영구표지가 표시된 노드는 최단경로를 구성하는 노드가 된다.임시표지(temporary label) : 노드 h 로부터 특정노드까지의 어떤 한 경로의 길이를 나타내는 데, 이경로가 최단경로가 아닐수도 있기 때문에 임시표지는 실제 최단거리의 상한치(upper bound)를 나타낸다. 즉 노드 I의 임시표지를 노드 I 까지의 최단거리의 추정치라고 간주할 수 있으며, 이 추정지를 더 이상 줄일 수 없으면 이 추정치가 영구표지로 확정된다. 영구표지가 표지된 노드를 영구노드라 한다.? Labelling AlgorithmLabel - setting 기법 : 하나의 노드에 대한 고려가 끝나는 반복과정마다 영구표지를 표지하면서 최단 경로를 찾는 기법Label - correcting 기법 : 반복과정이 되풀이되는 동안 임시 표지값을 기록하고 있다가 모든 노드에 대한 고려가 끝난후에 영구표지를 결정하는 방법1.3 수형망(tree building)과 넝쿨망(vine building)의 비교통행배정에서 기초적 과정은 통행 출발지에서 통행 도착지까지의 최단경로를 결정하는 것과 최단경로에 통행량을 부과하는 것이다. 대부분의 통행배정 과정에서 “비용최소화”가 운전자들이 경로를 선택하는 기초가 된다고 가정한다. 따라서 통행은 출발지에서 도착지까지의 최소경로를 따라 배분된다고 가정한다.단일 출발지에서 도착 노드를 포함한 도로망 상의 다른 노드가지의 최소비용경로는 배정과정에서 어떤 노드나 링크를 단 1번만 통과(one pass)한다. 한 노드나 링크를 반복해서 순환하는 불필요한 반복은 없어야 한다. 만일 최단경로 결정과정 중, 각각의 노드에서 경로의 통과가 1번만 고려되고 경로가 중심지(centroid node)를 통과하는 것이 허용되지 않는 다면 그 알고리즘을 단일 통과 알고리즘(once through building)이라 한다.출발노드 h 에 대하여 알고리즘에 따라 경로가 완료되었을 때 도로망 상에서 다른 노드들이 단지 1개의 링크에 의해서만 도착된다면 h에서 다른 노드까지의 경로의 집합을 최소비용 수형망이라 하고, 이러한 최소비용 경로의 결정과정을 수형망 알고리즘이라 한다.넝쿨망은 출발노드에서부터 다른 노드들로 경로를 전개할 때 한개 이상의 경로를 사용하여, 어떤 노드에 대해서 한 개 이상의 이전링크(predecessor link)가 존재하는 경우 넝쿨망이라 하고, 이에 대한 알고리즘을 넝쿨망 알고리즘이라 한다.[표 1] Tree 와 Vine 의 비교구분Tree Building AlgorithmVine Building Algorithm특징? 출발노드로부터 임의의 다른 노드까지 단 1개의 경로만을 허용 (최단경로상의 모든 노드의 유입차수가 1)? 출발노드로부터 임의의 다른 노드까지 1개 이상의 경로를 허용(최단경로상의 모든 노드의 유입차수가 1이상)장점? 알고리즘 간단? 수행속도 빠름? 회전제약 고려 가능단점? 회전제약 고려 못함? 알고리즘 복잡? 계산량 많음2. 본론2.1 Dijkstra Algorithm 의 특징? Dijkstra Algorithm 은 Label - setting 기법을 적용한 알고리즘으로 이해가 쉽고 각종 최단경로 문제에 광범위하게 적용될 수 있으며, 사용이 간편함으로써 가장 널리 사용되는 알고리즘이다.? Dijkstra Algorithm 은 기점에서부터 여러 개의 대안 경로가 있을 경우 최적의 원리에 근거로 하여 최소비용 경로를 찾아 해당노드를 영구표지로 선정하는 단계를 거치므로 계산과정이 짧은 장점이 있으나, 다른 우회경로에 대한 고려를 할 수 없는 단점이 있다.? 모든 링크의 weight가 nonnegative한 값을 갖는다는 것이 기본 가정이다.즉,이 성립한다. 경로를 이루는 링크의 수가 늘어날수록 경로의 길이도 증가한다는 의미이다.2.2 Dijkstra Algorithm의 진행과정? 기본 Parameter? setp 1 : 초기화- Network상 모든 node에 대하여로 설정하며,로 초기화- Loose-Ends Table의 출발노드 h 와 연결되는 모든 도착노드 j 를 넣음- h 를 NEXT 로 설정? step 2 : 노드의 최적경로비용의 update 및 이전노드의 저장- Loose-Ends Table의 L 집합에서 NEXT 설정-이면,로 값을 변환하고,=Next로 값을 변환한다.- Loose-Ends Table의 L column에 j 와 연결되는 모든 도착노드를 넣는다.? step 3 : L로부터 고려될 Next 노드의 선정- (Next, K) 값이 이미 등록된 값과 동일하다면, 어떤 L-column 에도 등록되지 않는다.- Loose-Ends Table의 L에 더 이상 저장된 노드가 없을 때 까지 step2 반복? step 4 :최소비용경로와 비용의 결과- 최초의 노드로부터 각 노드별로 최소비용경로 및 비용 Table 출력2.3 Dijkstra Tree Algorithm 을 이용한 예제Tree Table , RNode no.kPredecessorNodeCost*************402650486047Loose - Ends Table , L‘NEXT' nodeLoose - endsLInitial entry , h112332244565-6-- node 1에서 모든 접근로의 노드를 고려, 그중 가장 min의 cost 를 가진 노드를 선택- 선택된 node 3에서의 접근 노드 고려, min의 cost 선택(여기서는 node 2의 대안만 있다.)- 단계별로 Loose - Ends Table을 작성, L값이 비었을 경우까지 반복- 선택된 node 만 고려, 다른 노드는 고려하지 않음최소비용경로 및 비용 TablecostDestinationnodePredecessor523 1231642 3 1854 2 3 1764 2 3 13. 프로그램에 의한 검증본 절에서는 위의 에제가 프로그램상에 어떻게 나타나는지를 검증하도록 한다. 따라서 실제 교통량을 모의 network 상에 배분하였을 때 iteration 횟누 및 통행비용의 변화에 따른 최단경로의 변화를 살펴보았다.사용한 프로그램은 Visual C++ 6.0 을 사용하였다.3.1 Visual C++을 이용한 Program Source Code#include #define MAX_N 202#define INT_MAX 100000 // INT_MAX 값void shortestPath(int v, int weight[MAX_N][MAX_N], int dist[MAX_N], int n, int found[MAX_N]){int i, minpos, w, min;for (i=0;i

공학/기술| 2007.03.13| 7페이지| 2,000원| 조회(1,846)

알고리즘, c, dijkstra, 최단경로

미리보기

닫기