폭탄 적하 알고리즘
n x m음수가 아닌 정수로 구성된 행렬 이 있습니다 . 예를 들면 다음과 같습니다.
2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4
"폭탄 제거"는 대상 군의 수와 그 이웃 8 개를 최소 0으로 줄입니다.
x x x
x X x
x x x
모든 셀을 0으로 줄이는 데 필요한 최소 폭탄 수를 결정하는 알고리즘은 무엇입니까?
B 옵션 (주의 독자가 아니기 때문에)
실제로 첫 번째 버전의 문제는 내가 찾고있는 것이 아닙니다. 나는 전체 작업을주의 깊게 읽지 않았으며 추가 제약이 있습니다.
연속열이 증가하지 않아야하는 간단한 문제는 무엇입니까?
8 7 6 6 5 가능한 입력 순서입니다
7 8 5 5 2 순서대로 7-> 8 성장하기 때문에 불가능합니다.
어쩌면 "쉬운"사례에 대한 답변을 찾는 것이 더 어려운 솔루션을 찾는 데 도움이 될 것입니다.
추신 : 나는 우리가 동일한 상황을 여러 번 가질 때 상단 줄을 정리하기 위해 최소 폭탄이 필요하다고 생각합니다. 행의 "왼쪽"에서 대부분의 폭탄을 사용하는 것을 선택합니다. 여전히 올바른 증거가 있습니까?
이것을 간단한 하위 문제로 줄이는 방법이 있습니다.
설명에는 알고리즘과 알고리즘이 최적의 솔루션을 제공하는 이유의 두 부분이 있습니다. 첫 번째는 두 번째가 없으면 이해가되지 않으므로 그 이유부터 시작하겠습니다.
직사각형 폭격을 생각한다면 (아직 큰 직사각형을 가정하십시오-가장자리가없는 것으로 가정하십시오) 경계에서 빈 사각형의 사각형을 0으로 줄이는 유일한 방법은 경계를 폭파하거나 중공 사각형을 폭파하는 것입니다. 주변의 정사각형. 경계 레이어 1을 호출하고 그 안에있는 사각형을 레이어 2라고합니다.
중요한 통찰력은 포인트 폭격 레이어 1이 없다는 것입니다. 그렇게하는 "폭발 반경"은 항상 레이어 2의 다른 사각형 폭파 반경 내에 포함되어 있기 때문에 쉽게 확신 할 수 있어야합니다.
따라서 주변을 폭파시키는 최적의 방법을 찾는 데 따른 문제를 줄일 수 있으며, 모든 제곱이 0이 될 때까지 반복 할 수 있습니다.
그러나 최적의 방식보다 주변을 폭격하는 것이 가능하다면 항상 최적의 솔루션을 찾지 못할 수도 있지만 X 여분의 폭탄을 사용하여> X 폭탄으로 내부 레이어를 단순화하는 문제가 발생합니다. 따라서 우리가 허가자 레이어 1이라고 부르면 레이어 2 어딘가에 (추가 레이어 1) 추가 X 폭탄을 배치하면 나중에 레이어 2를 X보다 더 폭격시키는 노력을 줄일 수 있습니까? 다시 말해, 우리는 바깥 둘레를 줄이는 데 욕심이있을 수 있음을 증명해야합니다.
그러나 우리는 우리가 탐욕 스러울 수 있다는 것을 알고 있습니다. 레이어 2의 폭탄은 레이어 3에 전략적으로 배치 된 폭탄보다 레이어 2를 0으로 줄이는 데 더 효율적일 수 없기 때문에 이전과 같은 이유로 항상 레이어 3에 배치 할 수있는 폭탄이 모든 사각형에 영향을 줄 수 있습니다 레이어 2에 배치 된 폭탄이 할 수있는 레이어 2의 그러므로 욕심을 느끼는 것은 결코 우리에게 해를 끼칠 수 없습니다 (이 욕심의 의미에서).
따라서 우리가해야 할 일은 다음 내층을 폭격함으로써 허가자를 0으로 줄이는 최적의 방법을 찾는 것입니다.
내부 레이어의 모서리 만 도달 할 수 있기 때문에 모서리를 0으로 먼저 폭파해도 결코 아프지 않습니다. 따라서 실제로는 선택의 여지가 없습니다 (모퉁이에 도달 할 수있는 주변의 모든 폭탄에는 폭발 반경이 포함되어 있음) 내부 레이어의 모서리에서 폭발 반경).
일단 그렇게하면 0 코너에 인접한 주변의 사각형은 내부 레이어에서 2 사각형으로 만 도달 할 수 있습니다.
0 A B
C X Y
D Z
이 시점에서 주변은 효과적으로 닫힌 1 차원 루프입니다. 폭탄이 있으면 인접한 3 개의 사각형이 줄어들 기 때문입니다. 모퉁이 근처의 이상한 점을 제외하고-X는 A, B, C 및 D를 "치게"할 수 있습니다.
이제 우리는 블라스트 반경 트릭을 사용할 수 없습니다. 각각의 상황은 이상한 코너를 제외하고 대칭이며 블라스트 반경은 다른 서브셋이 아닙니다. 폐 루프 대신에 (패닉 대령이 논의한 바와 같이) 이것이 선이라면 해결책은 사소한 것입니다. 끝점은 0으로 줄여야하며, 폭발 반경이 수퍼 셋이기 때문에 끝점에 인접한 점을 폭격하는 데 아무런 해가 없습니다. 엔드 포인트를 0으로 설정 한 후에도 여전히 새 엔드 포인트가 있으므로 반복하십시오 (라인이 모두 0이 될 때까지).
따라서 레이어의 단일 정사각형을 0으로 최적으로 줄일 수 있다면 알고리즘이 있습니다 (루프를 자르고 끝점과 직선이 있기 때문에). 나는 가장 낮은 값을 가진 정사각형에 인접한 폭격 (2 옵션을 제공)이 가장 낮은 값의 2 제곱 내에서 가장 높은 값이 가능한 최소값이라고 생각합니다 (이를 관리하기 위해 폭탄을 분할해야 할 수도 있음) 아직 증거가 없습니다.
Pólya는 "문제를 해결할 수 없다면 해결할 수있는 더 쉬운 문제가 있습니다. 찾으십시오"라고 말합니다.
가장 간단한 문제는 1 차원 문제입니다 (그리드가 단일 행인 경우). 가장 간단한 알고리즘부터 시작하겠습니다. 가장 큰 목표를 탐욕스럽게 폭파하십시오. 언제 잘못 되나요?
을 감안할 때 1 1 1, 욕심 알고리즘은 먼저 어느 셀이 폭탄에 무관심하다. 물론 가운데 셀이 더 좋습니다. 세 셀을 모두 한 번에 0으로 만듭니다. 이것은 새로운 알고리즘 A, "남은 합계를 최소화하기위한 폭탄"을 제안합니다. 이 알고리즘은 언제 잘못됩니까?
을 감안할 때 1 1 2 1 1, 알고리즘 A는 2, 3 또는 4 세포를 폭격 무차별입니다. 그러나 두 번째 칸을 떠나는 0 0 1 1 1것은 세 번째 칸을 떠나는 것보다 낫습니다 1 0 1 0 1. 그것을 고치는 방법? 세 번째 셀을 폭격하는 문제는 우리가 왼쪽으로 일하고 오른쪽으로 일해야한다는 것입니다.
"남은 금액을 최소화하기 위해 폭탄을 쓰지만 폭탄의 왼쪽에 최소값을 더한 다음 오른쪽에 최소값을 최대화하는 것은 어떻습니까?" 이 알고리즘 B를 호출하십시오.이 알고리즘은 언제 잘못됩니까?
편집 : 의견을 읽은 후, 훨씬 흥미로운 문제는 1 차원 문제가 변경되어 끝이 합쳐질 것이라는 데 동의합니다. 그 진행 상황을보고 싶습니다.
시간이 없어서 부분 솔루션 만 중단해야했지만이 부분 솔루션 조차도이 문제를 해결하기위한 하나의 잠재적 접근법에 대한 통찰력을 제공하기를 바랍니다.
어려운 문제에 직면했을 때 나는 문제 공간에 대한 직관을 개발하기 위해 더 간단한 문제를 생각해 내고 싶습니다. 여기서 내가 취한 첫 번째 단계는이 2 차원 문제를 1 차원 문제로 줄이는 것입니다. 라인을 고려하십시오 :
0 4 2 1 3 0 1
어떻게 든 또는 다른, 당신은 당신이 또는 그 주위에 폭탄을 투하해야합니다 알고 4폭격에 아무런 혜택이없는, 낮은 숫자가 그 자리의 왼쪽부터 0으로 내려 4 번 자리 0또는를 4을 폭격 이상은 2. 사실, 나는 2그 4지점이 0으로 내려갈 때까지 폭탄을 쏘는 것이 적어도 다른 전략만큼이나 좋다는 것을 믿습니다 (그러나 엄격한 증거는 없습니다). 전략에서 4왼쪽에서 오른쪽으로 줄을 내려갈 수 있습니다 이처럼 :
index = 1
while index < line_length
while number_at_index(index - 1) > 0
bomb(index)
end
index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
bomb(index - 1)
end
몇 가지 샘플 폭탄 주문 :
0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0
4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0
어떤 식 으로든 내려 가야하는 숫자로 시작한다는 아이디어는 매력적입니다. 어떤 다른 솔루션보다 적어도 우수하다고 주장하는 솔루션을 갑자기 찾을 수 있기 때문 입니다.
최소한 선을 찾는 것이 여전히 가능한 복잡성의 다음 단계 는 보드의 가장자리에 있습니다. 바깥 쪽 가장자리를 폭격 할 때 어떤 엄밀한 이점도 없다는 것이 분명합니다. 그 자리를 폭격하고 다른 3 곳을 무료로 얻는 것이 좋습니다. 이것을 감안할 때, 우리는 가장자리 안쪽에서 링 을 폭파시키는 것이 가장자리를 폭파시키는 것 이상 이라고 말할 수 있습니다 . 더구나, 우리는 이것을 가장자리의 오른쪽 내부를 폭파시키는 것이 실제로 가장자리 공간을 0으로 낮추는 유일한 방법이라는 직관과 결합 할 수 있습니다. 더 나아가, 최적의 전략을 알아내는 것은 아주 간단합니다. 모퉁이 숫자를 0으로 낮추는 것입니다. 우리는 이것을 모아서 2 차원 공간의 솔루션에 훨씬 더 가까이 갈 수 있습니다.
코너 피스에 대한 관찰을 고려하면 모든 시작 보드에서 모든 코너에 0이있는 보드로가는 최적의 전략을 알고 있다고 말할 수 있습니다. 이것은 그러한 보드의 예입니다 (위의 두 선형 보드에서 숫자를 빌 렸습니다). 공백을 다르게 표시했는데 그 이유를 설명하겠습니다.
0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0
하나는 상단 행에서 알 정말 밀접하게 우리가 이전에 보았던 선형 예제와 유사한. 앞줄을 모두 0으로 낮추는 가장 좋은 방법은 두 번째 줄 ( x줄) 을 폭파하는 것 입니다. 행을 폭격하여 맨 위 행을 지우는 방법은 없으며 y행의 해당 공간을 폭격하는 것보다 맨 위 행을 폭격하는 추가 이점이 없습니다 x.
우리는 수 (상의 해당 공간 폭격 위에서 선형 전략을 적용 x자신 직결 된 행) 만 상단의 행과 다른 아무것도. 다음과 같이 갈 것입니다.
0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0
0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0
0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0
0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0
0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0
이 접근 방식의 결점은 마지막 두 차례의 폭탄 테러에서 매우 분명해집니다. 4두 번째 행의 첫 번째 열에 있는 숫자 를 줄이는 유일한 폭탄 사이트 는 첫 번째 사이트 x와 y. 마지막 두 번의 폭탄 공격은 첫 번째 폭탄을 폭격 x하는 것 보다 분명히 열등합니다 . 이는 똑같은 일을 할 것입니다 (맨 위 줄의 첫 번째 지점과 관련하여 다른 정리 방법은 없습니다). 현재의 전략이 차선 책임을 입증 했으므로 전략을 수정해야합니다.
이 시점에서 복잡성을 한 단계 물러나 한 구석에 집중할 수 있습니다. 이것을 고려해 봅시다 :
0 4 2 1
4 x y a
2 z . .
1 b . .
그것은과 공간을 얻을 수있는 유일한 방법 분명하다 4의 조합을 폭격 할 수있는 제로에 이르기를 x, y하고 z. 내 곡예를 생각하면 최적의 솔루션이 x세 번 폭격 을 한 a다음 확실하게 확신합니다 b. 이제 그 솔루션에 어떻게 도달했는지 파악해야합니다. 직관이 드러나면이 지역 문제를 해결하는 데 사용할 수도 있습니다. 나는 폭격 y과 z공간이 없다는 것을 알았습니다 . 해당 공간을 폭격하는 것이 적합한 코너를 찾으려면 다음과 같은 코너가 생성됩니다.
0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .
이를 위해 최적의 해결책은 y5 번 5 번 폭격하는 것이 분명합니다 z. 한 걸음 더 나아 갑시다.
0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .
여기서 최적의 솔루션은 폭탄 a을 b6 번, 그 다음 x4 번 하는 것이 직관적으로 느껴집니다 .
이제이 직관을 우리가 만들 수있는 원칙으로 바꾸는 방법에 대한 게임이되었습니다.
계속되기를 바랍니다!
업데이트 된 질문의 경우 간단한 탐욕스러운 알고리즘이 최적의 결과를 제공합니다.
A [0,0] 폭탄을 셀 A [1,1]에 떨어 뜨린 다음 A [1,0] 폭탄을 셀 A [2,1]에 떨어 뜨린 다음이 과정을 아래쪽으로 계속 진행하십시오. 왼쪽 하단 모서리를 청소하려면 max (A [N-1,0], A [N-2,0], A [N-3,0]) 폭탄을 셀 A [N-2,1]에 떨어 뜨립니다. 이렇게하면 처음 3 개의 열이 완전히 정리됩니다.
동일한 접근 방식으로 열 3,4,5를 청소 한 다음 열 6,7,8 등을 정리하십시오.
불행히도 이것은 원래 문제에 대한 해결책을 찾는 데 도움이되지 않습니다.
"큰 감소"제약이없는 "큰"문제는 NP-hard 인 것으로 입증 될 수 있습니다. 여기 증거의 스케치가 있습니다.
최대 3 도의 평면 그래프가 있다고 가정 해 봅시다 .이 그래프의 최소 정점 커버 를 찾아 봅시다 . Wikipedia 기사에 따르면이 문제는 최대 3 도의 평면 그래프에서 NP-hard입니다. 이는 Planar 3SAT의 감소에 의해 입증 될 수 있습니다. 그리고 3SAT에서 감소하여 Planar 3SAT의 경도. 이 두 가지 증거는 교수님이 최근 발표 한 "알고리즘 하위 경계" 강의에서 발표되었습니다 . Erik Demaine (강의 7과 9).
원래 그래프의 일부 가장자리 (다이어그램의 왼쪽 그래프)와 짝수의 추가 노드가있는 경우 결과 그래프 (다이어그램의 오른쪽 그래프)는 원래 꼭짓점에 대해 정확히 동일한 최소 정점 커버를 가져야합니다. 이러한 변환을 통해 그래프 정점을 그리드의 임의 위치에 맞출 수 있습니다.
그래프 정점을 한 행과 열에 만 고르게 배치하는 경우 (한 정점에 입사하는 두 모서리가 예각을 형성하지 않는 방식으로) 모서리가있는 곳에 "1"을 삽입하고 다른 그리드 위치에 "0"을 삽입합니다. 최소 정점 표지를 찾기 위해 원래 문제에 대한 솔루션을 사용할 수 있습니다.
이 문제를 정수 프로그래밍 문제 로 나타낼 수 있습니다 . (이것은이 문제에 접근 할 수있는 해결책 중 하나 일뿐입니다)
포인트가있는 경우 :
a b c d
e f g h
i j k l
m n o p
예를 들어 점 f에 대해 보유한 16 개의 방정식을 쓸 수 있습니다.
f <= ai + bi + ci + ei + fi + gi + ii + ji + ki
모든 인덱스와 정수 솔루션의 합계보다 최소화되었습니다.
솔루션은 물론이 인덱스의 합계입니다.
경계 0에서 모든 xi를 설정하면 더욱 단순화 할 수 있으므로이 예제에서는 4 + 1 방정식을 갖게됩니다.
문제는 그러한 문제를 해결하기위한 사소한 알고리즘이 없다는 것입니다. 나는 이것에 대해 전문가가 아니지만 선형 프로그래밍이 NP 어렵 기 때문에이 문제를 해결합니다.
이것은 부분적인 대답입니다. 가능한 폭탄 수일 수있는 하한 및 상한을 찾으려고합니다.
3x3 이하의 보드에서 솔루션은 항상 가장 큰 숫자 셀입니다.
4x4보다 큰 보드에서 첫 번째 명백한 하한은 모서리의 합입니다.
*2* 3 7 *1*
1 5 6 2
2 1 3 2
*6* 9 6 *4*
그러나 폭탄을 배치하면 2 + 1 + 6 + 4 = 13 미만의 폭탄 으로이 4x4 보드를 지울 수 없습니다.
다른 답변에서 코너를 제거하기 위해 두 번째 코너에 폭탄을 배치하는 것이 코너 자체에 폭탄을 배치하는 것보다 결코 나쁘지 않다는 것이 언급되었습니다.
*2* 3 4 7 *1*
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
*6* 9 1 6 *4*
우리는 새로운 보드를 제공하기 위해 두 번째 코너에 폭탄을 배치하여 코너를 제로로 만들 수 있습니다.
0 1 1 6 0
0 3 0 5 1
2 1 1 1 0
2 1 2 4 1
0 0 0 0 0
0 0 0 0 0
0 3 0 2 0
여태까지는 그런대로 잘됐다. 모서리를 비우려면 13 개의 폭탄이 필요합니다.
이제 아래 표시된 6, 4, 3 및 2를 관찰하십시오.
0 1 1 *6* 0
0 3 0 5 1
2 1 1 1 0
*2* 1 2 *4* 1
0 0 0 0 0
0 0 0 0 0
0 *3* 0 2 0
하나의 폭탄을 사용하여 두 개의 세포 를 폭격 할 수있는 방법이 없으므로 최소 폭탄이 6 + 4 + 3 + 2 증가하여 모서리를 지우는 데 사용 된 폭탄 수를 추가하면 최소값을 얻습니다. 이지도에 필요한 폭탄 수는 28 개가되었습니다. 폭탄이 28 개 미만인 경우이지도를 지울 수 없습니다.이지도의 하한입니다.
욕심 많은 알고리즘을 사용하여 상한을 설정할 수 있습니다. 다른 답변에 따르면 탐욕스러운 알고리즘은 28 개의 폭탄을 사용하는 솔루션을 생성합니다. 앞서 우리는 최적의 솔루션이 28 개 미만의 폭탄을 가질 수 없다는 것을 입증 했으므로 28 개의 폭탄이 실제로 최적의 솔루션입니다.
탐욕스럽고 위에서 언급 한 최소 한계를 찾는 방법이 수렴되지 않으면 모든 조합을 확인하는 것으로 되돌아 가야한다고 생각합니다.
하한값을 찾는 알고리즘은 다음과 같습니다.
- 숫자가 가장 높은 요소를 선택하고 이름을 P로 지정하십시오.
- P와 P 자체에서 2 단계 떨어진 모든 셀을 선택 불가능한 것으로 표시합니다.
- P를
minimums목록에 추가 하십시오. - 모든 셀을 선택할 수 없을 때까지 1 단계로 반복하십시오.
minimums하한을 얻으려면 목록을 합산하십시오 .
이것은 욕심 많은 접근 방식입니다.
차수 n X m의 "점수"행렬을 계산합니다. 여기서 점수 [i] [j]는 위치 (i, j)에 폭격이있는 경우 행렬의 점 총합입니다. (점의 최대 점수는 9이고 최소 점수는 0입니다)
행을 현명하게 움직여서 가장 높은 점수를 가진 첫 번째 위치를 찾아서 선택하십시오 (예 : (i, j)).
폭탄 (i, j). 폭탄 수를 늘리십시오.
원래 행렬의 모든 요소가 0이 아닌 경우 1로 이동하십시오.
그래도 이것이 최적의 해결책이라는 의심이 있습니다.
편집하다:
위에서 게시 한 욕심 접근 방식은 작동하지만 최적의 솔루션을 제공하지는 못합니다. 그래서 DP의 일부 요소를 추가해야한다고 생각했습니다.
어느 시점에서든 가장 높은 "점수"(점수 [i] [j] = (i, j)가 폭격 된 경우 총 점수 공제)가있는 위치 중 하나를 타겟팅해야 함)에 동의 할 수 있다고 생각합니다. 이 가정으로 시작하여 다음과 같은 새로운 접근 방식이 있습니다.
NumOfBombs (M) : (필요한 최소 폭격 수를 반환)
차수 n X m의 행렬 M이 주어집니다. M의 모든 요소가 0이면 0을 반환합니다.
"점수"행렬 M을 계산하십시오.
k 개의 개별 위치 P1, P2, ... Pk (1 <= k <= n * m)를 M에서 가장 높은 점수를 가진 위치로 둡니다.
리턴 (1 + min (NumOfBombs (M1), NumOfBombs (M2), ..., NumOfBombs (Mk)))
여기서 M1, M2, ..., Mk는 위치 P1, P2, ..., Pk를 각각 폭격하면 결과 행렬입니다.
또한이 외에도 핵의 위치 순서를 원한다면 "min"의 결과를 추적해야합니다.
귀하의 새로운 문제는 행에 걸쳐 비 감소 값으로 해결하는 것은 매우 쉽다.
왼쪽 열에 가장 큰 숫자가 포함되어 있는지 확인하십시오. 따라서 최적의 솔루션은 먼저이 열을 0으로 줄여야합니다. 따라서이 열에서 1D 폭격을 수행하여 모든 열을 0으로 줄일 수 있습니다. 폭탄을 두 번째 칸에 떨어 뜨려 최대한의 피해를 입 힙니다. 여기에 1D 사례를 다루는 게시물이 많이 있으므로 그 사례를 건너 뛰는 것이 안전하다고 생각합니다. (내가 설명하기를 원하면 할 수 있습니다.). 감소하는 속성으로 인해 가장 왼쪽에있는 세 개의 열이 모두 0으로 줄어 듭니다. 그러나 왼쪽 열을 0으로 설정해야하기 때문에 여기서는 최소 수의 폭탄을 사용할 것입니다.
이제 왼쪽 열이 0이되면 이제 0이 된 가장 왼쪽에있는 3 개의 열을 잘라 내고 이제 축소 된 행렬로 반복합니다. 각 단계마다 최소한의 폭탄을 사용하기 때문에 최적의 솔루션을 제공해야합니다.
문제를 선형 하위 문제로 변환 할 필요가 없습니다.
대신 가장 욕심 많은 휴리스틱을 사용하십시오 . 가장 큰 것부터 시작 하여 모퉁이 를 폭파시키는 것입니다.
주어진 예에는 네 개의 모서리 {2, 1, 6, 4}가 있습니다. 각 구석에 대해 셀 대각선을 모퉁이에 폭파시키는 것보다 더 나은 이동은 없으므로 첫 번째 2 + 1 + 6 + 4 = 13 폭격 이이 대각선 셀에 있어야한다는 것을 알고 있습니다. 폭격을 한 후에 우리는 새로운 매트릭스를 남깁니다.
2 3 4 7 1 0 1 1 6 0 0 1 1 6 0 1 1 6 0 0 0 5 0 0 0
1 5 2 6 2 0 3 0 5 1 0 3 0 5 1 => 1 0 4 0 => 0 0 3 => 0 0 0
4 3 4 2 1 2 1 1 1 0 2 1 1 1 0 0 0 0 0 0 0 0 0 0 3
2 1 2 4 1 => 2 1 2 4 1 => 2 1 2 4 1 0 0 3 0 0 0 3
3 1 3 4 1 0 0 0 0 0 0 0 0 0 0
2 1 4 3 2 0 0 0 0 0 0 0 0 0 0
6 9 1 6 4 0 3 0 2 0 0 0 0 0 0
처음 13 번의 폭탄 공격 후에 휴리스틱을 사용하여 3 번의 폭탄을 통해 3 0 2를 제거했습니다. 이제 4 번째 줄에 2 개의 새로운 코너 {2, 1}가 있습니다. 우리는 또 다른 3 번의 폭탄을 폭파합니다. 이제 행렬을 4 x 4로 줄였습니다. 왼쪽 상단에 하나의 모서리가 있습니다. 우리는 그것을 폭파합니다. 이제 2 개의 모서리가 남았습니다 ({5, 3}). 5가 가장 큰 모퉁이이므로 먼저 5 번의 폭탄을 터트리고 마지막으로 다른 쪽 모퉁이에서 3 번을 폭격하십시오. 합계는 13 + 3 + 3 + 1 + 5 + 3 = 28입니다.
이것은이 "미로"위치를 통해 최단 경로 (일련의 폭격)를 폭 넓게 검색합니다. 아니요, 더 빠른 알고리즘이 없다는 것을 증명할 수 없습니다. 죄송합니다.
#!/usr/bin/env python
M = ((1,2,3,4),
(2,3,4,5),
(5,2,7,4),
(2,3,5,8))
def eachPossibleMove(m):
for y in range(1, len(m)-1):
for x in range(1, len(m[0])-1):
if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
m[y][x-1] == m[y][x] == m[y][x+1] ==
m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
continue
yield x, y
def bomb(m, (mx, my)):
return tuple(tuple(max(0, m[y][x]-1)
if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
else m[y][x]
for x in range(len(m[y])))
for y in range(len(m)))
def findFirstSolution(m, path=[]):
# print path
# print m
if sum(map(sum, m)) == 0: # empty?
return path
for move in eachPossibleMove(m):
return findFirstSolution(bomb(m, move), path + [ move ])
def findShortestSolution(m):
black = {}
nextWhite = { m: [] }
while nextWhite:
white = nextWhite
nextWhite = {}
for position, path in white.iteritems():
for move in eachPossibleMove(position):
nextPosition = bomb(position, move)
nextPath = path + [ move ]
if sum(map(sum, nextPosition)) == 0: # empty?
return nextPath
if nextPosition in black or nextPosition in white:
continue # ignore, found that one before
nextWhite[nextPosition] = nextPath
def main(argv):
if argv[1] == 'first':
print findFirstSolution(M)
elif argv[1] == 'shortest':
print findShortestSolution(M)
else:
raise NotImplementedError(argv[1])
if __name__ == '__main__':
import sys
sys.exit(main(sys.argv))
선형 프로그래밍 접근법이 여기서 매우 도움이 될 것 같습니다.
P m xn을 위치 값을 가진 행렬로 하자 .
이제 정의하도록 (x, y)는 폭탄 행렬 B를 MXN 와 1 ≤ X ≤ m , 1 ≤ Y ≤ N 아래
그런 식으로
예를 들면 다음과 같습니다.
그래서 우리는 행렬 B m xn = [ b ij ]를 찾고 있습니다.
폭탄 매트릭스의 합으로 정의 할 수 있습니다.
( q ij 는 우리가 p ij 위치에 놓을 폭탄 의 수량이 될 것입니다 )
p ij -b ij ≤ 0 (보다 간결하게하기 위해 P-B ≤ 0 이라고하자 )
또한 B 는 합계를 최소화해야합니다 
.
B 를 추악한 행렬로 쓸 수도 있습니다 .
이후 P - B ≤ 0 (수단 P ≤ B를 ) 우리는 거의 일차 부등식 시스템 아래 다음 가지고
된다는 Q의 MN 1 (X) 로 정의
p mn x 1로 정의
우리는 우리가 시스템을 가지고 말할 수있는 행렬 http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D의 제품으로 표현 아래의 시스템 인 S 백만 X mn 시스템을 풀기 위해 역행 할 행렬. 나는 그것을 직접 확장하지는 않았지만 코드에서 쉽게 할 수 있다고 생각합니다.
이제 우리는 다음과 같이 말할 수있는 최소한의 문제가 있습니다
나는 단순한 알고리즘 과 같은 것으로 해결하는 것이 쉽고, 사소한 것이라고 생각합니다 (이에 대한 멋진 문서가 있습니다 ). 그러나 나는 선형 프로그래밍이 거의 없다는 것을 알고 있습니다 (코스 라에서 과정을 수강 할 것이지만 앞으로는 ...), 나는 그것을 이해하려고 두통이 있었고 끝내야 할 큰 프리랜서 직업이 있습니다. 여기서 포기 해 내가 어떤 시점에서 뭔가 잘못했다는 것을 할 수있다, 또는 더 이상 갈 수없는,하지만 난이 경로가 결국 이어질 수 있다고 생각 솔루션입니다. 어쨌든, 나는 당신의 의견을 염려합니다.
( LaTeX 표현으로 그림을 만드는이 놀라운 사이트에 특별한 감사를드립니다 )
이 욕심 많은 해결책 은 올바른 것 같습니다 .
의견에서 지적했듯이 2D에서는 실패합니다. 그러나 아마도 당신은 그것을 향상시킬 수 있습니다.
1D의
경우 : 두 개 이상의 숫자가있는 경우 두 번째 숫자로 촬영하는 것이 나쁘지 않기 때문에 가장 왼쪽 숫자로 촬영할 필요 가 없습니다 . 따라서 두 번째로 촬영하십시오. 첫 번째는 0이 아닙니다. 왜냐하면해야하기 때문입니다. 다음 셀로 이동하십시오. 마지막 셀을 잊지 마십시오.
C ++ 코드 :
void bombs(vector<int>& v, int i, int n){
ans += n;
v[i] -= n;
if(i > 0)
v[i - 1] -= n;
if(i + 1< v.size())
v[i + 1] -= n;
}
void solve(vector<int> v){
int n = v.size();
for(int i = 0; i < n;++i){
if(i != n - 1){
bombs(v, i + 1, v[i]);
}
else
bombs(v, i, v[i])
}
}
따라서 2D의 경우 :
다시 : 첫 번째 행에서 촬영할 필요가 없습니다 (두 번째 행이있는 경우). 두 번째로 촬영하십시오. 첫 번째 행에 대한 1D 작업을 해결하십시오. (널로 만들어야하기 때문에). 내려가 마지막 행을 잊지 마십시오.
분기 및 바운드를 사용한 Mathematica Integer 선형 프로그래밍
이미 언급 했듯이이 문제는 정수 선형 프로그래밍 ( NP-Hard )을 사용하여 해결할 수 있습니다 . Mathematica에는 이미 ILP가 내장되어 있습니다. "To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."[ Mathematica의 제한적 최적화 튜토리얼 참조 .]
Mathematica의 ILP 라이브러리를 활용하는 다음 코드를 작성했습니다. 놀랍게도 빠릅니다.
solveMatrixBombProblem[problem_, r_, c_] :=
Module[{},
bombEffect[x_, y_, m_, n_] :=
Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y ||
j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
bombMatrix[m_, n_] :=
Transpose[
Table[Table[
Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m,
n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0,
m*n - 1}], {i, 0, m*n - 1}]];
X := x /@ Range[c*r];
sol = Minimize[{Total[X],
And @@ Thread[bombMatrix[r, c].X >= problem] &&
And @@ Thread[X >= 0] && Total[X] <= 10^100 &&
Element[X, Integers]}, X];
Print["Minimum required bombs = ", sol[[1]]];
Print["A possible solution = ",
MatrixForm[
Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0,
c - 1}]]];]
문제에서 제공된 예제의 경우 :
solveMatrixBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5]
출력
탐욕스러운 알고리즘으로 이것을 읽는 사람이라면
다음 10x10 문제에 대한 코드를 시도하십시오.
5 20 7 1 9 8 19 16 11 3
17 8 15 17 12 4 5 16 8 18
4 19 12 11 9 7 4 15 14 6
17 20 4 9 19 8 17 2 10 8
3 9 10 13 8 9 12 12 6 18
16 16 2 10 7 12 17 11 4 15
11 1 15 1 5 11 3 12 8 3
7 11 16 19 17 11 20 2 5 19
5 18 2 17 7 14 19 11 1 6
13 20 8 4 15 10 19 5 11 12
쉼표로 구분되어 있습니다.
5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12
이 문제를 해결하기 위해 내 솔루션에는 208 개의 폭탄이 포함되어 있습니다 . 가능한 해결책이 있습니다 (약 12 초 안에 해결할 수있었습니다).
Mathematica가 생산하는 결과를 테스트하는 방법으로 욕심 많은 알고리즘이 더 잘할 수 있는지 확인하십시오.
폭탄의 수를 최소화하려면 모든 폭탄의 효과를 극대화해야합니다. 이를 달성하기 위해 모든 단계에서 가장 좋은 목표를 선택해야합니다. 각 포인트를 합산하면 8 개의 이웃이 있습니다.이 지점을 폭파하는 효율 양으로 사용할 수 있습니다. 이것은 최적의 폭탄 순서에 가깝습니다.
UPD : 우리는 또한 비제로 폭격하기 때문에 0을 고려해야합니다. 실제로 문제는 적중 된 0의 수를 최소화하는 것입니다. 그러나 우리는 어떤 단계가 우리를이 목표에 더 가깝게하는지 알 수 없습니다. 문제가 NP- 완전하다는 생각에 동의합니다. 나는 욕심 많은 접근 방식을 제안합니다. 실제에 가까운 대답을 줄 것입니다.
나는 폭탄의 양을 최소화하기 위해 단순히 손상의 양을 극대화해야한다고 생각합니다. 그 일이 발생하기 위해서는 가장 강한 힘을 가진 지역을 확인해야합니다. 그래서 먼저 3x3 커널로 필드를 분석하고 합계가 어디 있는지 확인하십시오 더 강력하고 .. 그리고 폭탄이 .. 그리고 들판이 평평해질 때까지하세요.
var oMatrix = [
[2,3,4,7,1],
[1,5,2,6,2],
[4,3,4,2,1],
[2,1,2,4,1],
[3,1,3,4,1],
[2,1,4,3,2],
[6,9,1,6,4]
]
var nBombs = 0;
do
{
var bSpacesLeftToBomb = false;
var nHigh = 0;
var nCellX = 0;
var nCellY = 0;
for(var y = 1 ; y<oMatrix.length-1;y++)
for(var x = 1 ; x<oMatrix[y].length-1;x++)
{
var nValue = 0;
for(var yy = y-1;yy<=y+1;yy++)
for(var xx = x-1;xx<=x+1;xx++)
nValue += oMatrix[yy][xx];
if(nValue>nHigh)
{
nHigh = nValue;
nCellX = x;
nCellY = y;
}
}
if(nHigh>0)
{
nBombs++;
for(var yy = nCellY-1;yy<=nCellY+1;yy++)
{
for(var xx = nCellX-1;xx<=nCellX+1;xx++)
{
if(oMatrix[yy][xx]<=0)
continue;
oMatrix[yy][xx] = --oMatrix[yy][xx];
}
}
bSpacesLeftToBomb = true;
}
}
while(bSpacesLeftToBomb);
alert(nBombs+'bombs');
다음은 모서리의 좋은 특성을 일반화하는 솔루션입니다.
주어진 필드에 대한 완벽한 드롭 포인트, 즉 필드의 값을 줄이는 가장 좋은 방법을 찾을 수 있다고 가정 해 봅시다. 그런 다음 드롭 할 최소 폭탄 수를 찾기 위해 알고리즘의 첫 번째 초안이 될 수 있습니다 (루비 구현에서 코드를 복사하여 붙여 넣습니다).
dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
coordinates = choose_a_perfect_drop_point
drop_bomb(coordinates)
dropped_bomb_count += 1
end
return dropped_bomb_count
도전은 choose_a_perfect_drop_point입니다. 먼저 완벽한 드롭 포인트를 정의 해 봅시다.
- 에 대한 드롭 포인트 는
(x, y)의 값 을 줄입니다(x, y). 다른 셀의 값도 감소 할 수 있습니다. - 낙하 지점 A를 위한
(x, y)것이다 더 저하 점보다 B 용(x, y)은 그 셀의 적절한 상위의 값을 감소하면 B가 감소한다. - 더 나은 드롭 포인트가 없으면 드롭 포인트가 최대가 됩니다.
- 동일한 셀 세트를 줄이면 두 개의 드롭 포인트
(x, y)가 동일 합니다. - 에 대한 모든 최대 드롭 포인트와 동등한 경우에 대한 드롭 포인트
(x, y)가 완벽 합니다(x, y).
에 대한 완벽한 드롭 포인트가 있으면에 대한 완벽한 드롭 포인트 중 하나에 폭탄을 드롭하는 것보다 더 효과적으로 (x, y)값을 줄일 수 없습니다 .(x, y)(x, y)
주어진 필드에 대한 완벽한 드롭 포인트는 모든 셀에 대한 완벽한 드롭 포인트입니다.
몇 가지 예는 다음과 같습니다.
1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
셀에 대한 완벽한 드롭 포인트 (0, 0)(0부터 시작하는 인덱스)는 (1, 1)입니다. 모든 다른 드롭 포인트 (1, 1)입니다, (0, 0), (0, 1), 그리고 (1, 0), 적은 세포를 감소시킨다.
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
셀에 대한 완벽한 낙하 점 (2, 2)(제로 지수)이고 (2, 2), 또한 전체 주변 세포 (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), 및 (3, 3).
0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
세포에 대한 완전한 낙하 점 (2, 2)이다 (3, 1): 그것의 값이 감소 (2, 2)하고있는 값 (4, 0). 다른 모든 드롭 포인트 (2, 2)는 하나의 셀을 줄이므로 최대가 아닙니다. 에 대한 완벽한 드롭 포인트 (2, 2)는에 대한 완벽한 드롭 포인트이며 (4, 0)필드에 대한 유일한 완벽한 드롭 포인트입니다. 이 분야에 대한 완벽한 솔루션으로 이어집니다 (한 번의 폭탄 투하).
1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
1 0 0 0 0
완벽한 드롭 포인트는 없습니다 (2, 2): (1, 1)및 (1, 3)감소 (2, 2)및 다른 셀 (모두 최대 드롭 포인트 (2, 2))이지만 동등하지 않습니다. 그러나에 (1, 1)대한 완벽한 드롭 포인트 (0, 0)이며 (1, 3)에 대한 완벽한 드롭 포인트입니다 (0, 4).
완벽한 드롭 포인트와 특정 검사 순서에 대한 정의를 통해 문제의 예에 대해 다음과 같은 결과를 얻습니다.
Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28
그러나 알고리즘은 각 단계 후에 하나 이상의 완벽한 드롭 포인트가있는 경우에만 작동합니다. 완벽한 드롭 포인트가없는 예제를 구성 할 수 있습니다.
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
이 경우 완벽한 드롭 포인트 대신 최소 드롭 포인트를 선택하여 좌표를 선택한 다음 각 선택에 대한 최소값을 계산하도록 알고리즘을 수정할 수 있습니다. 위의 경우 값이있는 모든 셀에는 최대 두 개의 드롭 포인트가 있습니다. 예를 들어, (0, 1)최대 드롭 지점이 (1, 1)와 (1, 2). 하나를 선택한 다음 최소값을 계산하면 다음과 같은 결과가 발생합니다.
Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2
다른 아이디어가 있습니다.
폭탄을 떨어 뜨려 몇 개의 숫자를 줄일 수 있는지 보드의 각 공간에 가중치를 부여하는 것으로 시작하겠습니다. 따라서 공간에 0이 아닌 숫자가 있으면 포인트를 얻습니다. 인접한 공간에 0이 아닌 숫자가 있으면 추가 포인트를 얻습니다. 따라서 1000 x 1000 격자가있는 경우 각 백만 개의 공간에 가중치가 할당됩니다.
그런 다음 공간 목록을 무게별로 정렬하고 가장 큰 무게를 가진 공간을 폭격하십시오. 이것은 우리의 돈에 가장 큰 영향을 미치고 있습니다.
그런 다음 폭탄의 무게가 영향을받는 모든 공간의 무게를 업데이트하십시오. 이것은 당신이 폭격 한 공간과 바로 인접 해있는 공간이 될 것입니다. 다시 말해 폭격으로 인해 그 값이 0으로 줄어든 공간이나 인접한 공간의 값이 0으로 줄어든 공간이 있다는 것입니다.
그런 다음 목록 공간을 가중치별로 다시 정렬하십시오. 폭파로 인해 공간의 작은 부분 집합 만 무게가 바뀌 었으므로 전체 목록을 사용하지 않아도됩니다.
새로운 최고 중량 공간을 폭파하고 절차를 반복하십시오.
이것은 모든 폭격이 가능한 한 많은 공간을 줄 이도록 보장합니다 (기본적으로 가능한 한 적은 공간에 충돌합니다). 따라서 무게가 가중 될 수 있다는 점을 제외하면 최적입니다. 따라서 최고 무게에 대한 타이가있을 때 역 추적을해야 할 수도 있습니다. 그러나 가장 큰 무게의 넥타이 만 중요하지만 다른 관계는 중요하지 않으므로 역 추적이 그리 크지 않기를 바랍니다.
편집 : 아래의 Mysticial의 반례는 실제로 무게와의 관계에 관계없이 이것이 최적이라고 보장하지는 않습니다. 어떤 경우에는 주어진 단계에서 가능한 한 많은 무게를 줄이면 실제로 나머지 폭탄이 너무 퍼져 두 번째 단계 후에 누적 감소를 달성 할 수 있으므로 첫 번째 단계에서 약간 덜 욕심스러운 선택을 할 수 있습니다. 나는 결과가 폭탄의 순서에 둔감하다는 생각에 다소 오도되었다. 그들은 이다일련의 폭격을 시작부터 다른 순서로 시작하여 동일한 결과 보드로 끝날 수 있다는 점에서 순서에 둔감합니다. 그러나 각 폭격을 독립적으로 고려할 수 있다는 것은 아닙니다. 또는 적어도 각 폭격은 후속 폭격에 대한 보드 구성 정도를 고려하여 고려해야합니다.
글쎄, 보드 위치 1, 2, ..., nx m의 번호를 정한다고 가정 해보십시오. 일련의 폭탄 방울은이 세트에서 일련의 숫자로 표시 될 수 있으며, 여기서 숫자는 반복 될 수 있습니다. 그러나 보드에 미치는 영향은 폭탄을 떨어 뜨린 순서와 상관없이 동일하므로 실제로 폭탄 드롭의 선택은 nxm 숫자 목록으로 표시 될 수 있습니다. 첫 번째 숫자는 위치 1에서 떨어진 폭탄 수를 나타냅니다. 두 번째 숫자는 위치 2 등에서 떨어진 폭탄의 수를 나타냅니다.이 nxm 숫자 목록을 "키"라고하겠습니다.
먼저 폭탄을 떨어 뜨린 결과로 발생하는 모든 보드 상태를 계산 한 다음 0을 얻을 때까지 폭탄을 떨어 뜨린 결과로 발생하는 모든 보드 상태를 계산할 수 있습니다. 그러나 각 단계에서 위에서 정의한 키를 사용하여 상태를 캐시하므로이 결과를 사용하여 다음 단계 ( "동적 프로그래밍"접근 방식)를 계산할 수 있습니다.
그러나 n, m의 크기 및 그리드의 숫자에 따라이 방법의 메모리 요구 사항이 과도 할 수 있습니다. N + 1에 대한 모든 결과를 계산하면 N 폭탄 방울에 대한 모든 결과를 버릴 수 있으므로 절약 할 수 있습니다. 물론 당신은 가지고있는의 비용 캐시 아무것도 할 수 없었다 많은 동적 프로그래밍 접근 방식은 속도를 위해 메모리를 거래 - 더 이상은.
보드를 청소하기 위해 절대 최적의 솔루션을 원한다면 고전적인 역 추적을 사용해야하지만 매트릭스가 매우 큰 경우 최상의 솔루션을 찾는 데 오랜 시간이 걸릴 것입니다. "가능한"최적의 솔루션을 원한다면 탐욕스러운 알고리즘을 사용할 수 있습니다 알고리즘 작성에 도움이 필요한 경우 도움을 드릴 수 있습니다.
그것이 가장 좋은 방법이라고 생각하십시오. 폭탄을 떨어 뜨려 제거한 포인트를 저장 한 다른 행렬을 만든 다음 최대 포인트를 가진 셀을 선택하고 폭탄을 떨어 뜨려 포인트 매트릭스를 업데이트하고 계속합니다. 예:
2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))
0보다 큰 값을 가진 모든 인접한 셀에 대한 셀 값 +1
무차별 대입!
나는 그것이 효율적이지 않다는 것을 알고 있지만, 더 빠른 알고리즘을 찾더라도 항상이 결과를 테스트하여 얼마나 정확한지 알 수 있습니다.
다음과 같이 재귀를 사용하십시오.
void fn(tableState ts, currentlevel cl)
{
// first check if ts is all zeros yet, if not:
//
// do a for loop to go through all cells of ts,
// for each cell do a bomb, and then
// call:
// fn(ts, cl + 1);
}
캐싱을 통해이를보다 효율적으로 만들 수 있습니다. 다른 방법으로 동일한 결과가 나오면 동일한 단계를 반복해서는 안됩니다.
정교하게 :
폭격 셀 1,3,5가 폭격 셀 5,3,1과 동일한 결과를 초래하는 경우, 두 경우 모두 다음 단계를 모두 다시 수행하지 말고 1만으로 충분합니다. 테이블 상태와 결과를 사용합니다.
테이블 통계 해시를 사용하여 빠른 비교를 수행 할 수 있습니다.
- 국경을 폭파하지 마십시오 (사각형에 국경이없는 이웃이 아닌 한)
- 제로 코너.
- 모서리를 0으로하려면 모서리의 값을 1 사각형 떨어진 대각선으로 떨어 뜨립니다 (국경이 아닌 유일한 이웃)
- 새로운 코너가 생깁니다. 2로 이동
편집 : Kostek이 거의 동일한 접근 방식을 제안한다는 사실을 알지 못했기 때문에 이제 더 강력하게 주장합니다. 지우기 모서리가 항상 가장 바깥층에 있도록 선택하면 최적입니다.
OP의 예에서 : 5가 아닌 다른 것에 2 (1 + 1 또는 2로)를 떨어 뜨려도 5에 떨어질 때 어떤 사각형도 치지 않습니다. 그래서 우리는 단순히 5에서 2를 떨어 뜨려야합니다 (그리고 왼쪽 아래 1에서 6을 떨어 뜨립니다 ...)
그 후, 원본 1 (현재 0)을 (왼쪽 상단) 모서리를 지우는 방법은 한 가지뿐입니다. 즉 B3에 0을 떨어 뜨립니다 (표기법과 유사). 등등.
전체 A 및 E 열과 1 및 7 행을 지운 후에 만 한 층 더 깊게 지울 수 있습니다.
의도적으로 지워진 값만 지우고 0 값 코너를 지우면 비용이 들지 않으며 그것에 대한 생각을 단순화합니다.
이 방법으로 떨어 뜨린 모든 폭탄을 떨어 뜨려야하며 이로 인해 들판이 비워 지므로 최적의 솔루션입니다.
수면 후 나는 이것이 사실이 아님을 깨달았다. 치다
ABCDE
1 01000
2 10000
3 00000
4 00000
B2를 떨어 뜨리는 것만으로도 B3와 C2에 폭탄을 떨어 뜨릴 수 있습니다.
여기 내 해결책이 있습니다. 시간이 없기 때문에 아직 코드로 작성하지는 않지만 매번 최적의 움직임을 생성해야한다고 생각합니다.하지만 얼마나 효율적으로 찾을 수 있을지는 모르겠습니다. 폭탄의 요점.
첫째, @Luka Rahne이 의견 중 하나에서 언급했듯이 폭탄의 순서는 중요하지 않으며 조합 만 중요합니다.
둘째, 다른 많은 사람들이 말했듯이 모서리에서 대각선에서 1-1의 폭탄을 폭파하는 것이 모서리보다 많은 점에 닿기 때문에 최적입니다.
이것은 내 버전의 알고리즘에 대한 기초를 생성합니다 : 우리는 '모퉁이에서 1 번 끄기'를 처음으로 또는 마지막으로 폭격 할 수 있습니다. (이론상) 중요하지 않습니다 (이론적으로) 우리는 나중에 결정하기 쉽기 때문에 먼저 폭격합니다 우리는 가장 많은 포인트에 영향을 미치는 포인트를 폭격하면서 동시에 그 코너를 폭격합니다.
저항 점이 Points of Resistance 를 보드의 가장 폭이 넓은 지점 + 주위 에 0이 가장 많은 지점으로 정의합시다
폭격 불가 지점 은 현재 보고있는 보드 범위 에 존재하지 않는 지점으로 정의 할 수 있습니다 .
또한 범위를 처리 할 범위를 Top = 0, Left = 0, Bottom = k, right = j로 정의합니다. (시작할 값)
마지막으로, 최적의 폭탄 을 저항 점에 인접한 지점에 떨어 뜨리고 (1) 가장 높은 저항 지점과 (2) 가능한 많은 지점에 닿는 폭탄 으로 정의하겠습니다 .
접근 방식에 대해서는 외부에서 작업하는 것이 분명합니다. 동시에 4 개의 '폭격기'와 함께 작업 할 수 있습니다.
저항의 첫 번째 지점은 분명히 우리의 모퉁이입니다. '경계를 벗어난'지점은 폭탄을 사용할 수 없습니다 (각 코너의 범위를 벗어난 5 점). 그래서 우리는 먼저 모서리에서 대각선으로 점을 폭파합니다.
연산:
- 최적의 폭탄 포인트 4 개를 찾으십시오.
- 폭탄 지점이 2 범위 (즉, 모서리)에 닿는 저항 지점을 폭격하는 경우 해당 지점까지의 폭탄은 0입니다. 그렇지 않으면 최적의 폭탄 지점에 닿는 저항 지점 중 하나가 0이 될 때까지 각각 폭탄을 격발하십시오.
- 각 바운드에 대해 : if (sum (bound) == 0) advance bound
TOP = BOTTOM 및 LEFT = RIGHT까지 반복
나중에 실제 코드를 작성하려고합니다
주 공간 계획을 사용할 수 있습니다. 예를 들어, A * (또는 그 변형 중 하나)를 휴리스틱 f = g + h과 함께 다음과 같이 사용합니다.
- g : 폭탄의 수는 지금까지 떨어졌다
- h : 그리드의 모든 값을 9로 나눈 값의 합 (최상의 결과, 허용 가능한 휴리스틱이 있음)
나도 28 개의 움직임을 얻었다. 다음으로 가장 좋은 다음 이동을 위해 두 가지 테스트를 사용했습니다. 먼저 이동은 보드의 최소 합계를 생성합니다. 둘째, 같은 합에 대해 최대 밀도를 생성하는 움직임은 다음과 같이 정의됩니다.
number-of-zeros / number-of-groups-of-zeros
하스켈입니다. "솔브 보드"는 엔진의 솔루션을 보여줍니다. "main"을 입력하여 게임을 한 다음 권장 사항에 대해 "best"또는 "quit"를 입력하거나 종료하려면 "point"를 입력하십시오.
출력 :
* 주> 해결 보드
[(4,4), (3,6), (3,3), (2,2), (2,2), (4,6), (4,6), (2,6), (3,2), (4,2), (2,6), (3,3), (4,3), (2,6), (4,2), (4 , 6), (4,6), (3,6), (2,6), (2,6), (2,4), (2,4), (2,6), (3,6 ), (4,2), (4,2), (4,2), (4,2)]
import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)
board = [2,3,4,7,1,
1,5,2,6,2,
4,3,4,2,1,
2,1,2,4,1,
3,1,3,4,1,
2,1,4,3,2,
6,9,1,6,4]
n = 5
m = 7
updateBoard board pt =
let x = fst pt
y = snd pt
precedingLines = replicate ((y-2) * n) 0
bomb = concat $ replicate (if y == 1
then 2
else min 3 (m+2-y)) (replicate (x-2) 0
++ (if x == 1
then [1,1]
else replicate (min 3 (n+2-x)) 1)
++ replicate (n-(x+1)) 0)
in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)
showBoard board =
let top = " " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n"
chunks = chunksOf n board
in putStrLn (top ++ showBoard' chunks "" 1)
where showBoard' [] str count = str
showBoard' (x:xs) str count =
showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)
instances _ [] = 0
instances x (y:ys)
| x == y = 1 + instances x ys
| otherwise = instances x ys
density a =
let numZeros = instances 0 a
groupsOfZeros = filter (\x -> head x == 0) (group a)
in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)
boardDensity board = sum (map density (chunksOf n board))
moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]
bestMove board =
let lowestSumMoves = take 1 $ groupBy ((==) `on` snd)
$ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves))
in if null lowestSumMoves
then (0,0)
else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves)
in fst $ head $ reverse $ sortBy (comparing snd)
(map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves'))
solve board = solve' board [] where
solve' board result
| sum board == 0 = result
| otherwise =
let best = bestMove board
in solve' (updateBoard board best) (result ++ [best])
main :: IO ()
main = mainLoop board where
mainLoop board = do
putStrLn ""
showBoard board
putStr "Pt: "
a <- getLine
case a of
"quit" -> do putStrLn ""
return ()
"best" -> do putStrLn (show $ bestMove board)
mainLoop board
otherwise -> let ws = splitOn "," a
pt = (read (head ws), read (last ws))
in do mainLoop (updateBoard board pt)
여기에는 이분자가 아닌 일치 하위 구조가있는 것 같습니다. 다음 인스턴스를 고려하십시오.
0010000
1000100
0000001
1000000
0000001
1000100
0010000
이 경우에 대한 최적의 솔루션은 크기가 5이므로 가장자리가 9주기 정점의 최소 커버 크기입니다.
이 사례는 특히 소수의 사람들이 게시 한 선형 프로그래밍 완화가 정확하지 않고 작동하지 않으며 다른 모든 나쁜 것들을 보여줍니다. 나는 당신의 문제에 대해 "평면 입방 그래프의 꼭짓점을 가능한 한 적은 수의 가장자리로 덮을 수 있습니다"라고 확신 할 수 있다고 확신합니다. 그러면 탐욕 / 언덕 등반 솔루션이 작동하는지 의심 스럽습니다.
최악의 경우 다항식 시간으로 이것을 해결할 수있는 방법을 찾지 못했습니다. 내가 보지 못한 매우 영리한 이진 검색 및 DP 솔루션이있을 수 있습니다.
편집 : 대회 ( http://deadline24.pl )는 언어에 구애받지 않습니다. 그들은 당신에게 많은 입력 파일을 보내고 당신은 그들에게 출력을 보냅니다. 따라서 최악의 다항식 시간에 실행되는 것은 필요하지 않습니다. 특히, 당신 은 입력 을 볼 수 있습니다 !
입력에 작은 사례가 많이 있습니다. 그런 다음 10x1000 케이스, 100x100 케이스 및 1000x1000 케이스가 있습니다. 세 가지 큰 경우는 모두 매우 잘 작동합니다. 가로로 인접한 항목은 일반적으로 동일한 값을 갖습니다. 비교적 견고한 컴퓨터에서는 CPLEX를 사용하여 몇 분만에 무차별 강제 실행하여 모든 사례를 해결할 수 있습니다. 나는 1000x1000에 운이 좋았다. LP 이완은 통합 된 최적의 솔루션을 갖습니다. 내 솔루션 .ans은 테스트 데이터 번들에 제공된 파일에 동의 합니다.
입력 구조를 살펴보면 내가하는 것보다 훨씬 더 직접적인 방식으로 입력 구조를 사용할 수 있습니다. 아무것도 남지 않을 때까지 첫 번째 행 또는 두 세 번을 반복적으로 제거 할 수있는 것처럼 보입니다. (1000x1000에서 모든 행이 증가하지 않는 것처럼 보입니다. "파트 B"의 출처는 어디입니까?)
최고의 휴리스틱을 사용하여 폭격 캠페인을 계산하지 않고 실제 수를 계산하는 방법을 생각할 수 없으며 합리적인 결과를 얻길 바랍니다.
그래서 내 방법은 각 셀에 대한 폭격 효율 메트릭을 계산하고, 가장 높은 값으로 셀을 폭격하는 것입니다. .... 모든 것을 병합 할 때까지 프로세스를 반복하십시오. 일부는 단순한 잠재적 피해 (즉, 0에서 9까지의 점수)를 지표로 사용하도록 옹호했지만, 고가의 셀을 두드리고 피해 겹침을 사용하지 않으면 부족합니다. 나는 계산 cell value - sum of all neighbouring cells하고 양수를 0으로 재설정하고 음수의 절대 값을 사용합니다. 직관적으로이 측정 항목은 셀을 직접 두드리지 않고 셀 수가 많은 셀의 손상 겹침을 최대화하도록 선택해야합니다.
아래 코드는 28 폭탄에서 테스트 필드의 총 파괴에 도달합니다 (메트릭으로 잠재적 손상을 사용하면 31이 생성됩니다!).
using System;
using System.Collections.Generic;
using System.Linq;
namespace StackOverflow
{
internal class Program
{
// store the battle field as flat array + dimensions
private static int _width = 5;
private static int _length = 7;
private static int[] _field = new int[] {
2, 3, 4, 7, 1,
1, 5, 2, 6, 2,
4, 3, 4, 2, 1,
2, 1, 2, 4, 1,
3, 1, 3, 4, 1,
2, 1, 4, 3, 2,
6, 9, 1, 6, 4
};
// this will store the devastation metric
private static int[] _metric;
// do the work
private static void Main(string[] args)
{
int count = 0;
while (_field.Sum() > 0)
{
Console.Out.WriteLine("Round {0}:", ++count);
GetBlastPotential();
int cell_to_bomb = FindBestBombingSite();
PrintField(cell_to_bomb);
Bomb(cell_to_bomb);
}
Console.Out.WriteLine("Done in {0} rounds", count);
}
// convert 2D position to 1D index
private static int Get1DCoord(int x, int y)
{
if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
else
{
return (y * _width) + x;
}
}
// Convert 1D index to 2D position
private static void Get2DCoord(int n, out int x, out int y)
{
if ((n < 0) || (n >= _field.Length))
{
x = -1;
y = -1;
}
else
{
x = n % _width;
y = n / _width;
}
}
// Compute a list of 1D indices for a cell neighbours
private static List<int> GetNeighbours(int cell)
{
List<int> neighbours = new List<int>();
int x, y;
Get2DCoord(cell, out x, out y);
if ((x >= 0) && (y >= 0))
{
List<int> tmp = new List<int>();
tmp.Add(Get1DCoord(x - 1, y - 1));
tmp.Add(Get1DCoord(x - 1, y));
tmp.Add(Get1DCoord(x - 1, y + 1));
tmp.Add(Get1DCoord(x, y - 1));
tmp.Add(Get1DCoord(x, y + 1));
tmp.Add(Get1DCoord(x + 1, y - 1));
tmp.Add(Get1DCoord(x + 1, y));
tmp.Add(Get1DCoord(x + 1, y + 1));
// eliminate invalid coords - i.e. stuff past the edges
foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
}
return neighbours;
}
// Compute the devastation metric for each cell
// Represent the Value of the cell minus the sum of all its neighbours
private static void GetBlastPotential()
{
_metric = new int[_field.Length];
for (int i = 0; i < _field.Length; i++)
{
_metric[i] = _field[i];
List<int> neighbours = GetNeighbours(i);
if (neighbours != null)
{
foreach (int j in neighbours) _metric[i] -= _field[j];
}
}
for (int i = 0; i < _metric.Length; i++)
{
_metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
}
}
//// Compute the simple expected damage a bomb would score
//private static void GetBlastPotential()
//{
// _metric = new int[_field.Length];
// for (int i = 0; i < _field.Length; i++)
// {
// _metric[i] = (_field[i] > 0) ? 1 : 0;
// List<int> neighbours = GetNeighbours(i);
// if (neighbours != null)
// {
// foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
// }
// }
//}
// Update the battle field upon dropping a bomb
private static void Bomb(int cell)
{
List<int> neighbours = GetNeighbours(cell);
foreach (int i in neighbours)
{
if (_field[i] > 0) _field[i]--;
}
}
// Find the best bombing site - just return index of local maxima
private static int FindBestBombingSite()
{
int max_idx = 0;
int max_val = int.MinValue;
for (int i = 0; i < _metric.Length; i++)
{
if (_metric[i] > max_val)
{
max_val = _metric[i];
max_idx = i;
}
}
return max_idx;
}
// Display the battle field on the console
private static void PrintField(int cell)
{
for (int x = 0; x < _width; x++)
{
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
}
Console.Out.Write(" || ");
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
}
Console.Out.WriteLine();
}
Console.Out.WriteLine();
}
}
}
결과 폭탄 패턴은 다음과 같이 출력됩니다 (왼쪽 필드 값, 오른쪽 메트릭)
Round 1:
2 1 4 2 3 2 6 || 7 16 8 10 4 18 6
3 5 3 1 1 1 9 || 11 18 18 21 17 28 5
4 [2] 4 2 3 4 1 || 19 [32] 21 20 17 24 22
7 6 2 4 4 3 6 || 8 17 20 14 16 22 8
1 2 1 1 1 2 4 || 14 15 14 11 13 16 7
Round 2:
2 1 4 2 3 2 6 || 5 13 6 9 4 18 6
2 4 2 1 1 [1] 9 || 10 15 17 19 17 [28] 5
3 2 3 2 3 4 1 || 16 24 18 17 17 24 22
6 5 1 4 4 3 6 || 7 14 19 12 16 22 8
1 2 1 1 1 2 4 || 12 12 12 10 13 16 7
Round 3:
2 1 4 2 2 1 5 || 5 13 6 7 3 15 5
2 4 2 1 0 1 8 || 10 15 17 16 14 20 2
3 [2] 3 2 2 3 0 || 16 [24] 18 15 16 21 21
6 5 1 4 4 3 6 || 7 14 19 11 14 19 6
1 2 1 1 1 2 4 || 12 12 12 10 13 16 7
Round 4:
2 1 4 2 2 1 5 || 3 10 4 6 3 15 5
1 3 1 1 0 1 8 || 9 12 16 14 14 20 2
2 2 2 2 2 [3] 0 || 13 16 15 12 16 [21] 21
5 4 0 4 4 3 6 || 6 11 18 9 14 19 6
1 2 1 1 1 2 4 || 10 9 10 9 13 16 7
Round 5:
2 1 4 2 2 1 5 || 3 10 4 6 2 13 3
1 3 1 1 0 [0] 7 || 9 12 16 13 12 [19] 2
2 2 2 2 1 3 0 || 13 16 15 10 14 15 17
5 4 0 4 3 2 5 || 6 11 18 7 13 17 6
1 2 1 1 1 2 4 || 10 9 10 8 11 13 5
Round 6:
2 1 4 2 1 0 4 || 3 10 4 5 2 11 2
1 3 1 1 0 0 6 || 9 12 16 11 8 13 0
2 2 2 2 0 2 0 || 13 16 15 9 14 14 15
5 4 [0] 4 3 2 5 || 6 11 [18] 6 11 15 5
1 2 1 1 1 2 4 || 10 9 10 8 11 13 5
Round 7:
2 1 4 2 1 0 4 || 3 10 4 5 2 11 2
1 3 1 1 0 0 6 || 8 10 13 9 7 13 0
2 [1] 1 1 0 2 0 || 11 [15] 12 8 12 14 15
5 3 0 3 3 2 5 || 3 8 10 3 8 15 5
1 1 0 0 1 2 4 || 8 8 7 7 9 13 5
Round 8:
2 1 4 2 1 0 4 || 1 7 2 4 2 11 2
0 2 0 1 0 0 6 || 7 7 12 7 7 13 0
1 1 0 1 0 2 0 || 8 8 10 6 12 14 15
4 2 0 3 3 [2] 5 || 2 6 8 2 8 [15] 5
1 1 0 0 1 2 4 || 6 6 6 7 9 13 5
Round 9:
2 1 4 2 1 0 4 || 1 7 2 4 2 11 2
0 2 0 1 0 0 6 || 7 7 12 7 6 12 0
1 1 0 1 0 [1] 0 || 8 8 10 5 10 [13] 13
4 2 0 3 2 2 4 || 2 6 8 0 6 9 3
1 1 0 0 0 1 3 || 6 6 6 5 8 10 4
Round 10:
2 1 4 2 1 0 4 || 1 7 2 4 2 10 1
0 2 [0] 1 0 0 5 || 7 7 [12] 7 6 11 0
1 1 0 1 0 1 0 || 8 8 10 4 8 9 10
4 2 0 3 1 1 3 || 2 6 8 0 6 8 3
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 11:
2 0 3 1 1 0 4 || 0 6 0 3 0 10 1
0 1 0 0 0 [0] 5 || 4 5 5 5 3 [11] 0
1 0 0 0 0 1 0 || 6 8 6 4 6 9 10
4 2 0 3 1 1 3 || 1 5 6 0 5 8 3
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 12:
2 0 3 1 0 0 3 || 0 6 0 2 1 7 1
0 1 0 0 0 0 4 || 4 5 5 4 1 7 0
1 0 0 0 0 [0] 0 || 6 8 6 4 5 [9] 8
4 2 0 3 1 1 3 || 1 5 6 0 4 7 2
1 1 0 0 0 1 3 || 6 6 6 4 6 7 2
Round 13:
2 0 3 1 0 0 3 || 0 6 0 2 1 6 0
0 1 0 0 0 0 3 || 4 5 5 4 1 6 0
1 [0] 0 0 0 0 0 || 6 [8] 6 3 3 5 5
4 2 0 3 0 0 2 || 1 5 6 0 4 6 2
1 1 0 0 0 1 3 || 6 6 6 3 4 4 0
Round 14:
2 0 3 1 0 [0] 3 || 0 5 0 2 1 [6] 0
0 0 0 0 0 0 3 || 2 5 4 4 1 6 0
0 0 0 0 0 0 0 || 4 4 4 3 3 5 5
3 1 0 3 0 0 2 || 0 4 5 0 4 6 2
1 1 0 0 0 1 3 || 4 4 5 3 4 4 0
Round 15:
2 0 3 1 0 0 2 || 0 5 0 2 1 4 0
0 0 0 0 0 0 2 || 2 5 4 4 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 4 4
3 1 0 3 0 [0] 2 || 0 4 5 0 4 [6] 2
1 1 0 0 0 1 3 || 4 4 5 3 4 4 0
Round 16:
2 [0] 3 1 0 0 2 || 0 [5] 0 2 1 4 0
0 0 0 0 0 0 2 || 2 5 4 4 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 3 3
3 1 0 3 0 0 1 || 0 4 5 0 3 3 1
1 1 0 0 0 0 2 || 4 4 5 3 3 3 0
Round 17:
1 0 2 1 0 0 2 || 0 3 0 1 1 4 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 4 4 4 3 3 3 3
3 1 [0] 3 0 0 1 || 0 4 [5] 0 3 3 1
1 1 0 0 0 0 2 || 4 4 5 3 3 3 0
Round 18:
1 0 2 1 0 0 2 || 0 3 0 1 1 4 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 3 3 2 2 2 3 3
3 [0] 0 2 0 0 1 || 0 [4] 2 0 2 3 1
1 0 0 0 0 0 2 || 2 4 2 2 2 3 0
Round 19:
1 0 2 1 0 [0] 2 || 0 3 0 1 1 [4] 0
0 0 0 0 0 0 2 || 1 3 3 3 1 4 0
0 0 0 0 0 0 0 || 2 2 2 2 2 3 3
2 0 0 2 0 0 1 || 0 2 2 0 2 3 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 20:
1 [0] 2 1 0 0 1 || 0 [3] 0 1 1 2 0
0 0 0 0 0 0 1 || 1 3 3 3 1 2 0
0 0 0 0 0 0 0 || 2 2 2 2 2 2 2
2 0 0 2 0 0 1 || 0 2 2 0 2 3 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 21:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 0 0 0 0 1 || 0 1 2 2 1 2 0
0 0 0 0 0 0 0 || 2 2 2 2 2 2 2
2 0 0 2 0 [0] 1 || 0 2 2 0 2 [3] 1
0 0 0 0 0 0 2 || 2 2 2 2 2 3 0
Round 22:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 0 0 0 0 1 || 0 1 2 2 1 2 0
[0] 0 0 0 0 0 0 || [2] 2 2 2 2 1 1
2 0 0 2 0 0 0 || 0 2 2 0 2 1 1
0 0 0 0 0 0 1 || 2 2 2 2 2 1 0
Round 23:
0 0 1 1 0 0 1 || 0 1 0 0 1 2 0
0 0 [0] 0 0 0 1 || 0 1 [2] 2 1 2 0
0 0 0 0 0 0 0 || 1 1 2 2 2 1 1
1 0 0 2 0 0 0 || 0 1 2 0 2 1 1
0 0 0 0 0 0 1 || 1 1 2 2 2 1 0
Round 24:
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 [0] 0 0 0 0 || 1 1 [2] 2 2 1 1
1 0 0 2 0 0 0 || 0 1 2 0 2 1 1
0 0 0 0 0 0 1 || 1 1 2 2 2 1 0
Round 25:
0 0 0 0 0 [0] 1 || 0 0 0 0 0 [2] 0
0 0 0 0 0 0 1 || 0 0 0 0 0 2 0
0 0 0 0 0 0 0 || 1 1 1 1 1 1 1
1 0 0 1 0 0 0 || 0 1 1 0 1 1 1
0 0 0 0 0 0 1 || 1 1 1 1 1 1 0
Round 26:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
[0] 0 0 0 0 0 0 || [1] 1 1 1 1 0 0
1 0 0 1 0 0 0 || 0 1 1 0 1 1 1
0 0 0 0 0 0 1 || 1 1 1 1 1 1 0
Round 27:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 [0] 0 0 0 0 || 0 0 [1] 1 1 0 0
0 0 0 1 0 0 0 || 0 0 1 0 1 1 1
0 0 0 0 0 0 1 || 0 0 1 1 1 1 0
Round 28:
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 0 0 || 0 0 0 0 0 0 0
0 0 0 0 0 [0] 0 || 0 0 0 0 0 [1] 1
0 0 0 0 0 0 1 || 0 0 0 0 0 1 0
Done in 28 rounds
이것은 깊이 O (3 ^ (n))의 트리를 사용하여 해결할 수 있습니다. 여기서 n은 모든 제곱의 합입니다.
우선 O (9 ^ n)의 나무로 문제를 해결하는 것은 사소한 일이며 가능한 모든 폭격 위치를 고려하십시오. 예를 들어 Alfe의 구현을 참조하십시오 .
다음으로 우리는 아래에서 위로 폭탄을 터뜨리면서도 최소한의 폭탄 패턴을 얻을 수 있음을 깨달으십시오.
- 왼쪽 하단에서 시작하십시오.
- 이해가되는 유일한 연극 (위와 오른쪽)으로 망각으로 폭파 시키십시오.
- 한 칸 오른쪽으로 이동합니다.
- 목표는 0보다 큰 값을 가지지 만, 똑바로 위 또는 오른쪽으로 이해되는 두 가지 연극 각각을 고려하고 목표 값을 1 씩 줄이고 각 가능성에 대해 새로운 분기를 만듭니다.
- 다른 것을 오른쪽으로 움직입니다.
- 목표는 0보다 큰 값을 가지지 만, 타당한 3 개의 연극 (상단, 위, 위)을 고려하고 목표 값을 1 씩 줄이고 각 가능성에 대해 새로운 브랜치를 만듭니다.
- 행이 제거 될 때까지 5 단계와 6 단계를 반복하십시오.
- 퍼즐이 풀릴 때까지 행을 위로 이동하고 1 ~ 7 단계를 반복합니다.
이 알고리즘은 정확하기 때문에
- 어느 시점에서 각 행을 완료해야합니다.
- 행을 완성하려면 항상 위, 아래 또는 그 행 내에서 플레이해야합니다.
- 행에서 또는 행 아래에서 행하는 것보다 가장 잘 지워지지 않은 행 위의 행을 선택하는 것이 항상 좋습니다.
실제로이 알고리즘은 이웃을 정기적으로 폭격하고 검색 크기를 줄이기 때문에 이론상 최대 값보다 정기적으로 더 좋습니다. 각 폭탄이 4 개의 추가 목표 값을 감소 시킨다고 가정하면 알고리즘은 O (3 ^ (n / 4)) 또는 대략 O (1.3 ^ n)에서 실행됩니다.
이 알고리즘은 여전히 기하 급수적이므로 검색 깊이를 제한하는 것이 좋습니다. 허용되는 분기 수를 일부 숫자 X로 제한 할 수 있으며,이 깊이에 도달하면 알고리즘이 지금까지 식별 한 최상의 경로 (터미널 잎 중 하나에서 최소 총 보드 합계를 갖는 경로)를 선택하도록합니다. ). 그런 다음 알고리즘은 O (3 ^ X) 시간에 실행되도록 보장되지만 정답을 얻을 수는 없습니다. 그러나 증가 된 계산과 더 나은 답변 사이의 균형이 가치가 있다면 항상 X를 높이고 경험적으로 테스트 할 수 있습니다.
평가 기능, 총계 :
int f (int ** matrix, int width, int height, int x, int y)
{
int m[3][3] = { 0 };
m[1][1] = matrix[x][y];
if (x > 0) m[0][1] = matrix[x-1][y];
if (x < width-1) m[2][1] = matrix[x+1][y];
if (y > 0)
{
m[1][0] = matrix[x][y-1];
if (x > 0) m[0][0] = matrix[x-1][y-1];
if (x < width-1) m[2][0] = matrix[x+1][y-1];
}
if (y < height-1)
{
m[1][2] = matrix[x][y+1];
if (x > 0) m[0][2] = matrix[x-1][y+1];
if (x < width-1) m[2][2] = matrix[x+1][y+1];
}
return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}
목적 함수 :
Point bestState (int ** matrix, int width, int height)
{
Point p = new Point(0,0);
int bestScore = 0;
int b = 0;
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
{
b = f(matrix,width,height,i,j);
if (b > bestScore)
{
bestScore = best;
p = new Point(i,j);
}
}
retunr p;
}
기능 파괴 :
void destroy (int ** matrix, int width, int height, Point p)
{
int x = p.x;
int y = p.y;
if(matrix[x][y] > 0) matrix[x][y]--;
if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;
if (y > 0)
{
if(matrix[x][y-1] > 0) matrix[x][y-1]--;
if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
}
if (y < height-1)
{
if(matrix[x][y] > 0) matrix[x][y+1]--;
if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
}
}
목표 기능 :
bool isGoal (int ** matrix, int width, int height)
{
for (int i=0; i<width; i++)
for (int j=0; j<height; j++)
if (matrix[i][j] > 0)
return false;
return true;
}
선형 최대화 기능 :
void solve (int ** matrix, int width, int height)
{
while (!isGoal(matrix,width,height))
{
destroy(matrix,width,height, bestState(matrix,width,height));
}
}
이것은 최적은 아니지만 더 나은 평가 기능을 찾아서 최적화 할 수 있습니다.
.. 그러나이 문제에 대해 생각할 때, 주요 문제 중 하나가 어느 시점에서 0 중간에 버려진 숫자를 얻는 것이라고 생각하고 있었으므로 다른 접근 방식을 취할 것입니다. 가능한 한 0을 이스케이프하여 기존의 최소값을 최소화합니다.
이 모든 문제는 편집 거리를 계산하는 것입니다. 주어진 행렬과 영 행렬 사이의 Levenshtein 거리의 변형을 간단히 계산하십시오. 여기서 편집은 중간 배열 사이의 거리를 저장하기 위해 동적 프로그래밍을 사용하여 폭격으로 대체됩니다. 행렬의 해시를 키로 사용하는 것이 좋습니다. 의사 파이썬에서 :
memo = {}
def bomb(matrix,i,j):
# bomb matrix at i,j
def bombsRequired(matrix,i,j):
# bombs required to zero matrix[i,j]
def distance(m1, i, len1, m2, j, len2):
key = hash(m1)
if memo[key] != None:
return memo[key]
if len1 == 0: return len2
if len2 == 0: return len1
cost = 0
if m1 != m2: cost = m1[i,j]
m = bomb(m1,i,j)
dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
memo[key] = dist
return dist
이것은 첫 번째 질문에 대한 답변이었습니다. 나는 그가 매개 변수를 변경 한 것을 보지 못했습니다.
모든 대상 목록을 작성하십시오. 하락에 의해 영향을받는 양수 값 (자체 및 모든 이웃)을 기반으로 대상에 값을 지정하십시오. 가장 높은 가치는 9입니다.
영향을받는 대상 (내림차순) 수에 따라 대상을 정렬하고 영향을받는 각 대상의 합계에서 2 차 내림차순으로 정렬합니다.
가장 높은 순위의 대상에 폭탄을 떨어 뜨린 다음 대상을 다시 계산하고 모든 대상 값이 0이 될 때까지 반복하십시오.
동의, 이것이 항상 가장 최적 은 아닙니다 . 예를 들어
100011
011100
011100
011100
000000
100011
이 접근법은 5 개의 폭탄을 제거해야합니다. 그러나 최적의 방법은 4에서 가능합니다. 여전히, 아주 가까이 있고 역 추적은 없습니다. 대부분의 상황에서 최적이거나 매우 가깝습니다.
이 문제는 원래 문제 번호를 사용하여 28 개의 폭탄을 해결합니다.
이 방법을 보여주는 코드 추가 (버튼이있는 양식 사용) :
private void button1_Click(object sender, EventArgs e)
{
int[,] matrix = new int[10, 10] {{5, 20, 7, 1, 9, 8, 19, 16, 11, 3},
{17, 8, 15, 17, 12, 4, 5, 16, 8, 18},
{ 4, 19, 12, 11, 9, 7, 4, 15, 14, 6},
{ 17, 20, 4, 9, 19, 8, 17, 2, 10, 8},
{ 3, 9, 10, 13, 8, 9, 12, 12, 6, 18},
{16, 16, 2, 10, 7, 12, 17, 11, 4, 15},
{ 11, 1, 15, 1, 5, 11, 3, 12, 8, 3},
{ 7, 11, 16, 19, 17, 11, 20, 2, 5, 19},
{ 5, 18, 2, 17, 7, 14, 19, 11, 1, 6},
{ 13, 20, 8, 4, 15, 10, 19, 5, 11, 12}};
int value = 0;
List<Target> Targets = GetTargets(matrix);
while (Targets.Count > 0)
{
BombTarget(ref matrix, Targets[0]);
value += 1;
Targets = GetTargets(matrix);
}
Console.WriteLine( value);
MessageBox.Show("done: " + value);
}
private static void BombTarget(ref int[,] matrix, Target t)
{
for (int a = t.x - 1; a <= t.x + 1; a++)
{
for (int b = t.y - 1; b <= t.y + 1; b++)
{
if (a >= 0 && a <= matrix.GetUpperBound(0))
{
if (b >= 0 && b <= matrix.GetUpperBound(1))
{
if (matrix[a, b] > 0)
{
matrix[a, b] -= 1;
}
}
}
}
}
Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
}
private static List<Target> GetTargets(int[,] matrix)
{
List<Target> Targets = new List<Target>();
int width = matrix.GetUpperBound(0);
int height = matrix.GetUpperBound(1);
for (int x = 0; x <= width; x++)
{
for (int y = 0; y <= height; y++)
{
Target t = new Target();
t.x = x;
t.y = y;
SetTargetValue(matrix, ref t);
if (t.value > 0) Targets.Add(t);
}
}
Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
return Targets;
}
private static void SetTargetValue(int[,] matrix, ref Target t)
{
for (int a = t.x - 1; a <= t.x + 1; a++)
{
for (int b = t.y - 1; b <= t.y + 1; b++)
{
if (a >= 0 && a <= matrix.GetUpperBound(0))
{
if (b >= 0 && b <= matrix.GetUpperBound(1))
{
if (matrix[ a, b] > 0)
{
t.value += 1;
t.sum += matrix[a,b];
}
}
}
}
}
}
필요한 수업 :
class Target
{
public int value;
public int sum;
public int x;
public int y;
}
참고 URL : https://stackoverflow.com/questions/15300149/bomb-dropping-algorithm
'Programing' 카테고리의 다른 글
| Swift에서 pull을 사용하여 새로 고치는 방법은 무엇입니까? (0) | 2020.04.29 |
|---|---|
| -XAllowAmbiguousTypes는 언제 적절한가요? (0) | 2020.04.29 |
| Expressjs에서 미들웨어 및 app.use는 실제로 무엇을 의미합니까? (0) | 2020.04.29 |
| 서브 프로세스 stdout을 한 줄씩 읽으십시오 (0) | 2020.04.29 |
| 파이썬에서“with”블록으로 돌아 오면 파일이 여전히 닫히나요? (0) | 2020.04.29 |