js 알고리즘 초기 탐색 05 (알고리즘 모델 02 - 동적 계획 과 욕심 알고리즘)

앞의 글 에서 (js 알고리즘 초기 엿 보기 02 (정렬 알고리즘 02 - 병합, 빠 르 고 쌓 기)우 리 는 어떻게 분 치 법 으로 병합 순 서 를 실현 하 는 지 배 웠 다. 그러면 동태 계획 은 분 치 법 과 약간 유사 하지만 분 치 법 은 문 제 를 서로 독립 된 서브 문제 로 분해 하고 마지막 으로 그들의 결 과 를 조합 하 는 것 이 고 동태 계획 은 문 제 를 서로 의존 하 는 서브 문제 로 분해 하 는 것 이다.
그러면 저 는 또 하나의 의문 이 있 습 니 다. 앞에서 재 귀 를 말 했 습 니 다. 그러면 재 귀 는 요? 분 치 법 과 동적 계획 은 일종 의 수단 이나 방법 같 고 재 귀 는 구체 적 으로 조작 하 는 도구 나 집행 자 입 니 다. 분 치 법 이 든 동적 계획 이 든 다른 어떤 재 미 있 는 방법 이 든 재 귀 도 구 를 사용 하여 '실행' 코드 를 사용 할 수 있 습 니 다.
동적 계획 으로 문 제 를 해결 하 는 것 은 주로 세 가지 절차 로 나 뉜 다. 1. 서브 문 제 를 정의 하고 2. 반복 적 으로 실행 하여 서브 문 제 를 해결 해 야 하 는 부분 (예 를 들 어 재 귀 로 '반복') 을 실현 한다. 3. 경계 조건 을 식별 하고 해결 해 야 한다. 이렇게 말 하면 좀 어리둥절 하 다. 그러면 우 리 는 동적 계획 으로 전형 적 인 문 제 를 해결 해 보 자.
1. 최소 동전 거스름돈 문제
최소 동전 거스름돈 문 제 는 동전 거스름돈 문제 의 변종 이다. 동전 거스름돈 문 제 는 거스름돈 의 액수 와 사용 가능 한 동전 의 액수, 그리고 그 에 대응 하 는 수량 을 제시 하 는 것 이다. 동전 거스름돈 을 얼마나 찾 느 냐 하 는 것 이다. 최소 동전 거스름돈 문 제 는 그 중 가장 적은 양의 동전 을 찾 는 것 이다. 예 를 들 어 우 리 는 1, 5, 10, 25 액면가 의 동전 이 있 는데 36 액면가 의 동전 을 찾 으 려 면돈 을 어떻게 거스름돈 으로 드릴 까요? 답 은 25 개, 10 개, 1 개 입 니 다. 이것 이 답 입 니 다. 그러면 어떻게 위의 문 제 를 알고리즘 으로 바 꾸 어 해결 할 수 있 습 니까? 컴퓨터 가 있 으 면 빠 르 고 간단 한 결 과 를 얻 을 수 있 습 니 다. 우리 가 더 이상 머리 를 써 서 문 제 를 해결 하지 않 아 도 됩 니 다. 다음은 코드 를 살 펴 보 겠 습 니 다.

//      
function MinCoinChange(coins) {
    // coins          。
    //                           。
    var coins = coins;
    //           
    var cache = {};
    //              ，
    this.makeChange = function (amount) {
        //    this     this.makeChange      ，                          （    ）
        var me = this;
        // amount          ，      ，       ，              。
        if(!amount) {
            return [];
        };
        
        // cache[amount]                              
        //               
        if(cache[amount]) {
            return cache[amount];
        };
        // min           ，newMin newAmount            ，                      。
        var min = [],newMin,newAmount;
        //     coins   。    ，      conis                。（      coin   ）
        for(var i = 0; i < coins.length; i++) {
            //   coins      。
            var coin = coins[i];
            //                    。    newAmount  。
            newAmount = amount - coin;
            //          ，  newAmount    0  ，           ，             。
            //                   ，    。
            if(newAmount >= 0) {
                newMin = me.makeChange(newAmount);
            };
            //         newAmount               ，            
            //    if                ，   ，             。
            console.log(!min.length,min.length)
            if(newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
                //console.log('new Min' + min + 'for' + amount);
            }
        };
        //cache   1 amount       
        //console.log(cache)
        return (cache[amount] = min);
    };
};

var minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36))

이것 은 동적 계획 의 방법 으로 최소 동전 찾기 문 제 를 해결 하 는 것 입 니 다. 그러면 욕심 산법 으로 최소 동전 찾기 문 제 를 어떻게 해결 하 는 지 살 펴 보 겠 습 니 다. 그렇다면 욕심 산법 은 무엇 입 니까? 욕심 산법 은 가장 좋 은 서브 구 조 를 가 진 문제 에서 특히 효과 적 입 니 다. 가장 좋 은 서브 구 조 는 부분 적 인 최 적 화 를 통 해 전체 국면 을 결정 할 수 있다 는 뜻 입 니 다. 쉽게 말 하면 문 제 는 분해 할 수 있 습 니 다.하위 문 제 를 해결 하기 위해 서 는 하위 문제 의 최 적 화 를 최종 문제 의 최 적 화 된 문제 로 미 룰 수 있 습 니 다. 욕심 산법 은 동적 계획 과 달리 모든 하위 문제 의 해결 방안 을 선택 하여 되 돌 릴 수 없습니다. 동적 계획 은 이전의 연산 결 과 를 저장 하고 앞의 결과 에 따라 현 재 를 선택 하여 되 돌 리 는 기능 이 있 습 니 다.
코드 를 보 겠 습 니 다.

function MinCoinChange(coins) {
    var coins = coins;
    this.makeChange = function (amount) {
        var change = [],total = 0;
        for(var i = coins.length; i >= 0; i--) {
            var coin = coins[i];
            while(total + coin <= amount) {
                change.push(coin);
                total += coin;
            }
        }
        return change;
    };
}

var minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36))

우 리 는 위의 코드 를 보 았 습 니 다. 주요 논 리 는 동적 계획 과 매우 비슷 합 니 다. 다만 코드 자체 가 아주 간단 해 야 합 니 다. 욕심 산법 은 우리 의 동전 중에서 가장 큰 것 부터 가 져 갈 수 없 을 때 까지 다음 것 을 가 져 가 최종 결과 로 돌아 갈 때 까지 두 가지 해결 방법 이 통과 하지 못 하 는 지 살 펴 보 겠 습 니 다. 동적 계획 은 cache 를 통 해 이전의 계산 결 과 를 캐 시 할 것 입 니 다.현재 의 계산 결과 에서 이전 과 비교 하여 둘 사이 의 최 적 화 를 선택 하 십시오. 욕심 산법 은 현재 의 최 적 화 를 선택 할 뿐 되 돌아 가지 않 고 기록 전의 해결 방안 을 저장 하지 않 습 니 다.
 
2. 가방 문제
가방 문 제 는 조합 최적화 문제 입 니 다. 문 제 는 이 렇 습 니 다. 고정 크기 를 정 하고 무게 가 W 인 가방 과 가치 와 무게 가 있 는 물건 을 휴대 할 수 있 습 니 다. 가장 좋 은 해결 방안 을 찾 아 가방 에 넣 은 물품 의 총 중량 이 W 를 초과 하지 않 고 총 가치 가 가장 큽 니 다. 이 문 제 는 두 가지 버 전이 있 습 니 다. 하 나 는 0 - 1 가방 문제 입 니 다. 이 버 전 은가방 에 온전한 물건 만 넣 을 수 있 으 며 분리 할 수 없습니다. 또 하 나 는 점수 아 이 템 을 넣 을 수 있 습 니 다. 우 리 는 나중에 욕심 산법 으로 점수 가방 문 제 를 해결 할 것 입 니 다.
코드 를 보 겠 습 니 다.

//    
function knapSack(capacity,weights,values,n) {
    var i,w,a,b,kS = [];

    for (var i = 0; i <= n; i++) {
        kS[i] = [];
    }

    for(i = 0; i <= n; i++) {
        for(w = 0; w <= capacity; w++) {
            if(i == 0 || w == 0) {
                kS[i][w] = 0;
            } else if(weights[i - 1] <= w) {
                a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
                b = kS[i - 1][w];
                kS[i][w] = (a > b) ? a : b;
            } else {
                kS[i][w] = kS[i - 1][w];
            }
        }
    }
    findValues(n,capacity,kS,weights,values);
    return kS[n][capacity];
};

function findValues(n,capacity,kS,weights,values) {
    var i = n,k = capacity;
    console.log('          ：');
    while(i > 0 && k > 0) {
        if(kS[i][k] !== kS[i - 1][k]) {
            console.log('  ' + i + ',  ：' + weights[i- 1] + ',  ：' + values[i - 1]);
            i--;
            k = k - kS[i][k];
        } else {
            i--;
        }
    }
}

var values = [3,4,5],weights = [2,3,4],capacity = 5,n = values.length;
console.log(knapSack(capacity,weights,values,n))

위의 코드 에서, 우 리 는 처음에 하나의 행렬 을 초기 화하 여 각종 해결 방안 을 저장 하 였 으 며, 가방 에 넣 는 물품 i 는 capacity 보다 작 아야 합 니 다. 즉, 가방 에 넣 을 수 있 는 무게 보다 작 아야 가방 에 넣 을 수 있 는 일부분 이 될 수 있 습 니 다. 그렇지 않 으 면 가방 에 넣 을 수 있 는 무 게 를 초과 할 수 있 습 니 다. 이것 은 허용 되 지 않 습 니 다. 또한 두 개의 물품 이 있 을 때.무게 가 같 을 때 우 리 는 가치 가 비교적 큰 어느 것 을 선택한다.
사실 위의 알고리즘 은 계속 최적화 할 수 있 습 니 다. 여 기 는 많이 말 하지 않 고 여러분 들 이 관심 이 있 으 면 깊이 공부 할 수 있 습 니 다.
욕심 산법 의 점수 가방 문제:
점수 가방 문 제 는 0 - 1 가방 문제 와 유사 합 니 다. 다만 점수 가방 에 일부 아 이 템 을 넣 을 수 있 습 니 다. 코드 는 어렵 지 않 습 니 다. 여러분 이 직접 쓰 시 면 알 수 있 습 니 다.

function knapSack(capacity,values,weights) {
    var n = values.length,load = 0,i = 0,val = 0;

    for(i = 0; i < n && load < capacity; i++) {
        if(weights[i] <= (capacity - load)) {
            val += values[i];
            load += weights[i];
        } else {
            var r = (capacity - load) / weights[i];
            val += r * values[i];
            load += weights[i];
        }
    }
    return val;
}
var values = [3,4,5],weights = [2,3,4],capacity = 6;

console.log(knapSack(capacity,values,weights))

3. 최 장 공공 서브 시퀀스 문제
이 문 제 는 이 렇 습 니 다. 두 문자열 서열 중 가장 긴 하위 서열 의 길 이 를 찾 아 보 세 요. 가장 긴 하위 서열 은 두 문자열 서열 에서 같은 순서 로 나타 나 지만 반드시 연속 적 인 문자열 서열 이 라 고 요구 하 지 는 않 습 니 다.

//       LCS
function lcs(wordX,wordY) {
    var m = wordX.length,n = wordY.length,l = [],i,j,a,b;
    var solution = [];

    for (i = 0; i <= m; ++i) {
        l[i] = [];
        solution[i] = [];
        for(j = 0; j <= n; ++j) {
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }

    for(i = 0; i <= m; i++) {
        for(j = 0; j <= n; j++) {
            if(i == 0 || j == 0) {
                l[i][j] = 0;
            } else if(wordX[i - 1] == wordY[j - 1]) {
                l[i][j] = l[i - 1][j - 1] + 1;
                solution[i][j] = 'diagonal';
            } else {
                a = l[i - 1][j];
                b = l[i][j - 1];
                l[i][j] = (a > b) ? a : b;
                solution[i][j] = (l[i][j] == l[i - 1][j]) ? 'top' : 'left';
            }
        }
    }
    printSolution(solution,l,wordX,wordY,m,n);
    return l[m][n];
}

function printSolution(solution,l,wordX,wordY,m,n) {
    var a = m,b = n,i,j,
    x = solution[a][b],
    answer = '';

    while(x !== '0') {
        if(solution[a][b] === 'diagonal') {
            answer = wordX[a - 1] + answer;
            a--;
            b--;
        } else if(solution[a][b] === 'left') {
            b--;
        } else if(solution[a][b] === 'top') {
            a--;
        }
        x = solution[a][b];
    }
    console.log('lcs:' + answer);
}

lcs("acbaed","abcadf");

 　　
4. 행렬 체인 상승
이 문 제 는 행렬 을 곱 하 는 가장 좋 은 방법 (순서) 을 찾 는 것 이다.시작 하기 전에 행렬 의 상승 을 간단히 설명 할 필요 가 있 습 니 다. 쉽게 말 하면 n 행 m 열 을 넣 은 행렬 A 와 m 행 p 열 을 넣 은 행렬 B 를 곱 하면 n 행 p 열의 행렬 C 를 얻 을 수 있 습 니 다. 한 행렬 의 행 이 다른 행렬 의 열 과 같은 두 행렬 만 이 곱 할 수 있 음 을 주의해 야 합 니 다.
그러면 만약 에 제 가 A, B, C, D 네 개의 행렬 을 곱 하고 싶다 면 곱셈 이 결합 율 (초등학교 수학 지식 점) 을 만족 시 키 기 때문에 우 리 는 이렇게 (A (B (CD)) 하거나 이렇게 (AB) (CD)) 할 수 있 습 니 다.등 다섯 가지 상승 방법, 그러나 주의해 야 할 것 은 각 상승 순서 가 다 르 고 우리 의 계 산 량 도 다르다 는 것 이다. 그래서 우 리 는 함 수 를 구축 하여 계 산 량 이 가장 적은 상승 방법 을 찾 아야 한다. 이것 이 바로 행렬 체인 상승 문제 이다.

//     
function matrixChainOrder(p,n) {
    var i,j,k,l,q,m = [];


    //    s
    var s = [];
    for(i = 0; i <= n; i++) {
        s[i] = [];
        for(j = 0; j <= n; j++) {
            s[i][j] = 0;
        }
    }

    for(i = 0; i <= n; i++) {
        m[i] = [];
        m[i][i] = 0;
    };

    for(l = 2; l < n; l++) {
        for(i = 1; i <= n - l + 1; i++) {
            j = i + l - 1;
            m[i][j] = Number.MAX_SAFE_INTEGER;
            for(k = i; k <= j - 1; k++) {
                q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];
                if(q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;//    
                }
            }
        }
    }
    printOptimalParenthesis(s,1,n - 1);
    return m[1][n - 1];
}

function printOptimalParenthesis(s,i,j) {
    if(i == j) {
        console.log("A[" + i + "]");
    } else {
        console.log("(");
        printOptimalParenthesis(s,i,s[i][j]);
        printOptimalParenthesis(s,s[i][j] + 1,j);
        console.log(")");
    }
}

var p = [10,100,5,50,1,100];
n = p.length;
console.log(matrixChainOrder(p,n));

 
마지막 으로, 본인 의 수준 이 제한 되 어 있 기 때문에, 능력 과 큰 신 은 여전히 거리 가 멀 습 니 다. 잘못 이 있 거나 불분명 한 점 이 있 으 면, 여러분 의 가르침 을 아 끼 지 않 기 를 바 랍 니 다. 감사합니다. 더 높이 날 고 싶 은 채소 새 입 니 다.