프로 그래 밍 - 행렬 왼쪽 상단 에서 오른쪽 하단 으로

제목 요구: 마이너스 행렬 이 아 닌 왼쪽 상단 에서 오른쪽 하단 으로 가 는 알고리즘 을 만 듭 니 다. 매번 왼쪽 이나 아래로 한 칸 만 이동 할 수 있 고 지나 간 경로 노드 좌표 와 최소 값 을 출력 할 수 있 습 니 다.방법: 동적 계획 법 상태 전이 방정식 stat [i] [j] = min {stat [i - 1] [j], stat [i] [j - 1]}.논리: 목적 노드 는 위 노드 나 왼쪽 노드 에서 내 려 온 것 으로 위 노드 와 왼쪽 노드 의 어느 것 이 작은 지 판단 하고 어느 노드 에서 내 려 온 것 인지 판단 하 며 하나의 direct 매트릭스 로 내 려 온 방향 을 기록한다. 만약 에 이 노드 가 위 노드 에서 내 려 온 것 이 라면 direct 매트릭스 의 이 노드 를 1 로 정 하고 그렇지 않 으 면 0 으로 정한다.네 거 티 브 매트릭스 이름 은 matrix 로 정의 되 지 않 습 니 다. 이 matrix 행렬 은 두 가지 특수 한 경로 가 있 습 니 다. 즉, 첫 번 째 줄 과 첫 번 째 열 은 모든 노드 가 왼쪽 노드 에서 만 걸 어 올 수 있 기 때 문 입 니 다. 첫 번 째 줄 의 모든 노드 는 위의 노드 에서 걸 어 옵 니 다.이렇게 하면 첫 번 째 줄 의 각 노드 에서 왼쪽 상단 노드 까지 의 가중치 와 첫 번 째 열 각 노드 에서 왼쪽 상단 노드 까지 의 가중치 를 얻 을 수 있다.예 를 들 어 (0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0) (2, 1) (2, 2) (2, 2) 대응 하 는 가중치 는 1, 2, 3, 4, 5 노드 (0, 0) 가 시작 점 이 고 노드 (2, 2) 가 종료 점 이 며 시작 점 에서 노드 (0, 1) 까지 의 총 가중치 에 (0, 0) 의 가중치 를 더 하면 (0, 1) 의 가중치 는 시작 점 에서 (0, 2) 까지 이다.의 총 가중치 는 (0, 0) 의 가중치 에 (0, 1) 의 가중치 에 (0, 2) 의 가중치 이다.같은 이치 로 (1, 0) 시작 점 까지 의 총 가중치, (2, 0) 시작 점 까지 의 총 가중치 를 얻 을 수 있다.얻 은 stat 표 는 1, 3, 6, 5 7 이 고 (1, 1) 노드 는 시작 점 까지 두 가지 방향 이 있 습 니 다. 하 나 는 그의 위쪽, 즉 (0, 1) 점 입 니 다. 하 나 는 그의 왼쪽 (1, 0) 점 입 니 다. stat 표를 통 해 알 수 있 듯 이 (0, 1) 점 의 총 가중치 는 3 입 니 다. (1, 0) 점 의 총 가중치 는 5 입 니 다. 가장 짧 은 경 로 를 얻 으 려 면.그래서 우 리 는 가장 작은 가중치 3 을 선택 하고 현재 노드 의 가중치 가 바로 현재 노드 에서 시작 노드 까지 의 총 가중치, 즉 8 이다.현재 가중치 가 위 에서 걸 어 왔 는 지 왼쪽 에서 걸 어 왔 는 지 기록 하기 위해 서 우 리 는 첫 번 째 direct 행렬 을 만 들 었 습 니 다. 초기 화 된 direct 행렬 은 0, 11, 0 입 니 다. 1 은 이 노드 가 왼쪽 에서 걸 어 왔 다 는 것 을 나타 내 고 0 은 이 노드 가 위 노드 에서 걸 어 왔 다 는 것 을 나타 내 며 stat 행렬 을 수정 할 때 도 direct 행렬 을 수정 해 야 합 니 다.2 층 순환 을 통 해 stat 매트릭스 와 direct 매 트릭 스 를 채 울 수 있 습 니 다. 채 워 진 stat 매트릭스 와 direct 매 트릭 스 는 stat 매트릭스 입 니 다. 1, 3, 6, 5, 8, 12, 10 15 direct 매트릭스: 0, 1, 0, 0, 0, 0, 1 stat 매트릭스 의 종료 정점 중의 가중치 가 가장 짧 은 경로 의 가중치 입 니 다.direct 매트릭스 에 따 르 면 우 리 는 목적 의 정점 (2, 2) 을 얻 을 수 있 습 니 다. 현재 direct 값 은 1 (현재 정점 왼쪽 에서 걸 어 온 다 는 뜻) 이 고 (2, 1) 은 왼쪽 정점 (2, 0) 에서 걸 어 왔 기 때 문 입 니 다. (2, 0) 은 위 정점 (1, 0) 에서 걸 어 왔 고 (1, 0) 은 위 (0, 0) 에서 걸 어 왔 기 때 문 입 니 다.시 에 걸 어 온 것 이 고 (0, 0) 시 는 시작 정점 이다.이 를 통 해 최 단 경로 와 최 단 경로 의 가중치 를 얻 었 습 니 다. 코드 는 다음 과 같 습 니 다.

# include 
# include 

using namespace std;

void getPath(vector<vector<int> > &matrix, int &value, vector<int> &path_i, vector<int> &path_j)
{
    if(matrix.empty())
        return;
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<int> > stat(rows, vector<int> (cols));  //              
    vector<vector<int> > direct(rows, vector<int> (cols)); //                (1     ,0     )）
    int sum = 0;
    for (int j = 0; j < cols; ++j)  //          
    {
        sum += matrix[0][j];
        stat[0][j] = sum;
        direct[0][j] = 1;
    }
    sum = 0;
    for (int i = 0; i < rows; ++i)  //          
    {
        sum += matrix[i][0];
        stat[i][0] = sum;
        direct[i][0] = 0;
    }
    for (int i = 1; i < rows; ++i)  //          
    {
        for (int j = 1; j < cols; ++j)
        {
            if (stat[i - 1][j] < stat[i][j - 1])
            {
                stat[i][j] = stat[i - 1][j] + matrix[i][j];
                direct[i][j] = 0;
            }
            else
            {
                stat[i][j] = stat[i][j - 1] + matrix[i][j];
                direct[i][j] = 1;
            }
        }
    }

    value = stat[rows - 1][cols - 1];  //         
    for (int i = rows -1, j = cols - 1; i >= 0 && j >= 0;)  //       
    {
            path_i.push_back(i);
            path_j.push_back(j);
            if (direct[i][j] == 1)
                j--;
            else
                i--;
    }
}
void printPath(vector<int> path_i, vector<int> path_j)  //     
{
    for (int i = path_i.size() - 1; i >= 0; --i)
    {
        cout << '(' << path_i[i] << ", " << path_j[i] << ')' << endl;
    }
}

int main(void)
{
    int matrix_temp[6][7] = {{0, 2, 8, 3, 7, 9, 6},
                            {5, 3, 7, 9, 6, 8, 1},
                            {3, 9, 2, 9, 8, 7, 6},
                            {8, 8, 1, 6, 9, 6, 8},
                            {3, 2, 9, 8, 7, 7, 1},
                            {4, 2, 9, 6, 5, 3, 9}};
    vector<vector<int> > matrix;
    int rows = 6;
    int cols = 7;
    for (int i = 0; i < rows; ++i)
    {
        vector<int> temp;
        for (int j = 0; j < cols; ++j)
        {
            temp.push_back(matrix_temp[i][j]);
        }
        matrix.push_back(temp);
        temp.clear();
    }
    vector<int> path_i;  //             
    vector<int> path_j;  //             
    int value;           //            
    getPath(matrix, value, path_i, path_j);
    cout << "value is " << value << endl;
    cout << "path: " << endl;
    printPath(path_i, path_j);
}

잘못된 점 이 있 으 면 지적 하여 바로잡아 주 십시오.