中国郵路問題のプログラミングの解
9771 ワード
中国郵路問題(Chinese Postman Problem)は非常に古典的な図論問題である.郵便配達員が手紙を送り、彼が配達を担当しているすべての街(すべての街が双方向に通行し、すべての街が一度以上通過できる)を歩き終え、任務を終えて郵便局に戻り、どのようなルートで歩けば、彼が歩いた道のりが最も短いのだろうか.この問題を図論に抽象化する言語は,連通図を与え,各エッジの重み値が街の長さである場合,本問題は図中に回路を求め,回路の総重み値を最小にすることに変換される.
街の連通図がオーラ図であれば、図中のオーラ戻り路を1本だけ要求すればよい.そうでなければ、郵便配達員が任務を遂行するには、いくつかの街を何度も繰り返さなければならない.1回繰り返すと平行なエッジが追加され、元の対応する図形が多重図になります.追加する平行エッジの総重み値が最小であればよいだけです.そこで,我々の問題は,奇度数ノードを有する重み付き連通図において,新しい図が奇度数ノードを含まず,増加したエッジの総重み値が最小になるように,いくつかの平行エッジを増加させることに転化した.
増加したエッジの総重み値の最小を求めるスキームは,すべての奇度頂点(偶数個)を2つのグループに分け,各グループの2つの点に対して最短経路を求め,さらに各グループの総重み値を求める必要がある.すべてのグループの状況に対して、最小の重み値を見つけるのが最適です.
以下、ソースコードを直接アップします.
転載先:https://www.cnblogs.com/guocai/archive/2012/07/08/2581979.html
街の連通図がオーラ図であれば、図中のオーラ戻り路を1本だけ要求すればよい.そうでなければ、郵便配達員が任務を遂行するには、いくつかの街を何度も繰り返さなければならない.1回繰り返すと平行なエッジが追加され、元の対応する図形が多重図になります.追加する平行エッジの総重み値が最小であればよいだけです.そこで,我々の問題は,奇度数ノードを有する重み付き連通図において,新しい図が奇度数ノードを含まず,増加したエッジの総重み値が最小になるように,いくつかの平行エッジを増加させることに転化した.
増加したエッジの総重み値の最小を求めるスキームは,すべての奇度頂点(偶数個)を2つのグループに分け,各グループの2つの点に対して最短経路を求め,さらに各グループの総重み値を求める必要がある.すべてのグループの状況に対して、最小の重み値を見つけるのが最適です.
以下、ソースコードを直接アップします.
#include
#include
#include
#include
#include
using namespace std;
#define MAX_NODE 26 //
#define COST_NO_LINK INT_MAX // INT_MAX
int Graph[MAX_NODE][MAX_NODE];
int Cost[MAX_NODE][MAX_NODE];
int V_dingdianshu, E_bianshu, Start_Point; // ， （ 0 ）
int Odd_Grouping[MAX_NODE]; // 0 ， 1 ， 2 ， 2 ， 3 ，……
int Bak_Odd_Grouping[MAX_NODE]; // ， ， ， 。
int SHORTEST_PATH_WEIGHT(COST_NO_LINK); // ， ， 。 Bak_Odd_Grouping 。
int Dist[MAX_NODE]; // Dijstra ， v0 v1 ， v0
int ShortCache[MAX_NODE][MAX_NODE]; // Dijstra ， v0 v1 ， ， ， ， 。
// ， Graph Cost
void Input()
{
int i, j;
int m, n;
char cs, cm, cn;
int w;
cout << " ：";
cin >> V_dingdianshu;
cout << " ：";
cin >> E_bianshu;
cout << " ：";
cin >> cs;
Start_Point = cs - 'a';
for(i = 0; i < V_dingdianshu; i++)
{
for(j = 0; j < V_dingdianshu; j++)
{
Graph[i][j] = 0;
ShortCache[i][j] = 0;
Cost[i][j] = COST_NO_LINK;
}
Cost[i][i] = 0; // 0
}
cout << " " << E_bianshu << " （ a ）：" << endl;
for(i = 0; i < E_bianshu; i++)
{
cin >> cm >> cn >> w;
m = cm - 'a';
n = cn - 'a';
Graph[m][n] += 1;
Graph[n][m] += 1;
Cost[m][n] = w;
Cost[n][m] = w;
}
}
// G v0 v1 ， dist 。 dist （ dist[v] v0 v ）
// Cache ， ， Dist ， dist[v] v0 v
// dist[v1]， v0 v1
int Dijstra(int v0, int v1, bool useCache)
{
if(useCache && ShortCache[v0][v1] != 0) // ，
{
return ShortCache[v0][v1];
}
int i, s, w, min, minIndex;
bool Final[MAX_NODE];
// ，
for (s = 0; s < V_dingdianshu; s++)
{
Final[s] = false;
Dist[s] = COST_NO_LINK; //
}
// v0 v0 ，
Final[v0] = true;
Dist[v0] = 0;
s = v0; // 0 v0
for (i = 0; i < V_dingdianshu; i++)
{
// 1
for(w = 0; w < V_dingdianshu; w++)
{
if(!Final[w] // w
&& Cost[s][w] < COST_NO_LINK // s
&& Dist[w] > Dist[s] + Cost[s][w]) // s
{
if(Dist[s] + Cost[s][w] <= 0)
{
cout << " 。" << endl;
exit(-1);
}
Dist[w] = Dist[s] + Cost[s][w];
}
}
// 1.5 v1，
if(s == v1)
{
ShortCache[v0][v1] = Dist[s];
ShortCache[v1][v0] = Dist[s];
return Dist[s];
}
// 2
min = COST_NO_LINK;
for(w = 0; w < V_dingdianshu; w++)
{
if(!Final[w] //
&& Dist[w] < min) //
{
minIndex = w;
min = Dist[w];
}
}
s = minIndex;
Final[s] = true;
}
cerr << " 。。。 " << endl;
exit(-1);
}
//
// start （ 0 ），
//
// start ：start
bool ConnectivityTest(int start, bool& bNoPoints)
{
set nodeSet; //
vector for_test_nodes; //
int i, j;
set singlePoints; //
//
bool hasEdge = false;
for(i = 0; i < V_dingdianshu; i++)
{
hasEdge = false;
for(j = 0; j < V_dingdianshu; j++) // 0，
{
if (Graph[i][j] > 0)
{
hasEdge = true;
break;
}
}
if (!hasEdge)
{
singlePoints.insert(i);
}
}
bNoPoints = (singlePoints.size() == V_dingdianshu); // bNoPoints
if(singlePoints.find(start) != singlePoints.end()) // start
{
return false;
}
for_test_nodes.push_back(start); //
while(for_test_nodes.size() > 0)
{
int testNode = for_test_nodes.back();
for_test_nodes.pop_back();
for(i = 0; i < V_dingdianshu; i++)
{
if(Graph[testNode][i] > 0)
{
if(nodeSet.insert(i).second)
{
for_test_nodes.push_back(i);
}
}
}
}
for(i = 0; i < V_dingdianshu; i++)
{
if (singlePoints.find(i) == singlePoints.end()
&& nodeSet.find(i) == nodeSet.end())
// ， ， ，
{
return false;
}
}
return true;
}
// ， ，
int OddTest()
{
int i, j, rSum, count;
//
for(i = 0; i < V_dingdianshu; i++)
{
Odd_Grouping[i] = 0; // 0
Bak_Odd_Grouping[i] = 0;
}
count = 0;
for(i = 0; i < V_dingdianshu; i++)
{
rSum = 0;
for(j = 0; j < V_dingdianshu; j++)
{
rSum += Graph[i][j]; // i
}
if(rSum % 2 == 1)
{
Odd_Grouping[i] = 1;
count++;
}
}
return count;
}
void Bak_Grouping()
{
int i;
for(i = 0; i < V_dingdianshu; i++)
{
Bak_Odd_Grouping[i] = Odd_Grouping[i];
}
}
// ，level 2 。
// 。 。
bool Grouping(int level)
{
if(level < 2)
{
cerr << " 2 level 。" << endl;
exit(-1);
}
int i, j, findI = -1;
for(i = 0; i < V_dingdianshu; i++)
{
if(Odd_Grouping[i] == 1)
{
Odd_Grouping[i] = level; // 。
findI = i;
break;
}
}
bool re = true;
if(findI == -1) // ， 。
{
int weightSum = 0;
for(i = 2; i < level; i++) // level 2 level-1 ， i
{
int index[2];
int *pIndex = index;
for(j = 0; j < V_dingdianshu; j++)
{
if(Odd_Grouping[j] == i)
{
*pIndex = j;
if(pIndex == index + 1) // index
{
break;
}
pIndex++;
}
}
weightSum += Dijstra(index[0], index[1], true); // ， ， 。 。
}
if(weightSum < SHORTEST_PATH_WEIGHT) // ，
{
Bak_Grouping(); // ，
SHORTEST_PATH_WEIGHT = weightSum;
return true; // ，
}
else
{
return false; // ，
}
}
else if(findI > -1)
{
// ， 。
for(/* for */; i < V_dingdianshu; i++)
{
if(Odd_Grouping[i] == 1) //
{
Odd_Grouping[i] = level;
re = Grouping(level + 1);
Odd_Grouping[i] = 1; // ，
}
}
}
else
{
cerr << "findCount " << endl;
exit(-1);
}
if(findI > -1)
{
Odd_Grouping[findI] = 1; // ，
}
return re;
}
void AddShortPath(int from, int to)
{
int i, back;
Dijstra(from, to, false); // ， dist
back = to;
while(back != from) // from ... back ... to
{
for(i = 0; i < V_dingdianshu; i++)
{
if(i != back
&& Dist[i] < COST_NO_LINK // from i
&& Dist[back] < COST_NO_LINK // from back
&& Dist[i] + Cost[i][back] == Dist[back]) // from i back from back ， i ( ， (i,back) ， Dist[i] + Cost[i][back] )
{
Graph[i][back]++; //
Graph[back][i]++;
back = i;
break;
}
}
if(i == V_dingdianshu) // ： break ++
{
cerr << " ， 。。。" << endl;
exit(-1);
}
}
}
// odd
void AddShortPaths()
{
int i, j;
for(i = 0; i < V_dingdianshu; i++)
{
if(Bak_Odd_Grouping[i] > 1)
{
for(j = i + 1; j < V_dingdianshu; j++)
{
if(Bak_Odd_Grouping[j] == Bak_Odd_Grouping[i])
{
AddShortPath(i, j);
break;
}
}
}
}
}
//
void OddDeal()
{
// ，
int oddCount = OddTest();
if(oddCount > 0)
{
if(oddCount % 2 == 1)
{
cerr << " ， ？" << endl;
exit(-1);
}
// 。。。
Grouping(2); // odd2
AddShortPaths(); // odd
}
}
/*
Fleury
wi=v0e1v1…eivi ， E-｛e1,e2,…,ei｝ ei+1:
1)、 ei+1 vi+1 ；
2)、 ， ei+1 Gi=G-｛e1,e2,…,ei｝ 。
3)、 (2) ， 。
*/
void Fleury(int start)
{
int i;
int vi = start; // v0e1v1…eivi
bool bNoPoints, bCnecTest;
cout << " ：";
while(true)
{
// ei+1
for(i = 0; i < V_dingdianshu; i++)
{
if (Graph[vi][i] > 0)
{
// （vi，i）
Graph[vi][i]--; // Graph ， ， 。
Graph[i][vi]--;
bCnecTest = ConnectivityTest(i, bNoPoints);
if(!bNoPoints && !bCnecTest) // i， ，
{
Graph[vi][i]++;
Graph[i][vi]++;
continue;
}
// （vi，i）
cout << (char)('a' + vi) << "-" << (char)('a' + i) << " ";
vi = i;
break;
}
}
if (i == V_dingdianshu)
{
cout << endl;
break; //
}
}
}
int main()
{
Input();
bool b;
if(!ConnectivityTest(0, b)) // b ， 。
{
cout << " ！
";
exit(0);
}
OddDeal(); //
Fleury(Start_Point); //
return 0;
} 転載先:https://www.cnblogs.com/guocai/archive/2012/07/08/2581979.html