매개변수화된 알고리즘을 사용하여 NP-하드 문제를 해결하는 방법

연구 작업은 아마도 우리 교육에서 가장 흥미로운 부분일 것입니다. 대학에 있는 동안 자신이 선택한 방향으로 자신을 시험해 보는 것이 아이디어입니다. 예를 들어, 소프트웨어 엔지니어링 및 기계 학습 분야의 학생들은 종종 회사(주로 JetBrains 또는 Yandex뿐만 아니라)에서 연구를 하러 갑니다.

이번 포스팅에서는 컴퓨터 과학 분야의 프로젝트에 대해 이야기하겠습니다. 작업의 일환으로 저는 가장 유명한 NP-하드 문제 중 하나를 해결하기 위한 접근 방식을 연구하고 실천했습니다. 꼭지점 덮기 문제.

요즘 NP-난해 문제에 대한 흥미로운 접근 방식은 매우 빠르게 매개변수화된 알고리즘을 개발하는 것입니다. 나는 여러분에게 최신 정보를 제공하고 몇 가지 간단한 매개변수화된 알고리즘을 설명하고 나에게 많은 도움이 된 강력한 방법을 설명하려고 노력할 것입니다. 저는 PACE Challenge 대회에서 결과를 발표했습니다. 공개 테스트 결과에 따르면 제 솔루션이 1위를 차지했으며 최종 결과는 XNUMX월 XNUMX일에 발표될 예정입니다.

성명서

제 이름은 Vasily Alferov입니다. 저는 현재 상트페테르부르크 국립 연구 대학 고등 경제 학교에서 179학년을 마치고 있습니다. 저는 모스크바 학교 No. XNUMX에서 공부하고 컴퓨터 과학 올림피아드에 성공적으로 참가했던 학창 시절부터 알고리즘에 관심이 있었습니다.

매개변수화된 알고리즘의 한정된 수의 전문가가 참여합니다...

책에서 가져온 예 "매개변수화된 알고리즘"

당신이 작은 마을의 술집 경비원이라고 상상해 보세요. 매주 금요일이면 도시의 절반이 휴식을 취하기 위해 바에 옵니다. 이는 당신에게 많은 문제를 안겨줍니다. 싸움을 방지하려면 소란스러운 고객을 바 밖으로 내쫓아야 합니다. 결국, 당신은 지쳐서 예방 조치를 취하기로 결정합니다.

귀하의 도시는 작기 때문에 고객이 술집에 함께 가게 되면 어떤 쌍의 고객이 싸울 가능성이 있는지 정확히 알 수 있습니다. 다음 목록이 있나요? n 오늘 밤 바에 올 사람들. 당신은 누구도 싸움에 참여하지 않도록 몇몇 마을 사람들을 술집에 들어오지 못하게 하기로 결정했습니다. 동시에, 당신의 상사는 이익을 잃는 것을 원하지 않으며 당신이 그 이상을 허용하지 않으면 불행해질 것입니다. k 명.

불행하게도 당신 앞에 놓인 문제는 고전적인 NP-hard 문제입니다. 당신은 그녀를 다음과 같이 알 수도 있습니다. 정점 커버, 또는 정점 덮기 문제로 사용됩니다. 이러한 문제의 경우 일반적으로 허용 가능한 시간에 작동하는 알고리즘이 없습니다. 정확하게 말하면, 입증되지 않았지만 꽤 강력한 가설인 ETH(Exponential Time Hypothese)는 이 문제가 시간 내에 해결될 수 없다고 말합니다. , 즉, 완전한 검색보다 눈에 띄게 더 나은 것을 생각할 수 없습니다. 예를 들어, 누군가가 당신의 술집에 올 것이라고 가정해 봅시다. N = 1000 인간. 그러면 전체 검색은 다음과 같습니다. 대략적인 옵션이 있습니다. - 미친 금액. 다행히 경영진이 제한을 두었습니다. k = 10이므로 반복해야 하는 조합의 수가 훨씬 적습니다. 즉, XNUMX개 요소의 하위 집합 수는 다음과 같습니다. . 이것이 더 좋지만 강력한 클러스터에서도 여전히 하루에 계산되지 않습니다.

바 방문자 간의 긴장된 관계 구성에서 싸움의 가능성을 제거하려면 Bob, Daniel 및 Fedor를 쫓아내야 합니다. 두 명만 남게 되는 해결책은 없습니다.

이것은 포기하고 모든 사람을 받아들여야 할 때라는 것을 의미합니까? 다른 옵션을 고려해 봅시다. 예를 들어, 매우 많은 수의 사람들과 싸울 가능성이 있는 사람들만 들여보내서는 안 됩니다. 누군가가 적어도 싸울 수 있다면 k+1 다른 사람이 있으면 그 사람을 들여보내줄 수 없습니다. 그렇지 않으면 모든 사람이 들어오지 못하게 해야 합니다. k+1 그가 싸울 수있는 마을 사람들은 확실히 지도력을 화나게 할 것입니다.

이 원칙에 따라 가능한 모든 사람을 버리십시오. 그러면 다른 사람들은 모두 더 이상 싸울 수 없습니다 k 사람들. 그것들을 버리고 k 이봐, 너는 그 이상을 막을 수 없어 갈등. 즉, 그 이상이면 어떤 사람이 적어도 하나의 갈등에 연루되어 있다면 모든 갈등을 예방할 수는 없습니다. 물론 완전히 갈등이 없는 사람들을 확실히 받아들일 것이기 때문에 XNUMX명 중 XNUMX명 규모의 모든 하위 집합을 통과해야 합니다. 대략적으로 있습니다 , 이 작업 수는 이미 클러스터에서 정렬될 수 있습니다.

갈등이 전혀 없는 개인을 안전하게 데려갈 수 있다면, 한 번의 갈등에만 참여하는 사람들은 어떨까요? 실제로 상대방의 문을 닫아서 들어갈 수도 있습니다. 실제로 Alice가 Bob과만 충돌하는 경우 두 사람 중에서 Alice를 내보내더라도 우리는 잃지 않을 것입니다. Bob은 다른 충돌이 있을 수 있지만 Alice에게는 확실히 그러한 충돌이 없습니다. 더욱이 우리 둘 다 들여보내지 않는 것은 말이 되지 않습니다. 그러한 작업 후에는 더 이상 남아 있지 않습니다. 운명이 결정되지 않은 손님: 우리는 갈등은 각각 두 명의 참가자로 구성되며 각각은 적어도 두 명과 관련됩니다. 그럼 이제 남은 건 정리뿐 노트북에서는 반나절이면 쉽게 고려될 수 있는 옵션입니다.

실제로 간단한 추론을 통해 훨씬 더 매력적인 조건을 얻을 수 있습니다. 모든 분쟁을 해결해야 합니다. 즉, 충돌하는 각 쌍에서 허용하지 않을 사람을 한 명 이상 선택해야 합니다. 다음 알고리즘을 고려해 보겠습니다. 충돌이 발생하면 참가자 한 명을 제거하고 나머지에서 재귀적으로 시작한 다음 다른 참가자를 제거하고 재귀적으로 시작합니다. 우리는 모든 단계에서 누군가를 버리기 때문에 그러한 알고리즘의 재귀 트리는 깊이의 이진 트리입니다. k, 그래서 전체적으로 알고리즘은 다음과 같이 작동합니다. 어디에서 n 는 꼭짓점의 수이고, m - 갈비뼈의 수. 이 예에서는 약 천만 달러로 노트북뿐만 아니라 휴대폰에서도 순식간에 계산할 수 있습니다.

위의 예시는 예시입니다 매개변수화된 알고리즘. 매개변수화된 알고리즘은 시간에 맞춰 실행되는 알고리즘입니다. f(k) 폴리(n)어디에서 p - 다항식, f 임의의 계산 가능한 함수이고, k - 문제의 크기보다 훨씬 작은 일부 매개변수.

이 알고리즘 이전의 모든 추론은 예를 제공합니다. 커널화 매개변수화된 알고리즘을 생성하는 일반적인 기술 중 하나입니다. 커널화는 문제 크기를 매개변수의 기능에 의해 제한되는 값으로 줄이는 것입니다. 결과적인 문제를 종종 커널이라고 부릅니다. 따라서 정점의 정도에 대한 간단한 추론을 통해 우리는 정점 커버 문제에 대한 답의 크기에 따라 매개변수화된 XNUMX차 커널을 얻었습니다. 이 작업에 대해 선택할 수 있는 다른 설정(예: LP 위의 Vertex Cover)이 있지만 이것이 우리가 논의할 설정입니다.

페이스 챌린지

경쟁 페이스 챌린지 (매개변수화된 알고리즘 및 계산 실험 챌린지)는 계산 문제를 해결하기 위해 실제로 사용되는 매개변수화된 알고리즘과 접근 방식 간의 연결을 확립하기 위해 2015년에 탄생했습니다. 처음 세 번의 대회는 그래프의 트리 너비를 찾는 데 전념했습니다(트리 너비), 스타이너 트리 검색(슈타이너 트리) 그리고 사이클을 자르는 정점 세트를 검색합니다(피드백 정점 세트). 올해 여러분이 시도해 볼 수 있는 문제 중 하나는 위에서 설명한 정점 덮기 문제였습니다.

이 대회는 매년 인기를 얻고 있습니다. 예비 데이터를 믿으시면 올해 24개 팀이 정점 덮기 문제만 해결하기 위해 대회에 참가했습니다. 경쟁이 몇 시간이나 일주일이 아니라 몇 달 동안 지속된다는 점은 주목할 가치가 있습니다. 팀은 문헌을 연구하고 자신만의 독창적인 아이디어를 생각해내고 이를 구현해 볼 수 있는 기회를 갖습니다. 본질적으로 이번 대회는 연구 프로젝트입니다. 가장 효과적인 솔루션에 대한 아이디어와 우승자 시상은 컨퍼런스와 함께 진행됩니다. IPEC (매개변수화 및 정확한 계산에 관한 국제 심포지엄)은 유럽 최대 규모의 연례 알고리즘 회의의 일부입니다. ALGO. 대회 자체에 대한 자세한 내용은 다음에서 확인할 수 있습니다. 온라인으로, 전년도 결과는 거짓말 여기에.

솔루션 체계

정점 덮기 문제를 해결하기 위해 매개변수화된 알고리즘을 사용해 보았습니다. 일반적으로 단순화 규칙(이상적으로는 커널화로 이어짐)과 분할 규칙의 두 부분으로 구성됩니다. 단순화 규칙은 다항식 시간에 입력을 전처리하는 것입니다. 이러한 규칙을 적용하는 목적은 문제를 동등한 더 작은 문제로 줄이는 것입니다. 단순화 규칙은 알고리즘에서 가장 비용이 많이 드는 부분이며, 이 부분을 적용하면 전체 실행 시간이 늘어납니다. 단순한 다항식 시간 대신. 우리의 경우 분할 규칙은 각 꼭지점에 대해 해당 꼭지점이나 그 이웃을 답으로 가져와야 한다는 사실을 기반으로 합니다.

일반적인 계획은 다음과 같습니다. 단순화 규칙을 적용한 다음 일부 정점을 선택하고 두 번의 재귀 호출을 수행합니다. 첫 번째에서는 응답으로 이를 취하고 다른 하나에서는 모든 이웃을 취합니다. 이것이 바로 이 정점을 따라 분할(분기)이라고 부르는 것입니다.

다음 단락에서는 이 체계에 정확히 한 가지를 추가할 것입니다.

분할(브런칭) 규칙에 대한 아이디어

분할이 발생할 꼭지점을 선택하는 방법에 대해 논의해 보겠습니다.
주요 아이디어는 알고리즘 측면에서 매우 탐욕적입니다. 즉, 최대 차수의 꼭지점을 가져와 이를 따라 분할해 보겠습니다. 왜 더 나은 것 같나요? 재귀 호출의 두 번째 분기에서는 이런 방식으로 많은 정점을 제거하기 때문입니다. 작은 그래프만 남아 있으면 신속하게 작업할 수 있습니다.

이미 논의된 간단한 커널화 기술을 사용하는 이 접근 방식은 그 자체로 잘 나타나며 수천 개의 정점 크기에 대한 일부 테스트를 해결합니다. 하지만 예를 들어 큐빅 그래프(즉, 각 꼭지점의 차수가 XNUMX인 그래프)에는 잘 작동하지 않습니다.
매우 간단한 아이디어에 기초한 또 다른 아이디어가 있습니다. 그래프의 연결이 끊어지면 연결된 구성 요소의 문제는 마지막에 답변을 결합하여 독립적으로 해결할 수 있습니다. 그건 그렇고, 이것은 계획의 작은 약속 수정으로 솔루션 속도를 크게 높일 것입니다. 이전에 이 경우 우리는 구성 요소의 응답을 계산하기 위해 시대의 제품을 위해 작업했지만 지금은 다음을 위해 작업합니다. 합계. 그리고 분기 속도를 높이려면 연결된 그래프를 연결되지 않은 그래프로 바꿔야 합니다.

어떻게 하나요? 그래프에 연결 지점이 있으면 그 지점에서 싸워야 합니다. 연결점은 제거되면 그래프의 연결성을 잃는 꼭지점입니다. 그래프의 모든 연결점은 선형 시간의 고전적인 알고리즘을 사용하여 찾을 수 있습니다. 이 접근 방식은 분기 속도를 크게 향상시킵니다.

선택한 정점 중 하나라도 제거되면 그래프는 연결된 구성 요소로 분할됩니다.

우리는 이것을 할 것이지만 더 많은 것을 원합니다. 예를 들어, 그래프에서 작은 정점 절단을 찾아 정점을 따라 분할합니다. 최소 전역 정점 컷을 찾는 가장 효율적인 방법은 입방 시간으로 구성된 Gomori-Hu 트리를 사용하는 것입니다. PACE Challenge에서 일반적인 그래프 크기는 수천 개의 정점입니다. 이 상황에서는 재귀 트리의 각 꼭지점에서 수십억 개의 작업을 수행해야 합니다. 할당된 시간 내에 문제를 해결하는 것은 단순히 불가능하다는 것이 밝혀졌습니다.

솔루션을 최적화해 보겠습니다. 정점 쌍 사이의 최소 정점 절단은 최대 흐름을 구성하는 모든 알고리즘으로 찾을 수 있습니다. 그러한 네트워크에 허용할 수 있습니다. 디니츠 알고리즘, 실제로는 매우 빠르게 작동합니다. 작동시간에 대한 추정치를 이론적으로 증명하는 것이 가능한지 의구심이 듭니다. , 이는 이미 상당히 수용 가능합니다.

나는 무작위 정점 쌍 사이의 절단점을 찾고 가장 균형 잡힌 정점을 선택하기 위해 여러 번 시도했습니다. 불행하게도 이는 공개 PACE Challenge 테스트에서 좋지 않은 결과를 가져왔습니다. 최대 차수의 정점을 분할하여 하강 깊이에 제한을 두어 실행하는 알고리즘과 비교했습니다. 이러한 방식으로 컷을 찾으려는 알고리즘은 더 큰 그래프 뒤에 남습니다. 이는 컷의 균형이 매우 불균형한 것으로 나타났기 때문입니다. 5-10개의 정점을 제거한 후 15-20개만 분할할 수 있었습니다.

이론적으로 가장 빠른 알고리즘에 관한 기사에서는 분할할 정점을 선택하는 데 훨씬 더 고급 기술을 사용한다는 점은 주목할 가치가 있습니다. 이러한 기술은 구현이 매우 복잡하고 시간과 메모리 측면에서 성능이 떨어지는 경우가 많습니다. 나는 연습에 꽤 적합한 것들을 식별할 수 없었습니다.

단순화 규칙을 적용하는 방법

우리는 이미 커널화에 대한 아이디어를 갖고 있습니다. 상기시켜 드리겠습니다.

1. 고립된 정점이 있으면 삭제합니다.
2. 1차 정점이 있는 경우 이를 제거하고 응답으로 이웃을 가져옵니다.
3. 적어도 정도의 정점이 있는 경우 k+1, 다시 가져.

처음 두 개에는 모든 것이 명확하고 세 번째에는 하나의 트릭이 있습니다. 술집에 관한 만화 문제에서 우리에게 다음과 같은 상한선이 주어졌다면 k, PACE Challenge에서는 최소 크기의 꼭지점 덮개만 찾으면 됩니다. 이는 검색 문제를 결정 문제로 변환하는 전형적인 현상으로, 두 가지 유형의 문제 사이에 차이가 없는 경우가 많습니다. 실제로 정점 덮기 문제에 대한 솔버를 작성하는 경우 차이가 있을 수 있습니다. 예를 들어 세 번째 요점과 같습니다.

구현 관점에서 진행하는 방법에는 두 가지가 있습니다. 첫 번째 접근 방식은 반복 심화(Iterative Deepening)라고 합니다. 그것은 다음과 같습니다: 답에 대한 아래의 합리적인 제약 조건으로 시작한 다음, 이 제약 조건보다 재귀가 낮아지지 않고 위의 답에 대한 제약 조건으로 이 제약 조건을 사용하여 알고리즘을 실행할 수 있습니다. 어떤 답을 찾았다면 최적의 답이 보장됩니다. 그렇지 않으면 이 제한을 XNUMX만큼 늘리고 다시 시작할 수 있습니다.

또 다른 접근 방식은 현재 최적의 답을 저장하고 더 작은 답을 찾아서 발견되면 이 매개변수를 변경하는 것입니다. k 검색에서 불필요한 가지를 더 많이 차단합니다.

여러 번의 야간 실험을 수행한 후 저는 이 두 가지 방법을 조합하기로 결정했습니다. 먼저 검색 깊이에 대해 일종의 제한을 두고 알고리즘을 실행하고(주 솔루션에 비해 시간이 거의 걸리지 않도록 선택) 가장 좋은 방법을 사용합니다. 답에 대한 상한으로 발견된 해, 즉 동일한 것에 대한 해 k.

2차 꼭짓점

우리는 0차와 1차 정점을 다루었습니다. 이는 2차 정점으로 수행될 수 있지만 그래프에서 더 복잡한 작업이 필요합니다.

이를 설명하려면 어떻게든 정점을 지정해야 합니다. 2차 꼭지점을 꼭지점이라고 부르자. v, 및 그 이웃 - 정점 x и y. 다음으로 두 가지 경우를 살펴보겠습니다.

1. 언제 x и y - 이웃. 그러면 대답할 수 있다 x и y과 v 삭제. 실제로 이 삼각형에서 최소한 두 개의 꼭지점을 가져와야 하며, 이를 취하더라도 절대 잃지 않을 것입니다. x и y: 그들은 아마도 다른 이웃이 있을 것이고, 그리고 v 그들은 여기에 없습니다.
2. 언제 x и y - 이웃이 아닙니다. 그런 다음 세 꼭지점을 모두 하나로 붙일 수 있다고 명시되어 있습니다. 아이디어는 이 경우에 우리가 취하는 최적의 답이 있다는 것입니다. v또는 두 정점 모두 x и y. 또한 첫 번째 경우에는 이에 대응하여 모든 이웃을 취해야합니다. x и y, 그러나 두 번째에는 필요하지 않습니다. 이는 접착된 정점을 응답으로 취하지 않고 취하는 경우와 정확히 일치합니다. 두 경우 모두 그러한 작업의 응답이 XNUMX씩 감소한다는 점만 참고하면 됩니다.

이 접근 방식은 공정한 선형 시간 내에 정확하게 구현하기가 매우 어렵다는 점은 주목할 가치가 있습니다. 정점을 붙이는 것은 복잡한 작업이므로 이웃 목록을 복사해야 합니다. 이 작업을 부주의하게 수행하면 점근적으로 차선의 실행 시간이 발생할 수 있습니다(예를 들어 각 접착 후 많은 가장자리를 복사하는 경우). 나는 2차 꼭지점에서 전체 경로를 찾고 그러한 꼭지점 또는 하나를 제외한 모든 꼭지점의 순환과 같은 여러 특수 사례를 분석하기로 결정했습니다.

또한, 이 작업은 되돌릴 수 있어야 하므로 재귀에서 돌아올 때 그래프를 원래 형태로 복원할 수 있습니다. 이를 보장하기 위해 병합된 정점의 가장자리 목록을 지우지 않았으며, 그런 다음 어떤 가장자리가 어디로 가야 하는지만 알았습니다. 이 그래프 구현에도 정확성이 필요하지만 공정한 선형 시간을 제공합니다. 그리고 수만 개의 에지 그래프의 경우 프로세서 캐시에 적합하므로 속도면에서 큰 이점을 제공합니다.

선형 커널

마지막으로 커널의 가장 흥미로운 부분입니다.

우선, 이분 그래프에서 최소 정점 커버는 다음을 사용하여 찾을 수 있다는 것을 기억하십시오. . 이렇게 하려면 알고리즘을 사용해야 합니다. 홉크로프트-카프 거기에서 최대 일치를 찾고 정리를 사용하려면 쾨니히-에게르바리.

선형 커널의 아이디어는 다음과 같습니다. 먼저 각 정점 대신 그래프를 두 갈래로 나눕니다. v 피크 두 개를 추가해 보겠습니다. и , 그리고 각 가장자리 대신 너 - v 갈비뼈 두 개를 추가하자 и . 결과 그래프는 이분형이 됩니다. 그 안에서 최소 꼭짓점 피복을 찾아보겠습니다. 원래 그래프의 일부 정점은 두 번 도달하고 일부는 한 번만 도달하며 일부는 전혀 도달하지 않습니다. Nemhauser-Trotter 정리에 따르면 이 경우 한 번도 맞지 않은 정점을 제거하고 두 번 맞은 정점을 다시 가져올 수 있습니다. 게다가 그녀는 나머지 정점(한 번 맞은 정점) 중 적어도 절반을 답으로 가져와야 한다고 말합니다.

우리는 이제 막 떠나는 법을 배웠습니다. 2k 봉우리 실제로 나머지 답이 모든 꼭지점의 절반 이상인 경우 총합에서 다음보다 더 많은 꼭지점은 없습니다. 2k.

여기서 나는 작은 발걸음을 내딛을 수 있었다. 이러한 방식으로 구성된 커널은 이분 그래프에서 어떤 종류의 최소 정점 커버를 취하는지에 따라 달라집니다. 남은 정점 수가 최소화되도록 하나를 취하고 싶습니다. 이전에는 시간 내에만 이 작업을 수행할 수 있었습니다. . 나는 당시에 이 알고리즘의 구현을 생각해 냈습니다. 따라서 이 코어는 각 분기 단계에서 수십만 개의 정점 그래프에서 검색될 수 있습니다.

결과

실습에 따르면 내 솔루션은 수백 개의 꼭지점과 수천 개의 모서리에 대한 테스트에서 잘 작동합니다. 이러한 테스트에서는 10분 안에 해결책을 찾을 것으로 예상할 수 있습니다. 원칙적으로 그래프에 차수가 XNUMX 이상인 정점이 많으면 허용되는 시간에 답을 찾을 확률이 높아집니다.

대회에 참가하려면 다음 주소로 솔루션을 보내야 했습니다. optil.io. 거기에 제시된 정보로 판단하면 태블릿, 공개 테스트에서 내 솔루션은 XNUMX개 중 XNUMX위를 차지했으며 XNUMX위와 큰 차이가 있습니다. 솔직히 말해서 대회 자체에서 솔루션이 어떻게 평가되는지 완전히 명확하지 않습니다. 예를 들어 내 솔루션은 XNUMX위의 솔루션보다 더 적은 수의 테스트를 통과하지만 통과한 솔루션에서는 더 빠르게 작동합니다.

비공개 테스트 결과는 XNUMX월 XNUMX일 발표된다.

출처 : habr.com