기본적인 컴퓨터 문제, 최대 흐름 문제가 획기적인 진전을 이루었습니다. 새로운 알고리즘은 '어리석을 정도로 빠릅니다'

이 문제는 네트워크 흐름 이론에서 매우 기본적입니다. 예일대학교의 다니엘 스필만(Daniel Spielman)은 "새로운 알고리즘은 엄청나게 빠르다. 사실 나는 이 문제에 대해 그렇게 효율적인 알고리즘이 없다고 확신했다"고 말했다.

최대 흐름은 소련 철도 시스템을 모델로 연구하던 1950년대부터 연구되어 왔습니다. "이에 대한 연구는 컴퓨터 과학 이론보다 훨씬 더 오래되었습니다."라고 캘리포니아주 마운틴뷰에 있는 Google 연구 센터의 Edith Cohen은 말합니다.

이 질문은 인터넷 데이터 스트리밍, 항공 스케줄링, 구직자와 공석 매칭 등 다양한 응용 분야로 이어집니다. 이 새로운 논문은 비용을 최소화하면서 최대 흐름 문제와 최대 흐름을 처리하는 보다 일반적인 문제를 모두 다루고 있습니다. 이 두 가지 질문은 수년에 걸쳐 알고리즘 기술의 많은 중요한 발전에 영감을 주었습니다. Spielman은 "이것이 우리가 계속해서 알고리즘을 연구하는 이유입니다"라고 Spielman은 말했습니다. 즉, 알고리즘의 실행 시간은 기본적으로 필요한 시간에 비례하여 알고리즘의 실행 시간이 동일하다는 것을 의미합니다. 이러한 문제를 해결하기 위한 다른 알고리즘은 가능한 모든 네트워크에 대해 이 속도를 달성할 수 없습니다. University of California, Berkeley의 Satish Rao는 이 결과가 그를 뛰게 만들었다고 말했습니다. "정말 놀랍습니다."

Spielman은 우리가 그렇게 빠른 알고리즘을 발견했다고 믿고 있으며 이제 우리는 이전에 다양한 응용 문제를 생각해 본 적이 없습니다.

현재 새로운 방법은 주로 이론적인 개선입니다. 왜냐하면 알고리즘 속도의 개선은 실제 세계에서 발생하는 것보다 훨씬 더 큰 네트워크에만 적용 가능하며 최대 트래픽 문제는 이미 매우 빠르게 해결될 수 있기 때문입니다. 대답하십시오 (적어도 비용 최소화를 고려하지 않고). 6명의 개발자 중 한 명인 캐나다 워털루 대학교의 Richard Peng은 새로운 알고리즘이 1년 내에 실용화될 수 있을 것으로 기대하고 있습니다.

일부 연구자들은 앞으로 몇 년 안에 컴퓨터 과학자들이 이를 더욱 실용적이고 더 빠르게 만들 수 있는 방법을 찾을 것이라고 믿습니다.

MIT의 Aleksander Mądry는 앞으로 개선이 있더라도 이 새로운 논문은 "슬램덩크 콘테스트에서 가장 흥미로운 덩크"라고 말했습니다. 기본적으로는 최고라고 하더군요."

한 번에 한 길

Richard Peng은 많은 컴퓨터 과학자들이 최대 흐름 문제를 연구하고 있기 때문에 컨퍼런스에서 과거 작업에 대해 논의하는 것은 영화의 최종 크레딧을 통과하는 것과 같다고 말했습니다. 그러나 대부분의 사람들은 최초의 공식 알고리즘이 1956년 Lester Ford와 Delbert Fulkerson이 각 단계에서 가장 쉽게 사용할 수 있는 개체를 사용하는 최대 흐름을 위한 그리디 알고리즘을 적용한 것이라는 점에 동의합니다.

이 접근 방식은 다음과 같이 생각할 수 있습니다. 먼저 고속도로 네트워크를 상상하고 주어진 시간에 로스앤젤레스에서 뉴욕 시로 최대한 많은 배달 트럭을 이동하려고 합니다. Ford와 Fulkerson의 알고리즘은 로스앤젤레스에서 뉴욕까지의 경로를 선택하고 해당 경로를 따라 가능한 한 많은 트럭의 경로를 지정하는 것으로 시작됩니다. 이 방법은 일반적으로 특정 도로에 있는 모든 도로의 전체 용량을 활용하지 않습니다. 도로가 5차선 고속도로이지만 2차선 다리를 넘어가는 경우 한 번에 두 대의 트럭만 이동할 수 있습니다.

다음으로, 알고리즘은 현재 사용되는 구간 용량의 일부를 반영하기 위해 이러한 구간의 용량을 수정합니다. 즉, 구간 용량에서 보낸 트럭 수를 빼므로 이제 5차선 고속도로의 용량은 3이 됩니다. , 반면 2차선 교량의 수용능력은 0이다. 동시에 알고리즘은 반대 방향으로 이 도로의 용량에 2를 추가하므로 원할 경우 나중에 교통량의 일부를 철회할 수 있습니다.

그런 다음 알고리즘은 일부 트럭을 수용할 수 있는 로스앤젤레스에서 뉴욕까지의 새로운 경로를 찾아 경로를 따라 최대한 많은 트럭을 보내고 용량을 다시 업데이트합니다. 제한된 수의 이러한 단계를 거치면 로스앤젤레스에서 뉴욕까지의 도로는 더 이상 트럭을 수용할 수 없게 되며 이 시점에서 알고리즘이 완성됩니다. 우리는 가능한 최대 흐름을 얻기 위해 구성된 모든 흐름을 간단히 결합합니다. 네트워크.

Ford와 Fulkerson의 알고리즘은 그 과정에서 현명한 선택을 시도하지 않습니다. 다른 유용한 경로를 차단하는 경로를 선택한다면 이는 나중에 알고리즘이 처리해야 할 문제입니다. 알고리즘이 발표된 이후 수십 년 동안 연구자들은 알고리즘이 항상 사용 가능한 가장 짧은 경로나 사용 가능한 용량이 가장 큰 경로를 사용하는 등 더 현명한 선택을 하도록 하여 실행 시간을 단축하려고 노력해 왔습니다. 1970년에 Yefim Dinitz는 네트워크의 모든 최단 경로를 한 단계로 사용하는 효율적인 방법을 발견했습니다. 저용량 네트워크에서 이 알고리즘의 실행 시간은 Shimon Even과 Robert Tarjan에 의해 m^1.5(m: 네트워크의 링크 수)로 입증되었습니다. 반면 Ford-Fulkerson 알고리즘은 저용량 네트워크에서 여러 m이 필요합니다. 네트워크 ^2).

거의 30년 후 Rao와 Andrew Goldberg는 고용량 네트워크에 대해 비슷한 결과를 내놓았습니다. 하지만 누구도 m^1.5 지수를 이길 수는 없습니다. 새로운 논문의 저자 중 한 명인 토론토 대학의 Sushant Sachdeva는 "21세기로 접어들면서 m^1.5에 대한 장벽이 더욱 강화되었습니다"라고 말했습니다. 다양한 방법.

조합에서 미적분까지

지금까지 이러한 모든 알고리즘은 조합 접근 방식을 취했습니다. 즉, 각 단계에서 특정 유형의 구조를 찾고 해당 구조를 사용하여 스트림을 업데이트했습니다. 그러나 2003년에 남부 캘리포니아 대학의 Spielman과 ShangHua Teng은 미적분학 기술을 최적의 솔루션을 찾기 위한 가이드로 사용하는 "최적화"에 대한 완전히 다른 접근 방식의 문을 열었습니다.

Spielman과 Teng은 최대 흐름 문제가 아니라 주어진 저항을 가진 각 와이어 네트워크를 통해 가장 낮은 에너지 전류를 찾는 밀접하게 관련된 문제를 해결하는 빠른 최적화 알고리즘을 개발했습니다. Sachdeva는 Spielman과 Teng의 진전이 "중요한 순간"이라고 말했습니다.

네트워크의 최대 트래픽과 최소 비용을 결정하는 초고속 알고리즘을 만든 팀원(왼쪽 상단부터 시계 방향): Yang Liu, Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, 리처드 펭, 수샨트 사흐데바.

연구원들은 곧 이 진행 상황을 최대 흐름 문제에 적용하는 방법을 탐색하기 시작했습니다. 도로 네트워크를 가용 용량이 많지 않은 도로에 저항을 추가하여 전자가 도로를 가로질러 이동하는 것을 방지하는 전선 네트워크로 생각하십시오. Spielman과 Teng의 연구 덕분에 우리는 이러한 전선을 통한 전류를 신속하게 계산할 수 있으며 이 모델은 고속도로를 통한 최대 차량 흐름에 대한 대략적인 특성을 가지고 있습니다. (현재 문제는 전선 용량에 엄격한 제한을 두지 않기 때문에 정확히 동일하지는 않습니다.)

그런 다음 이 초기 흐름을 생성한 후 Ford 및 Fulkerson의 경우처럼 용량을 다시 조정할 수 있습니다. 결합된 알고리즘. 다음으로, 각 와이어의 저항을 재설정하여 이러한 변화량을 반영하고 새로 생성된 회로 문제를 해결할 수 있습니다.

한 번에 하나의 네트워크 블록을 변경하는 조합 방법과 달리 Spielman과 Teng의 최적화 방법은 매번 전체 네트워크에 대한 스캔을 완료합니다. 이렇게 하면 각 단계가 더욱 효율적이게 되므로 최대값에 도달하는 데 필요한 총 단계 수가 줄어듭니다. 2008년에 Google의 Samuel Daitch와 Spielman이 이 방법을 사용했는데, 이는 기본적으로 이전의 최대 트래픽 제한인 m^1.5와 일치했습니다. 2013년에 Mądry는 저용량 네트워크의 경우 m^1.5를 초과하는 접근 방식을 더욱 발전시켜 런타임을 대략 m^1.43의 배수로 개선했습니다. 라오는 "충격적이다"고 말했다.

향후 몇 년 동안 연구자들은 이 방법을 더욱 확장했지만 결과는 m^1.33에 머물렀습니다. 그들은 이 지수가 근본적인 한계인지 궁금해하기 시작했습니다.

최대 흐름 알고리즘의 경우 상상할 수 있는 가장 빠른 실행 시간은 m배(예: m^1.0)여야 합니다. 네트워크를 작성하려면 여러 m 단계가 필요하기 때문입니다. 이것을 선형 시간이라고 합니다. 그러나 많은 연구자들에게 이렇게 극도로 빠른 알고리즘은 생각할 수 없는 것처럼 보였습니다. Spielman은 "우리가 이것을 할 수 있다고 믿을 만한 타당한 이유가 없습니다"라고 말했습니다.

축소, 재사용, 재활용

이 새 논문의 저자는 Daitch와 Spielman의 접근 방식에 더 많은 이점이 있다고 믿습니다. Mądry는 최대 흐름 문제를 해결하는 데 필요한 단계 수를 줄이기 위해 이를 사용했지만 이러한 감소에는 비용이 발생했습니다. 각 단계에서 전체 네트워크를 다시 작성해야 하고 전력 흐름 문제를 처음부터 해결해야 했습니다.

이 접근 방식은 Spielman과 Teng의 알고리즘을 알고리즘 내부에서 무슨 일이 일어나고 있는지에 관계없이 블랙박스로 취급합니다. 6명의 연구원은 알고리즘의 핵심을 조사하고 해당 구성 요소를 최대 흐름 문제에 맞게 조정하기로 결정했습니다. 그들은 이러한 구성 요소가 주어진 양의 재료를 운송하는 가장 저렴한 방법을 찾는 더 어려운 "최소 비용 문제"를 해결할 수 있다고 의심합니다. 컴퓨터 과학자들은 최소 비용 알고리즘이 문제를 해결할 수 있다는 것을 오랫동안 알고 있었습니다. 질문.

다른 최적화 방법과 마찬가지로 연구원들은 링크 비용과 용량의 함수로 흐름 "에너지" 개념을 제안했습니다. 값비싼 저용량 링크에서 값싼 고용량 링크로 트래픽을 이동하면 시스템의 총 에너지가 줄어듭니다.

흐름을 낮은 에너지 상태로 빠르게 이동하는 방법을 알아내기 위해 연구원들은 이 최적화 접근 방식과 기존 조합 관점을 결합했습니다. 후자는 한 번에 네트워크의 한 부분만 변경하므로 이전 단계의 작업 중 일부를 재사용할 수 있습니다.

각 단계에서 알고리즘은 에너지를 줄일 수 있는 순환, 즉 동일한 지점에서 시작하고 끝나는 경로를 찾습니다. 기본 아이디어는 간단합니다. 시카고에서 뉴욕까지 유료 도로를 만든 다음 더 저렴한 고속도로가 있다는 것을 발견했다고 가정해 보겠습니다. 이 시점에서 루프에 뉴욕을 추가하고 시카고까지 값비싼 도로를 따라 달리고 다시 값싼 경로를 따라 돌아오면 값비싼 경로를 대체하는 루프가 생성되어 전체 교통 비용이 절감됩니다.

캐나다 빅토리아 대학의 발레리 킹(Valerie King)은 이 방법이 '전기적 방법'보다 더 많은 단계를 사용하기 때문에 언뜻 '한 단계 뒤로 물러나는 것'처럼 들린다고 말합니다. 이를 보완하기 위해 알고리즘은 전체 네트워크를 검사하는 데 걸리는 것보다 믿을 수 없을 정도로 빠르게 모든 단계에서 좋은 루프를 찾아야 합니다.

이것이 Spielman과 Teng의 알고리즘이 작동하는 방식입니다. 그들의 알고리즘은 알고리즘의 핵심이며 네트워크의 가장 두드러진 특징을 많이 포착할 수 있는 "낮은 확장 스패닝 트리"를 사용하는 새로운 방법을 제공합니다. 그러한 트리가 주어지면 트리 외부에 링크를 추가하여 적어도 하나의 양호한 순환을 구성하는 것이 항상 가능합니다. 따라서 낮은 규모의 스패닝 트리를 사용하면 고려해야 할 사이클 수를 크게 줄일 수 있습니다.

그래도 알고리즘을 빠르게 실행하기 위해 팀에서는 매 단계마다 새로운 스패닝 트리를 구축할 수 없습니다. 대신, 각각의 새로운 주기가 스패닝 트리에 작은 파급 효과만 생성하여 대부분의 이전 계산이 재사용되도록 해야 합니다. 이 수준의 제어를 달성하는 것이 "핵심 어려움"이라고 스탠포드 대학교 대학원생이자 논문 저자 중 한 명인 Yang Liu는 말했습니다.

궁극적으로 연구원들은 "거의 선형" 시간으로 실행되는 알고리즘을 만들었습니다. 즉, 대규모 네트워크를 사용할 때 실행 시간이 m에 가까워집니다.

이 알고리즘은 Spielman과 Teng의 많은 아이디어를 빌려와 완전히 새로운 것으로 결합합니다. 말이 끄는 수레만 본 적이 있다면 오늘날의 알고리즘은 자동차와 같다고 Spielman은 말했습니다. "앉을 곳도 있고, 바퀴도 있고, 움직일 수 있는 것도 있는 것 같아요. 그런데 말을 엔진으로 교체한 것 같아요."

Rao는 팀의 분석이 길었다고 추측합니다. 그러나 다른 연구자들은 곧 문제를 단순화하기 위해 노력했습니다. Spielman은 "내 생각에는 앞으로 몇 년 안에 모든 것이 더 깨끗해지고 좋아질 것"이라고 말했습니다. 일단 알고리즘이 단순화되면 컴퓨터 과학자들은 이를 다양한 문제를 해결하기 위한 알고리즘으로 사용할 수 있다고 Spielman은 말했습니다. "이제 우리는 이 작업을 매우 빠르게 수행할 수 있다는 것을 알았으므로 사람들은 이전에 생각하지 못했던 모든 종류의 응용 프로그램을 찾을 수 있습니다."

게다가 최대 흐름 문제에 대한 알고리즘의 현기증나는 속도 향상은 Spielman을 기대하게 만들었습니다. 알고리즘 이론의 또 다른 핵심 이슈, "우리가 또 무엇을 할 수 있을까?"

위 내용은 기본적인 컴퓨터 문제, 최대 흐름 문제가 획기적인 진전을 이루었습니다. 새로운 알고리즘은 '어리석을 정도로 빠릅니다'의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!