多段圖的最短路徑問題

建立一個(gè)從源點(diǎn)S到終點(diǎn)T的多段圖，設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法求出從S到T的最短路徑值，并輸出相應(yīng)的最短路徑。

例圖

改為序號(hào)下標(biāo)

思路

動(dòng)態(tài)規(guī)劃

首先確定能分段，即每一層的各個(gè)結(jié)點(diǎn)互不連通，后驅(qū)結(jié)點(diǎn)均在同一層。
通過有一定修改的bfs進(jìn)行分段，然后從最后一段，依段數(shù)逐段取最小路徑，有點(diǎn)類似最小路徑算法。

#include <iostream>
#include <vector>
#include <deque>
#define NODE_COUNT 8
#define MAX_SEG 5
#define INF 255
#define NO_NEXT -1
using namespace std;

int nodes[NODE_COUNT][NODE_COUNT];
int beginPos;
int endPos;

struct Segment {
    vector<int> nodes;
};

void setEdge(int graph[NODE_COUNT][NODE_COUNT], int from, int to, int weight) {
    graph[from][to] = weight;
}

bool isConnect(int graph[NODE_COUNT][NODE_COUNT], int from, int to) {
    return graph[from][to] != INF;
}

int getWeight(int graph[NODE_COUNT][NODE_COUNT], int from, int to) {
    return graph[from][to];
}

void setSegment(int graph[NODE_COUNT][NODE_COUNT], vector<Segment>& segments,int beginPos,int endPos) {
    int pos = beginPos;
    //避免同一段中結(jié)點(diǎn)被重復(fù)push
    bool check[NODE_COUNT] = {false};
    //bfs隊(duì)列
    deque<int> nowSegNodes;
    nowSegNodes.push_back(beginPos);
    deque<int> nextSegNodes;
    //第一段只有beginPos
    Segment newSeg;
    segments.push_back(newSeg);
    segments[0].nodes.push_back(pos);
    int segIndex = 1;
    while (pos != endPos) {
        //cout << "現(xiàn)在在bfs" << pos << "結(jié)點(diǎn)" << endl;
        for (int i = 0; i < NODE_COUNT; i++) {
            if (!check[i] && isConnect(graph, pos, i)) {
                if (segments.size() - 1 < segIndex) {
                    Segment newSeg;
                    segments.push_back(newSeg); 
                }
                //分段
                //cout << i << "是第" << segIndex << "段" << endl;
                segments[segIndex].nodes.push_back(i);
                //入下一段的隊(duì)
                nextSegNodes.push_back(i);
                check[i] = true;
            }
        }
        //出隊(duì)
        nowSegNodes.pop_front();
        //如果當(dāng)前段的隊(duì)列沒有結(jié)點(diǎn)了
        if (nowSegNodes.empty()) {
            //下一段的隊(duì)列置空，成為該段隊(duì)列
            nowSegNodes.swap(nextSegNodes);
            segIndex++;
        }
        pos = nowSegNodes.at(0);
    }
}

void findMinRoute(int graph[NODE_COUNT][NODE_COUNT], vector<Segment>& segments, int beginPos, int endPos) {
    int segCount = segments.size();
    //記錄距離endPos最近的鄰接的node
    int nextPos[NODE_COUNT];
    //記錄該pos到endPost的距離
    int dist[NODE_COUNT];
    dist[endPos] = 0;
    nextPos[endPos] = NO_NEXT;
    //遍歷每個(gè)分段
    for (int nowSeg = segCount - 2; nowSeg >= 0; nowSeg--) {
        //遍歷分段中每個(gè)pos
        //cout << "分段" << nowSeg << "開始遍歷" << endl;
        for (int nowNodeIndex = 0; nowNodeIndex < segments[nowSeg].nodes.size(); nowNodeIndex++) {
            int nowPos = segments[nowSeg].nodes[nowNodeIndex];
            //cout << nowPos << endl;
            //int minDist = INF;
            dist[nowPos] = INF;
            //跟上個(gè)分段的Node作比較
            for (int lastSegNodeIndex = 0; lastSegNodeIndex < segments[nowSeg + 1].nodes.size(); lastSegNodeIndex++) {
                int lastSegNodePos = segments[nowSeg + 1].nodes[lastSegNodeIndex];
                if (isConnect(graph, nowPos, lastSegNodePos) && getWeight(graph, nowPos, lastSegNodePos) + dist[lastSegNodePos] < dist[nowPos]) {
                    dist[nowPos] = getWeight(graph, nowPos, lastSegNodePos) + dist[lastSegNodePos];
                    nextPos[nowPos] = lastSegNodePos;
                }
            }
        }
        //cout << "分段" << nowSeg << "遍歷完成" << endl;
    }
    cout << "最短路徑:";
    int tempindex = beginPos;
    cout << beginPos;
    while (tempindex != endPos) {
        cout << "-->" << nextPos[tempindex];
        tempindex = nextPos[tempindex];
    }
    cout << "\n";
    cout << "最短路徑長度:" << dist[beginPos] << endl;
}

int main(void) {
    vector<Segment> segments;
    beginPos = 0;
    endPos = 7;

    for (int i = 0; i < NODE_COUNT; i++)
        for (int j = 0; j < NODE_COUNT; j++)
            nodes[i][j] = INF;

    //初始化
    setEdge(nodes, 0, 1, 1);
    setEdge(nodes, 0, 2, 2);
    setEdge(nodes, 0, 3, 5);
    setEdge(nodes, 1, 4, 4);
    setEdge(nodes, 1, 5, 11);
    setEdge(nodes, 2, 5, 5);
    setEdge(nodes, 2, 4, 9);
    setEdge(nodes, 2, 6, 16);
    setEdge(nodes, 3, 6, 2);
    setEdge(nodes, 4, 7, 18);
    setEdge(nodes, 5, 7, 13);
    setEdge(nodes, 6, 7, 2);

    //分段
    setSegment(nodes, segments, beginPos, endPos);

    int segCount = segments.size();
    for (int i = 0; i < segCount; i++) {
        cout << "第" << i << "段:";
        for (int j = 0; j < segments[i].nodes.size(); j++) {
            cout << segments[i].nodes[j] << " ";
        }
        cout << "\n";
    }

    findMinRoute(nodes, segments, beginPos, endPos);
    system("pause");
    return 0;
}

運(yùn)行示例

有向無環(huán)圖的最短路徑問題

建立一個(gè)從源點(diǎn)S到終點(diǎn)E的有向無環(huán)圖，設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法求出從S到E的最短路徑值，并輸出相應(yīng)的最短路徑。

示例

改為序號(hào)下標(biāo)

思路

動(dòng)態(tài)規(guī)劃

拓?fù)渑判蚝?，由后至前?dòng)態(tài)規(guī)劃。
實(shí)現(xiàn)上用鄰接矩陣檢索效率更高一些，這里用鄰接表是寫拓?fù)渑判虮容^方便。
結(jié)構(gòu)體數(shù)組組、vector一起用，并且元素都是int的時(shí)候很容易寫錯(cuò)，需要多注意一點(diǎn)。

#include <iostream>
#include <vector>
#include <deque>
#define NODE_COUNT 6
#define INF 255
using namespace std;

struct Node {
    int pos;
    int weight;
};

vector<Node> graph[NODE_COUNT];

int indegree[NODE_COUNT] = {0};
int beginPos;
int endPos;

void setEdge(vector<Node> graph[NODE_COUNT],int from, int to, int weight, int indegree[NODE_COUNT]) {
    //鄰接表
    Node node;
    node.pos = to;
    node.weight = weight;
    graph[from].push_back(node);
    indegree[to]++;
}

void topoSort(vector<Node> graph[NODE_COUNT], int indegree[NODE_COUNT], vector<int>& linearList) {
    deque<int> queue;
    for (int i = 0; i < NODE_COUNT; i++) {
        if (indegree[i] == 0) {
            queue.push_back(i);
        }
    }
    while (!queue.empty()) {
        int pos = queue.front();
        queue.pop_front();
        linearList.push_back(pos);
        for (int j = 0; j < graph[pos].size(); j++) {
            if (!--indegree[graph[pos].at(j).pos]) {
                queue.push_back(graph[pos].at(j).pos);
            }
        }
    }
}

int getWeight(vector<Node> graph[NODE_COUNT],int from,int to) {
    for (int i = 0; i < graph[from].size(); i++) {
        if (graph[from][i].pos == to) {
            return graph[from][i].weight;
        }
    }
    return INF;

}

void findMinRoute(vector<Node> graph[NODE_COUNT], int beginPos, int endPos,vector<int> linearlist) {
    int nextPos[NODE_COUNT];
    int dist[NODE_COUNT];
    for (int i = 0; i < NODE_COUNT; i++) {
        dist[i] = getWeight(graph, i, endPos);
    }
    dist[endPos] = 0;
    for (int i = NODE_COUNT - 2; i >= 0; i--) {
        int nowpos = linearlist[i];
        for (int j = 0; j < graph[nowpos].size(); j++) {
            if (graph[nowpos][j].weight + dist[graph[nowpos][j].pos] <= dist[nowpos]) {             
                nextPos[nowpos] = graph[nowpos][j].pos;
                dist[nowpos] = graph[nowpos][j].weight + dist[graph[nowpos][j].pos];

            }
        }
    }
    cout << "最短路徑長為:" << dist[beginPos] << endl;
    cout << "最短路徑為:";
    int temp = beginPos;
    cout << beginPos;
    while (temp != endPos) {
        cout << "-->" << nextPos[temp];
        temp = nextPos[temp];
    }
    cout << "\n";
}

int main(void) {

    beginPos = 0;
    endPos = 5;

    setEdge(graph, 0, 1, 1, indegree);
    setEdge(graph, 0, 2, 2, indegree);
    setEdge(graph, 1, 3, 6, indegree);
    setEdge(graph, 2, 1, 4, indegree);
    setEdge(graph, 2, 4, 3, indegree);
    setEdge(graph, 3, 4, 1, indegree);
    setEdge(graph, 3, 5, 2, indegree);
    setEdge(graph, 4, 5, 1, indegree);

    vector<int> list;
    topoSort(graph, indegree, list);
    cout << "拓?fù)渑判?";
    for (int i = 0; i < list.size(); i++) {
        cout << list[i] << " ";
    }
    cout << "\n";

    findMinRoute(graph, beginPos, endPos, list);
    system("pause");
    return 0;
}

運(yùn)行示例

最長遞增子序列問題

給定一個(gè)整數(shù)數(shù)組，設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法求出該數(shù)組中的最長遞增子序列。

思路

動(dòng)態(tài)規(guī)劃

從第一個(gè)元素開始，每個(gè)元素都遍歷k-1個(gè)之前的元素，記錄該元素及之前最大子序列長度。同時(shí)再用一個(gè)數(shù)組記錄前驅(qū)元素的下標(biāo)。

#include <iostream>
#define LENGTH 10
#define NO_PRE -1
using namespace std;
int INDEX[LENGTH] = { 1,5,2,3,4,8,3,9,10,7 };

void printSeq(int* posRecord,int* index,int now) {
    if (posRecord[now] == NO_PRE) {
        cout << index[now] << " ";
        return;
    }
    printSeq(posRecord, index, posRecord[now]);
    cout << index[now] << " ";
}

void lis(int* index,int length) {
    int* lenRecord = new int[length];
    //記錄index中該位置元素的前一個(gè)元素
    int* posRecord = new int[length];
    lenRecord[0] = 1;
    for (int i = 0; i < length; i++){
        lenRecord[i] = 1;
        posRecord[i] = NO_PRE;
        for (int j = 0; j < i; j++) {
            if (index[j]<index[i] && lenRecord[j]>lenRecord[i] - 1) {
                lenRecord[i] = lenRecord[j] + 1;
                posRecord[i] = j;
            }
        }
    }
    //找出最長的length
    int maxLen = 0;
    int maxLenPos = 0;
    for (int i = 0; i < length; i++) {
        if (lenRecord[i] > maxLen) {
            maxLen = lenRecord[i];
            maxLenPos = i;
        }
    }
    //輸出子序列
    printSeq(posRecord, index, maxLenPos);
}



int main(void) {
    cout << "原序列:";
    for (int i = 0; i < LENGTH; i++) {
        cout << INDEX[i] << " ";
    }
    cout << "\n最大子序列:";
    lis(INDEX, LENGTH);
    cout << "\n";
    system("pause");
    return 0;
}

運(yùn)行示例