図論--中国郵便配達員問題

中国の郵便配達員の問題は悲しいです.前後に3日ぐらいかかりました.の今日終わったばかりです.の
 
まず、質問について説明します.
郵便配達員は郵便局から送信し、管轄区内の街ごとに少なくとも1回通過し、郵便局に戻るように要求した.この条件の下で、どのように最短ルートを選択しますか?
街が形成された図自体がオラ回路であれば、最短路は自然にすべての街の全長である.しかし、そうでなければ、いくつかのパスを繰り返しなければなりません.言い換えれば、どのようにして繰り返したパスの全長を最も短くしますか.
 
この問題に関連する問題は次のとおりです.
(1)オーラループであるか否かを判別する(まず図は連通しなければならず,次にすべての頂点の度数は偶数である.
(2)オーラループでなければ、複数の頂点がある度数が奇数(奇点と呼ぶでしょう、奇点の個数は必ず偶数)であれば、この図をオーラ図として構築しなければなりません.
  (2.1)各奇点間の最短パスの計算
  (2.2)これらの奇点と奇点間の最短経路を1つの二分図とし,二分図の最小重みマッチングを求める.(例えば、4つの奇点1,2,3,4がある場合、左1と右1の間の辺の重みは無限大であり、左1と右2の辺の重みは奇点1から奇点2までの最短距離であり、このようにして最終的に得られる最小重みの総数は実際に増加した経路長の2倍である)
  (2.3)最小重みマッチングで得られた2対の頂点は,これらの頂点間の最短経路が通るエッジを繰り返し,形成されたオーラループが最短となる.
(3)オーラの帰り道を見つける.ネット上で2つの探し方が見られます.1つはfleuryアルゴリズムで、1つは私自身が命名した輪を描く方法で、つまり「すべての頂点の度数が偶数の連通図が必ずオラ回路である」ことを証明する方法です.
 
したがって、プロセス全体にわたるアルゴリズムには、次のものが含まれます.
(1)最短パスアルゴリズム.(これはみんな知っていると思いますから、余計なことは言うまでもありません)
(2)KMアルゴリズムは二分図の最小重みマッチングを求める.(http://www.cnblogs.com/zhuangli/archive/2008/08/03/1259248.html 私も主にこれを参考にしています)
(3)fleuryアルゴリズムまたは「輪を描く」アルゴリズム.
 
具体的に実装するとき、私は2つのマトリクスでこの図を記録します.1つは点と点の間の距離で、1つは点と点の間の辺の数(最初は最大1本)で、同時に総経路の長さを記録します.次に,2つの配列を用いて奇点を記録し,1つは索参照である.すべての奇点を始点として最短経路を求める.最短経路で求めた最短距離を二分図の重み行列に記録し,記録経路の配列を返した.そして最短経路で求めた重み行列を最小重みマッチングの入力として最適マッチングを求める.最後に,インデックス配列と最短経路を求める際に得られた経路(s)を記録点と点間の辺数の行列に1つずつ追加し,それをオーラループを求める入力とする.
 
主な関数は次のとおりです.

int connected( int** g, int vnum );
int* bestMatch( int** weight, int n );
path* eulerCircle( int** g, int* indgr, int num );
main(){
	
	int vnum, onum, i, j, k, total=0, hasEuler=1;
	//ge is to record the number of edges between to nodes while gd the distance
	int** ge, **gd;
	int* indgr;
	int** weight;
	printf( "enter the number of nodes: " );
	scanf( "%d", &vnum );
	ge = (int**)malloc( sizeof(int*)*vnum );
	gd = (int**)malloc( sizeof(int*)*vnum );
	for( i=0; i=0 ){
				index[j]=i;
				paths[j] = (int*)malloc( sizeof(int)*vnum );
				//in the shortestPath we also construct the weight map of the oddSet
				shortestPath( gd, paths[j], vnum ,i, weight, oddSet ); 
				j++;
			}
		}
		
		//now is to find the best Match for the oddset
		int* result = bestMatch( weight, onum );
		for( i=0; i 
  
 
 
  
connected()   ，      ，           。
 
  
shortestPath()    paths，weight, oddSet                 。paths                         ，                。
 
  
bestMatch()      ，      ，       。（                 ）
 
  
eulerCircle() 0  ，                 。
 
  
              ，  。