칠레처럼 아주 길쭉한 국가가 있다고 치자. 이 국가에는 지형을 따라 거대한 간선 철도가 놓여 있고 n개의 역이 있으며, n개의 역에 모두 정차하는 완행 열차가 일정 간격으로 다닌다.

이 설정을 좀 극단적으로 확장하여 역 수가 수백, 수천, 수만-_-개에 달한다고 가정하자. 그렇다면 급행 열차를 운행할 필요가 응당 생긴다. 2000개역쯤 떨어진 지역에 가려고 하는데 전역정차 열차를 탈 수는 없는 노릇 아닌가. 그렇게 여행 거리가 길어지면, 급행 열차가 서는 곳까지 가서 환승하는 불편 정도는 급행의 빠른 속도가 충분히 보상하고도 남게 된다.

자, 이를 일반화하면.. 급행도 등급이 필요해서 특급, 쾌특 등 n차원의 급행을 생각할 수 있게 된다. 등급이 올라갈수록, 서는 역 수가 무척 적어서 타기 힘든 대신에 일단 타기만 하면 엄청난 이동성이 보장된다. 급행과 완행은 배차 간격은 모두 동일하다고 치자.

여기서 문제가 생긴다.
각 등급의 급행 열차들은 정차역 수를 얼마로 설정하는 게 좋을까?
또한, 철도역 수 n에 대해서, 최대 몇 등급의 급행이 존재하는 게 적당할까?

n개의 역이 모두 똑같이 중요하고 이용객 수가 균일하다고 가정할 때,
어떻게 급행을 운영하는 게 승객의 평균 표정속도를 최대화하고 반대로 평균 환승 대기 시간을 최소화할 수 있을까?
선로 수는 충분하기 때문에, 완급 결합으로 인한 대피 대기 오버헤드라든가 선로 용량 걱정은 할 필요 없다고 가정하겠다. ^^

역 수가 10개 남짓이라면 급행이 있을 필요가 없겠지만, 역 수가 100개쯤 된다면 3~4개역을 건너뛰는 1차 급행에 이어서 한 10~12개쯤 역을 쉬엄쉬엄 건너뛰는 2차 급행이 있어도 좋을 것 같다.

전산학을 전공한 친구라면, 이런 부류의 문제를 생각하면서 비슷한 형태의 아주 유명한 알고리즘을 하나 떠올리게 될 것이다.
바로 '쉘 정렬'이다!

쉘 정렬은 삽입 정렬을 원소별로 띄엄띄엄 적용하되 나중에 그 간격을 촘촘히 좁히는 방식이다.
삽입 정렬은 시간 복잡도가 O(n^2)이지만, n의 크기가 작아서 띄엄띄엄일 때는 오버헤드가 크지 않으며, 또 편차가 커서 리스트가 상당수 정렬되어 있을 때는 매우 빠르게 수행되기 때문에 그 특성을 이용한 것이다.
쉘 정렬은 알고리즘의 특성상 실제로 코딩해 보면 루프가 3중, 4중으로 들어가기 때문에 무거울 것 같지만 돌려 보면 성능이 매우 좋다. 프로그래밍 언어라고는 아직 어셈블리밖에 없던 1950년대에 고안된 알고리즘이다.

여타 정렬 알고리즘들이 O(n^2), O(n log n) 아니면 심지어 O(n) 같은 식으로 시간 복잡도가 딱 파악되는 반면, 이 쉘 정렬은 비록 O(n^2)보다야 훨씬 빠르긴 하지만 시간 복잡도가 제대로 분석되어 있지 않다.
삽입 간격을 설정해서 좁히는 방식을 어떻게 설정하냐에 따라서 성능이 크게 달라지기 때문이다.

완행 다음으로 급행을 겨우 1역 균일 통과, 특급을 2역 균일 통과처럼 정말 무식하기 짝이 없게 운행하지는 않는다. 급행 등급이 하나 올라갈 때마다 급행은 최소한 기하급수적으로 통과역 수가 늘어야 이치에 맞다.
쉘 정렬도 그와 마찬가지이다. 23, 10, 4, 1 같은 급으로 큼직하게 수가 바뀌고, 이 수들이 가능한 한 서로소가 되게 하는 게 정렬 효율에 좋다고 알려져 있다. 16, 8, 4, 2, 1처럼 정확하게 컴퓨터스럽게 배수· 약수 관계로 포개지는 간격은 매우 비효율적이며, 그런 나쁜 수열을 쓰면 쉘 정렬의 시간 복잡도가 최악의 경우 도로 O(n^2)로 치솟는다고 한다.

우리나라의 급행 전철이 정차역 수가 여전히 너무 많다는 지적이 있긴 하지만, 이것은 환승을 싫어하는 국민 정서 내지 환승이 불편한 구조, 급행도 어차피 최대 속도는 동일하고 완행보다 그렇게 많이 빠르지 않은 것, 역마다 weight가 현실적으로 차이가 나는 것, 급행의 소극적인 운행(긴 배차 간격) 같은 다른 환경적인 요인 때문에 그런 것이다. (현실에서는 환승역이냐 그렇지 않느냐의 여부 하나만으로도 역별 weight가 크게 벌어질 수밖에 없다)

이상, 철도와 전산학을 융합한 뻘글이었다.
쉘 정렬의 수열 설정 방식이 철도 운영에서도 이론상 효율적이라 말할 수 있을까? ^^;; (급행은 4역씩 건너뛰고 특급은 10개역, 쾌특은 23개역.. ㄲㄲ)
참고로 쉘 정렬은 수열을 제일 잘 설정했을 때 시간 복잡도가 O(n (log n)^2) 까지는 떨어진다고 한다.


* 덧붙이는 말:
어제는 KTX 열차가 개통 사상 처음으로 탈선 사고를 일으켰다고 한다.
여기에 대해 철도 덕후 사무엘 님의 공식 입장을 말하자면, 이건 두말 할 나위도 없이 선로 시설 문제이지 차량 문제가 아니라는 것이다.
차량이 떼제베가 아닌 산천이었다고 하는데, 지금까지 늘 말썽을 일으켜 온 것처럼 차량이 고장을 일으킨 거라면, 그대로 차가 멈춰서는 걸로 끝나지 지가 무슨 능력으로 탈선까지 하겠는가?

더구나 이 차는 보기 드문 광명 시종착 KTX였다. 광명이 단순 경유역이 아닌 종착역이기 때문에 여타 열차와는 다른 선로로 건너가야만 했다. 그래서 선로 분기기가 열차를 새 선로로 유도하고 있었는데, 열차가 다 건너기 전에 선로 분기기가 전산 착오 내지 추위로 인해 오작동한 것 같다. 그래서 뒷부분 객차의 진로를 막았고, 이것 때문에 찌이이이익 소음+타는 냄새+탈선이 야기된 것으로 추정된다.

열차가 고속으로 쌩쌩 달리다가 교량이 붕괴했다거나 차량이 자폭이라도 한 것과는 전혀 다른 부류의 사고이다. 오히려 열차는 종착역 진입을 앞두고 위와 같은 이유로 인해서 아주 천천히 달리면서 신호를 기다리고 있는 상태였을 것이다. 그리고 그 사고도 그런 특수한 상황에서나 발생한 사고이다. 이 사고가 KTX 차량 시스템 전반에 대한 불신풍조로 이어지기는 않기를 본인은 바란다.

이 사고로 인해 이 열차를 바로 뒤따라오던 상행 KTX는 평택쯤에서 다시 천안아산-_- 역으로 역주행하여 돌아가야만 했고, 대전-서울 구간의 고속선이 폐쇄되는 바람에 다른 KTX들은 아예 경부선 기존선으로 우회해서 다녀야 했다. 주말 임시 열차는 아예 선로 용량 부족으로 인해 운행 중단. 코레일의 입장에서는 손해가 그야말로 막심했을 것이다. 이로 인해 수원-천안 구간에서 KTX 산천이 보이는 진풍경이 연출되기도 했다.

Posted by 사무엘

2011/02/12 17:49 2011/02/12 17:49
, , , , ,
Response
No Trackback , 5 Comments
RSS :
http://moogi.new21.org/tc/rss/response/464

Trackback URL : http://moogi.new21.org/tc/trackback/464

Comments List

  1. 아라크넹 2011/02/12 19:49 # M/D Reply Permalink

    셸 정렬은 gap이 일정하다는 가정을 하고 있기 때문에 급행-완행으로 그대로 적용하기는 좀 무리가 있죠. 한편 셸 정렬의 gap sequence를 아무리 잘 줘도 O(n log n)이 될 수 없다는 건 이미 알려져 있습니다(Plaxton, Poonen, Suel, 1992). 셸 정렬의 진짜 강점은 삽입 정렬의 장점(거의 정렬된 배열에 대해서 O(n)에 가까워짐)을 살리면서 최악의 경우에도 O(n^2) 시간 복잡도를 피할 수 있다는 것이기도 하고, 병렬 정렬 네트워크에도 적용할 수 있다는 장점도 있습니다(만 이건 병합 정렬도 마찬가지네요).

    KTX 탈선 얘기는 듣고 저도 깜짝 놀랐는데 저속 주행 중 사고가 났다는 얘기를 듣고 선로 문제겠구나 했었죠. 큰 사고가 되지 않아서 다행이네요.

    1. 사무엘 2011/02/13 08:59 # M/D Permalink

      후훗, 쉘?셸? 어쨌든 참 신비로운 정렬 알고리즘이죠. 당연히, 현실에서는 모든 역이 동일하게 중요한 구간이 그렇게 길지 않으며, 환승 오버헤드, 선로 용량 등 여러 제약으로 인해, 쉘 정렬의 수열 정하는 전략이 완급 운행 전략에 그대로 적용될 수는 없습니다.
      (요즘은 얼굴 보기가 힘들구만..;; 잘 지내고 있으셈? =_=)

  2. 김기윤 2011/02/13 10:25 # M/D Reply Permalink

    쉘 정렬 ㅋㅋㅋㅋㅋㅋ.. 재밌군요! 쉘 정렬과 비교가 되다니 ㄷㄷ...

    -뭐 언제나 제가 남기는 댓글이 그렇지만- OTTD 버젼 중에서 <일단은 오픈소스이니> 승객목적지버젼...이 있습니다. 통상 버전은 승객이던 화물이던간에 A->B 정거장으로 운송하면 그냥 그걸로 끝인, 승객 입장에서 보면 수동적인 시스템이었지만, 승객목적지 버전은 승객이 적극적으로 바뀝니다. A->F로 가야 하면, A->B->C->D->E->F 식으로 환승하는 식.

    얼마 전에 했던 세이브파일에서는 <del>귀찮아서</del> 완행밖에 없는 노선을 무더기로 만들었는데, 죄다 포화상태에 걸리더군요-_-. 이 버전은 승객 AI 를 잘 만들어놔서 A->B->C 루트가 포화상태면 A->D->E->F->C 와 같은 우회로도 이용하는 식이라서 포화상태인 노선 옆에 비슷한 방향으로 노선을 또 놨는데도 포화상태가 걸리는 일이 있었습니다. ..... 급행/특급을 깔면 더 나아졌으려나 생각해 봅니다=_=


    p.s. 그러고보니 게임이고 하니까 한번은 현실이라면 욕을 더럽게 처먹(...)을만한 노선도 만들어봤습니다. 완행인데, 노선에 고리가 있다고 해야 할까요?. A->B->C->D->E->F->E->C->G->H->I 순서.. (E랑 C가 두번 등장합니다 -_-;;;) (실제로도 효율이 떨어지더군요. C역에서 손님이 죄다 환승하는바람에 그곳에서 열차가 움직이질 못하는..)

    1. 김기윤 2011/02/13 10:31 # M/D Permalink

      쓰다보니 논제에 벗어났군요. -_-;; 어쨋든, 시간내서 OTTD 상에서 실험을 해 볼까 생각중입니다. 적당한 상황을 만들어 놓고 쉘 정렬의 수열 방식이 더 좋은지, 컴퓨터스러운 배수방식이 더 좋은지 ㄲㄲㄲ

      p.s. 이번 탈선사고는 저도 용묵님과는 같은 의견입니다. 다만, 어째선지 KTX를 안티하는 느낌이 팍팍 드는 기사가 많이 보이네요.. "직원들도 안타?" 라는 기사제목이 보이는데, 그럴 리가 없잖아요.

    2. 사무엘 2011/02/14 00:05 # M/D Permalink

      승객의 평균적인 이동 시간을 줄이고, 급행 환승 시간 오버헤드와 급행 시간 만회 사이에서 가장 좋은 tradeoff를 낼 수 있는 급행 운행 전략에 대해 체계적인 연구가 필요함을 느낍니다.
      조금만 더 조건을 구체적으로 엄밀하게 주고 나면 정보 올림피아드 문제감으로도, 심지어 논문감도 될 수 있을 것 같은데요? ^^

Leave a comment
« Previous : 1 : ... 1011 : 1012 : 1013 : 1014 : 1015 : 1016 : 1017 : 1018 : 1019 : ... 1430 : Next »

블로그 이미지

철도를 명절 때에나 떠오르는 4대 교통수단 중 하나로만 아는 것은, 예수님을 사대성인· 성인군자 중 하나로만 아는 것과 같다.

- 사무엘

Archives

Authors

  1. 사무엘

Calendar

«   2018/09   »
            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            

Site Stats

Total hits:
1020738
Today:
29
Yesterday:
625