http://moogi.new21.org/tc/ 그런즉 이제 애호박, 단호박, 늙은호박 이 셋은 항상 있으나, 그 중에 제일은 늙은호박이니라. ko Fri, 14 Mar 2025 06:50:07 +0900 Textcube 1.7.8 : Con moto http://moogi.new21.org/tc/attach/1/1226640661.jpg http://moogi.new21.org/tc/ 216 185 그런즉 이제 애호박, 단호박, 늙은호박 이 셋은 항상 있으나, 그 중에 제일은 늙은호박이니라. http://moogi.new21.org/tc/815#comment3815 흥미로운 주제로군요. 비슷하다면 비슷한데 또 다르다면 다른 주제로 동영상 압축 기법인 벡터 양자화(vector quantization)가 있습니다. 이를테면... 16x16 크기의 샘플 패턴 N개를 생성합니다. 이후 동영상의 각 프레임들을 16x16 격자로 나눈 후 거기에 대응되는 샘플 패턴의 번호로 나타내는 것이죠. 만일 패턴이 256개라면 1바이트로 표현할 수 있으니까 RGB 각 1바이트로 나타낸 색 공간에서라면 동영상은 1/3크기로 줄어들게 되겠죠. 샘플 패턴을 어떻게 정할 것인가는 자명한 방법이 있습니다. 해당 샘플 패턴을 사용할 격자들과의 제곱오차를 최소로 하는 패턴을 사용하면 되겠죠. 다시 말해서 그 격자들의 기하평균을 구하면 됩니다. 그렇다면 결국 각각의 격자값을 어떤 패턴에다 대응시키는 것이 화질 열화를 최소로 하는 방법인지 찾아내야 하는데 고려해야 할 변수가 많기 때문에 그리 쉽지는 않습니다. 이 경우에도 LP 등의 기법을 많이 동원하더군요. 그런데 Genetic algorithm에다가 local optimization을 동원한 알고리즘이 상당히 좋은 성능을 보인다는 얘기를 봤어요. (김재주) http://moogi.new21.org/tc/815#comment3815 http://moogi.new21.org/tc/815#comment Mon, 08 Apr 2013 18:21:39 +0900 http://moogi.new21.org/tc/815#comment3816 아, 어찌보면 엘리베이터 스케쥴링 문제와도 비슷하군요. 서울대학교 문병로 교수님의 논문을 링크합니다. http://soar.snu.ac.kr/papers/journals/9.pdf 엘리베이터 이용객은 흔히 푸아송 분포를 따른다고 알려져 있는데 이를 이용해서 다양한 평가항목을 가장 잘 만족시키는 스케쥴링 규칙을 GA를 이용해서 adaptive하게 바꿔나간다는 것입니다. 승객들의 철도 이용 행태도 거의 해마다 비슷할테니 1년 전의 데이터를 바탕으로 현재 최적이라고 할 수 있을 만한 배치 규칙을 찾아내게끔 할 수 있겠습니다. 코레일 나름대로 사용하고 있는 방법이 있겠지만, 이런 쪽으로도 한번 연구개발을 해보는 것이 어떨까 싶습니다. (김재주) http://moogi.new21.org/tc/815#comment3816 http://moogi.new21.org/tc/815#comment Mon, 08 Apr 2013 18:26:09 +0900 http://moogi.new21.org/tc/815#comment3817 1. 여러 흥미로운 보충 설명에 감사드립니다. 영상의 손실 압축에서 화질 열화를 최소화하는 기법에도 그런 방식의 문제가 있다는 것도 처음 알았고요. 그리고 문 교수님이 그 분야에도 손대신 적이 있다는 것도요. 그리고 엘리베이터.. 그것도 좌석 배당만큼이나 경험적인 전략이 필요한 아주 실용적인 주제임이 틀림없어 보입니다. 아주 초창기에 1회 IOI 때 대놓고 엘리베이터 시뮬레이션 문제가 나온 적이 있었지만 그때는 너무 옛날이어서 대회 진행 방식이 정착하기 전이었고, 9회(97년) 6번 문제 컨테이너 쌓기도 비슷하다면 비슷한 주제 같습니다. 승객 대신 컨테이너이고, 좌석의 단편화 대신 스택 구조가 있는 셈이죠. (사무엘) http://moogi.new21.org/tc/815#comment3817 http://moogi.new21.org/tc/815#comment Mon, 08 Apr 2013 22:54:50 +0900 http://moogi.new21.org/tc/815#comment3819 IOI 문제와는 좀 다른 것이 여러 개의 승강기가 있는 경우에 어떤 승강기를 스케쥴링할것인가 하는 문제라서요. 아무튼 열차 배치도 결국 평가함수는 수정되겠지만 거의 비슷한 접근을 할 수 있을 것 같네요. 그리고 다시 보니까 1/3로 줄어드는 게 아니네요. 16x16격자를 대표하는 것이니까 1/3 * 1/16^2로 줄어듭니다 후덜덜.. (김재주) http://moogi.new21.org/tc/815#comment3819 http://moogi.new21.org/tc/815#comment Tue, 09 Apr 2013 13:44:21 +0900