동적 계획: Swift 실현
동적 기획 (dynamic programming, 약칭 dp) 은 분할 방법 에 비해 다음 과 같다.
유사 점 은 모두 조합 자 문제 의 해 를 통 해 원 문 제 를 해결 하 는 것 이다.차이 점 은 분 치 방법 으로 문 제 를 서로 교차 하지 않 는 서브 문제 로 나 누고 재 귀적 인 해결 서브 문제 로 나 누 는 것 이다.한편, 동태 계획 은 서브 문제 가 중첩 되 는 상황 에 있 고 서로 다른 서브 문제 의 해 제 는 반복 적 으로 진행 되 며 공공 서브 문 제 를 반복 적 으로 해결 하 는 것 이다.
동적 계획 의 주 제 는 모든 하위 문제 에 대해 한 번 만 풀 고 기록 하 는 것 이다.동적 계획 의 응용 장면 은 최적화 문제 (optimization problem) 를 해결 하 는 데 있다.
동적 계획 알고리즘 절차:
밤 1) 강철 막대 절단
입력 원: 강철 막대 길이
n 및 각 사이즈 의 강철 막대 단가 pi 목표: 가격 rn 최대사고의 방향
먼저 두 절 (특수 한 두 절 에 속 하지 않 음) 의 가장 좋 은 절단 수익 을 고려 합 니 다: rn = max (pn, r1 + rn - 1 + r2 + rn - 2,..., rn - 1 + r1)
상식 은 반증 법 으로 확실히 이때 최대 치 를 얻 었 다 는 것 을 증명 할 수 있다.
두 절 단 된 두 개의 강철 막대 조합 은 최 적 화 된 서브 구조 (optional substructure) 의 성질 을 만족 시 킵 니 다. 문 제 는 관련 서브 문제 의 최 적 화 된 조합 으로 이 루어 져 있 고 이런 서브 문 제 는 독립 적 으로 해결 할 수 있 습 니 다.
이런 사고방식 의 이 곡 동공 의 변종 은 왼쪽 (오른쪽 도 마음대로) 에서 길이 가 i 인 한 단락 을 잘라 내 고 n - i 의 한 단락 만 계속 절단 (귀속) 하고 왼쪽 은 절단 하지 않 아 도 된다 는 것 이다.이러한 장점 은 매우 뚜렷 하 다. 한 단계 에서 한 방향 만 재 귀적 으로 호출 하고 대충 말 하면 절반 의 함수 호출 을 줄 일 수 있다.문 제 는 이렇게 설명 할 수 있다.
첫 번 째 단락 의 길 이 는 n 이 고 수익 은 pn 이 며 나머지 부분의 길 이 는 0 (왼쪽, 절단 하지 않 음) 이 며 대응 하 는 수익 은 r0 이 며 새로운 공식 을 얻 을 수 있다. rn = max (pi + rn - i) (1 < = i < = n)
위 에서 아래로 순환 하여 실현 하 다.
의사 코드 는 다음 과 같 습 니 다:
CUT-ROD(p, n)
if n == 0
return 0
q = -∞
for i = 1 to n
q = max(q, p[i] + CUT-ROD(p, n-i))
return q
상술 한 알고리즘 효율 은 입력 규모 가 클 때 찌꺼기 로 변 한다. 원인 은 매우 간단 하 다. 컴퓨터 는 이미 계 산 된 문 제 를 끊임없이 반복 해서 계산한다.
동적 계획 을 사용 하여 해답 을 구하 다
주 제 는 공간 교환 시간, 시공 저울질 (time - memory trade - of) 이다.
위 에서 아래로 의사 코드:
MEMOIZED-CUT-ROD(p, n)
let r[0..n] be a new array
for i = 0 to n
r[i] = -∞
return MEMOIZED-CUT-ROD-AUX(p, n, r)
MEMOIZED-CUT-ROD-AUX(p, n, r)
if r[n] >= 0
return r[n]
if n == 0
q = 0
else q = -∞
for i = 1 to n
q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n-i, r))
r[n] = q
return q
아래 에서 위로 의사 코드:
BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] be a new array
r[0] = 0
for j = 1 to n
q = -∞
for i = 1 to j
q = max(q, p[i] + r[j-i])
r[j] = q
return r[n]
재 구성 해
확장 버 전, 가장 좋 은 절단 방법 저장
EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
let r[0..n] and s[0..n] be new array
r[0] = 0
for j = 1 to n
q = -∞
for i = 1 to j
if q < p[i] + r[j-i]
q = p[i] + r[j-i]
s[j] = i
r[j] = q
return r and s
PRINT-CUT-ROD-SOLUTION(p, n)
(r, s) = EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
while n > n
print s[n]
n = n - s[n]
Swift 실현
주: 아래 에서 위로 정렬 해 야 합 니 다. 본 밤 에 가격 은 사이즈 의 길이 와 정비례 하기 때문에 이미 비 체감 서열 입 니 다 ~
func extendedBottomUpCutRod(priceList: [Int], rotLength: Int) -> (result: [Int], solution: [Int]) {
var result = Array (count: rotLength + 1 , repeatedValue: 0 )
var solution = Array (count: rotLength + 1 , repeatedValue: 0 )
for var j = 1; j <= rotLength; ++j {
var optNext = -10000
for var i = 1; i <= j; i++ {
if optNext < priceList[i] + result[j - i] {
optNext = priceList[i] + result[j - i]
solution[j] = i
}
}
result[j] = optNext
}
return (result, solution)
}
func printCutRodSolution(priceList: [Int], var rotLength: Int) {
var result: [Int]
var solution: [Int]
(result, solution) = extendedBottomUpCutRod(priceList, rotLength)
while rotLength > 0 {
println(solution[rotLength])
rotLength = rotLength - solution[rotLength]
}
}
var priceArray: [Int] = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
printCutRodSolution(priceArray, 4)
밤 2) 최 장 공공 서열
입력 원본: 배열 X, 배열 Y 목표: 두 그룹의 최 장 공공 교차 집합 서브 배열 을 구하 십시오.
최 장 공공 서브 시퀀스 문제 (longest - common - subsequence problem) 에 부 딪 혔 을 때, LCD 문 제 를 해결 하기 위해 dp 를 주저 하지 않 고 사용 할 수 있 습 니 다.
사고의 방향
DP 문제 단계 1: 가장 잘 풀 리 는 구조 적 특징 을 묘사 하고 폭력 적 으로 해결 하 는 효율 이 매우 무 섭 습 니 다. 만약 에 X 가 Y 보다 짧 고 길이 가 m 라면 그 하위 서열 은 2 ^ m 개 입 니 다.그 러 니까 2 ^ m 개 는 풀 수 있다 는 거 야.입력 배열 의 규모 가 크 면 자 연 스 럽 게 하하.
우선 LCS 문제 가 최 우선 서브 구조 적 성격 을 갖 고 있 는 지 살 펴 본다.LCS 의 하위 문제 (소 규모) 는 자 연 스 럽 게 두 서열 의 접두사 입 니 다.
각종 반증 법 은 LCS 문제 가 최 적 화 된 서브 구 조 를 갖 고 있다 는 것 을 증명 할 수 있 고 약 하 다.수학 하 는 거 아니 야.
LCS 최 우수 서브 구조의 특징 은 다음 과 같다. 만약 에 X =, Y = 이 두 개의 서열 이 고 Z = X 와 Y 의 임 의 LCS 라면
끊 임 없 는 1, 2, 3 은 하나의 해 (재 귀 해) 를 얻 을 수 있다.
DP 문제 절차 2: 재 귀 해 를 구 하 는 것 은 LCS 최 우수 서브 구조의 성질 에 따라 1, 2, 3 은 다음 과 같은 공식 (재 귀 해) 이 있 을 수 있다.
DP 문제 절차 3: 2 차원 배열 c [0. m, 0. n] 를 밑 에서 위로 계산 하여 c [i, j] 의 해 를 저장 합 니 다.줄 의 주 순서 (즉, 외곽 for 순환 은 1 에서 m) 에 따라 보조 목록 b [1. m, 1. n] 가 구조 최 적 화 를 도 와 줘 야 합 니 다.b [i, j] 에 저 장 된 매 거 형 은 c [i, j] 를 계산 할 때의 하위 문 제 를 가장 잘 풀 수 있 습 니 다.c [m, n] 는 X 와 Y 의 LCS 길 이 를 저장 합 니 다.
DP 문제 4 단계: 가장 좋 은 위조 코드 제시
LCS-LENGTH(X, Y)
m = X.length
n = Y.length
let b[1..m, 1..n] and c[0..m, 0..n] be new tables
for i = 1 to m // 0 ，
c[i, 0] = 0
for j = 0 to n
c[0, j] = 0
for i = 1 to m
for j = 1 to n
if xi == yi
c[i, j] = c[i-1, j-1] + 1
b[i, j] = left-top // left-top
elseif c[i-1, j] >= c[i, j-1]
c[i, j] = c[i-1, j]
b[i, j] = top // top
else
c[i, j] = c[i, j-1]
b[i, j] = left // left
return c and b
표 b 를 통 해 우 리 는 X 와 Y 를 추적 해 낸 LCS 를 신속하게 찾 아 볼 수 있다.LCS 위조 코드 인쇄 는 다음 과 같 습 니 다:
PRINT-LCS(b, X, i, j) // X,Y
if i == 0 or j == 0
return
if b[i, j] == left-top
PRINT-LCS(b, X, i-1, j-1)
print xi
elseif b[i, j] = top
PRINT-LCS(b, X, i-1, j)
else
PRINT-LCS(b, X, i, j-1)
알고리즘 개선
실제로 우 리 는 상수 시간 내 에 c [i, j] 와 c [i - 1, j - 1], c [i - 1, j], c [i, j - 1] 의 관 계 를 판단 할 수 있다.그러므로 보조 표 b 가 전혀 필요 하지 않 을 수 있다.
Swift 실현
// c[i, j] c[i-1, j-1]，c[i-1, j]，c[i, j-1]
enum LCSDirection: Int {
case left_top = 0
case top = 1
case left = 2
}
//
struct Matrix {
let rows: Int, columns: Int
var grid: [Int]
init(rows: Int, columns: Int) {
self.rows = rows
self.columns = columns
grid = Array(count: rows * columns, repeatedValue: -10000)
}
func indexIsValidForRow(row: Int, column: Int) -> Bool {
return row >= 0 && row < rows && column >= 0 && column < columns
}
subscript(row: Int, column: Int) -> Int {
get {
assert(indexIsValidForRow(row, column: column), "Index out of range")
return grid[(row * columns) + column]
}
set {
assert(indexIsValidForRow(row, column: column), "Index out of range")
grid[(row * columns) + column] = newValue
}
}
}
func LCSLength(var rowArray: [Int], var columnArray: [Int]) -> (b: Matrix, c: Matrix){
var m = rowArray.count
var n = columnArray.count
var b: Matrix = Matrix(rows: m+1, columns: n+1)
var c: Matrix = Matrix(rows: m+1, columns: n+1)
for var i = 1; i <= m; i++ {
c[i, 0] = 0
}
for var j = 0; j <= n; j++ {
c[0, j] = 0
}
for var i = 1; i <= m; i++ {
for var j = 1; j <= n; j++ {
if rowArray[i-1] == columnArray[j-1] {
c[i, j] = c[i-1, j-1] + 1
b[i, j] = LCSDirection.left_top.rawValue
} else if c[i-1, j] >= c[i, j-1] {
c[i, j] = c[i-1, j]
b[i, j] = LCSDirection.top.rawValue
} else {
c[i, j] = c[i, j-1]
b[i, j] = LCSDirection.left.rawValue
}
}
}
return (b, c)
}
func printLCS(b: Matrix, rowArray: [Int], rowIndex: Int, columnIndex: Int) {
if rowIndex == 0 || columnIndex == 0 { return }
if b[rowIndex, columnIndex] == LCSDirection.left_top.rawValue {
printLCS(b, rowArray, rowIndex-1, columnIndex-1)
println(rowArray[rowIndex-1])
} else if b[rowIndex, columnIndex] == LCSDirection.top.rawValue {
printLCS(b, rowArray, rowIndex-1, columnIndex)
} else {
printLCS(b, rowArray, rowIndex, columnIndex-1)
}
}
var A: [Int] = [1, 2, 3, 2, 4, 1, 2]
var B: [Int] = [2, 4, 3, 1, 2, 1]
var bRecord: Matrix
var cCommon: Matrix
(bRecord, cCommon) = LCSLength(A, B)
printLCS(bRecord, A, A.count, B.count)
밤 3) 가장 좋 은 두 갈래 검색 나무
잇다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
백그라운드에서 값을 계산하고 Swift 동시성 이후에 결과 사용값을 계산해야 하고 메인 스레드를 차단하지 않으려면 계산된 값을 반환하는 Swift Task 구조에서 해당 값을 계산하면 됩니다. Swift 동시성 이전에는 백그라운드 대기열로 이동하여 필요한 값을 계산하고 필요한 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
