[algorithm] 폭탄 적하 알고리즘

시간이 없어서 부분 솔루션 만 중단해야했지만이 부분 솔루션 조차도이 문제를 해결하기위한 하나의 잠재적 접근법에 대한 통찰력을 제공하기를 바랍니다.

어려운 문제에 직면했을 때 나는 문제 공간에 대한 직관을 개발하기 위해 더 간단한 문제를 생각해 내고 싶습니다. 여기서 제가 취한 첫 번째 단계는이 2 차원 문제를 1 차원 문제로 줄이는 것입니다. 라인을 고려하십시오 :

0 4 2 1 3 0 1

어떻게 든 또는 다른, 당신은 당신이 또는 그 주위에 폭탄을 투하해야합니다 알고 4폭격에 아무런 혜택이없는, 낮은 숫자가 그 자리의 왼쪽부터 0으로 내려 4 번 자리 0또는를 4을 폭격 이상은 2. 사실, 나는 2그 4지점이 0으로 떨어질 때까지 폭탄을 터뜨리는 것이 적어도 다른 전략보다 좋은 것이라고 믿습니다 (그러나 엄격한 증거는 부족합니다)4 전략 왼쪽에서 오른쪽으로 선을 진행할 수 0 원에 다운 이처럼 :

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 b c d
e f g h
i j k l
m n o p

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki

*2* 3  7 *1*
 1  5  6  2
 2  1  3  2
*6* 9  6 *4*

*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

 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