多段图的最短路径问题
建立一个从源点S到终点T的多段图，设计一个动态规划算法求出从S到T的最短路径值，并输出相应的最短路径。
例图
改为序号下标
思路
动态规划
首先确定能分段，即每一层的各个结点互不连通，后驱结点均在同一层。
通过有一定修改的bfs进行分段，然后从最后一段，依段数逐段取最小路径，有点类似最小路径算法。
#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;
//避免同一段中结点被重复push
bool check[NODE_COUNT] = {false};
//bfs队列
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 << "现在在bfs" << pos << "结点" << 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);
//入下一段的队
nextSegNodes.push_back(i);
check[i] = true;
}
}
//出队
nowSegNodes.pop_front();
//如果当前段的队列没有结点了
if (nowSegNodes.empty()) {
//下一段的队列置空，成为该段队列
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;
//遍历每个分段
for (int nowSeg = segCount - 2; nowSeg >= 0; nowSeg--) {
//遍历分段中每个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;
//跟上个分段的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;
}
运行示例
有向无环图的最短路径问题
建立一个从源点S到终点E的有向无环图，设计一个动态规划算法求出从S到E的最短路径值，并输出相应的最短路径。
示例
改为序号下标
思路
动态规划
拓扑排序后，由后至前动态规划。
实现上用邻接矩阵检索效率更高一些，这里用邻接表是写拓扑排序比较方便。
结构体数组组、vector一起用，并且元素都是int的时候很容易写错，需要多注意一点。
#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 << "拓扑排序:";
for (int i = 0; i < list.size(); i++) {
cout << list[i] << " ";
}
cout << "\n";
findMinRoute(graph, beginPos, endPos, list);
system("pause");
return 0;
}
运行示例
最长递增子序列问题
给定一个整数数组，设计一个动态规划算法求出该数组中的最长递增子序列。
思路
动态规划
从第一个元素开始，每个元素都遍历k-1个之前的元素，记录该元素及之前最大子序列长度。同时再用一个数组记录前驱元素的下标。
#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中该位置元素的前一个元素
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;
}
运行示例
网友评论