巡回セールスマンは誰ですか？ セールスマンとは、サンプルやカタログに従って製品を顧客に提供する会社の巡回販売代理店です。 そのタスクは、1回2回行ったことなくすべての目的地を移動し、出発点に戻ることです。
リトルメソッド
この方法の目的は、グラフ内の最小コストでハミルトニアンサイクルを検索することです。 それを見つけるには、次の手順に従う必要があります。
- コストマトリックスの各行で、最小要素を見つけ、その行のすべての要素からそれを減算します。 これは、ゼロを含まない列に対して行います。 各行と各列に少なくとも1つのゼロ要素が含まれるコストマトリックスを取得します。
- 行列の各ゼロ要素について、係数kを計算します。これは、このゼロの列と行の最小要素の合計に等しくなります。 最大係数のゼロを選択します（それらが複数ある場合は、いずれかを選択します）。 対応する弧をハミルトニアン輪郭に導入します。
- ゼロを選択した交点の行と列を削除します。
- グラフに戻り点があるかどうかを確認し、戻り値がある場合は最大値に変更します。 次数2の行列が残るまで、前の手順を繰り返します。
- 欠けている弧をハミルトニアン輪郭に導入します。 目的のサイクルが得られます。
実装
さらに拡張して他のアルゴリズムを使用するには、Algorithmクラスを作成します。
アルゴリズム
//Algorithm.h class Algorithm { public: char* name = "Algorithm"; // std::vector<std::vector<int>> data; // () Algorithm(); Algorithm(std::vector<std::vector<int>>); Algorithm(char*); bool LoadData(std::vector<std::vector<int>>); bool LoadData(char*); virtual void Run(); // protected: int GetStrCount(std::ifstream&); // int GetColCount(std::ifstream&); // virtual bool validateData(); // . Run() };
上記からわかるように、ファイルからデータをロードする方法と手動でここに実装されます。 それらの実装は、アプリケーションで表示できます。
次に、興味のあるアルゴリズムのクラスを作成します。 私たちの場合、LittleAlgorithm。
リトルアルゴリズム
class LittleAlgorithm : public Algorithm { public: vector<pair<int,int>> result; // . LittleAlgorithm(); LittleAlgorithm(vector<vector<int>>); LittleAlgorithm(char*); virtual void Run(); private: enum check{Row, Col}; int getMin(vector<vector<int>>, int, check); // / void matrixProcedure(vector<vector<int>>); // void showMatrix(vector<vector<int>>); // int getResultSum(); // virtual bool validateData(); };
ヘルパーメソッドの実装：
その他
void LittleAlgorithm::Run() { name = "Little algorithm"; Algorithm::Run(); matrixProcedure(vector<vector<int>>(data)); } int LittleAlgorithm::getMin(vector<vector<int>> matrix, int sel, check pos) { int min = INT32_MAX; for (int i = 0; i < matrix[sel].size() - 1; i++) switch (pos) { case LittleAlgorithm::Row: if (min > matrix[sel][i]) min = matrix[sel][i]; break; case LittleAlgorithm::Col: if (min > matrix[i][sel]) min = matrix[i][sel]; break; } return min; } void LittleAlgorithm::showMatrix(vector<vector<int>> temp) { std::cout << endl; std::cout << "\t"; for (int i = 0; i < temp[temp.size() - 1].size() - 1; i++) { std::cout << temp[temp.size() - 1][i] << "\t"; } std::cout << endl; std::cout << "\t"; for (int i = 0; i < temp[0].size(); i++) for (int j = 0; j<6; j++) std::cout << "_"; std::cout << endl <<endl; for (int i = 0; i < temp.size() - 1; i++) { std::cout << temp[i][temp.size() - 1] << " | " << "\t"; for (int j = 0; j < temp[i].size() - 1; j++) if(temp[i][j] != INT32_MAX && j != temp.size() - 1)std::cout << temp[i][j] << "\t"; else std::cout << "inf" << "\t"; std::cout << endl; } std::cout << endl << endl; } int LittleAlgorithm::getResultSum() { int sum = 0; for (int i = 0; i < result.size(); i++) sum += data[result[i].first - 1][result[i].second - 1]; return sum; } bool LittleAlgorithm::validateData() { // for (int i = 0; i < data.size(); i++) for (int j = 0; j < data[i].size(); j++) if (data[i][j] == 0) data[i][j] = INT32_MAX; vector<vector<int>> temp(data); for (int i = 0; i < data.size(); i++) data[i].push_back(i + 1); vector<int> numeration; for (int i = 0; i < data[0].size(); i++) numeration.push_back(i + 1); data.push_back(numeration); return true; }
そして、Littleメソッドを実装するメソッド自体は次のとおりです。
マトリックス
void LittleAlgorithm::matrixProcedure(vector<vector<int>> matrix) { // if (matrix.size() - 1 > 2){ vector<int> vertexes; for (int i = 0; i < result.size(); i++) { vertexes.push_back(result[i].first); vertexes.push_back(result[i].second); } for (int i = 0; i < vertexes.size(); i++) { pair<int, int> elem(INT32_MAX, INT32_MAX), elem1(INT32_MAX, INT32_MAX); for (int j = 0; j < vertexes.size(); j++) { if (vertexes[i] != vertexes[j]) { for (int k = 0; k < matrix[matrix.size() - 1].size() - 1; k++) { if (vertexes[i] == matrix[k][matrix[k].size() - 1]) elem.first = k; if (vertexes[j] == matrix[k][matrix[k].size() - 1]) elem1.first = k; } for (int k = 0; k < matrix.size() - 1; k++) { if (vertexes[i] == matrix[matrix.size() - 1][k]) elem.second = k; if (vertexes[j] == matrix[matrix.size() - 1][k]) elem1.second = k; } } } for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j<matrix.size() - 1; j++) if (i == elem1.first && j == elem1.second) matrix[elem1.first][elem1.second] = INT32_MAX; for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j < matrix.size() - 1; j++) if (i == elem.first && j == elem.second) matrix[elem.first][elem.second] = INT32_MAX; } } // for (int i = 0; i < matrix.size() - 1; i++) { int min = 0; if ((min = getMin(matrix, i, check::Row)) == INT32_MAX) { showMatrix(matrix); std::cout << endl << "Bad road" << endl; return; } if ((min = getMin(matrix, i, check::Row)) != 0) for (int j = 0; j < matrix[i].size() - 1; j++) if(matrix[i][j] != INT32_MAX) matrix[i][j] -= min; } // for (int i = 0; i < matrix[matrix.size() - 1].size() - 1; i++) { int min = 0; if ((min = getMin(matrix, i, check::Col)) == INT32_MAX) { showMatrix(matrix); std::cout << endl << "Bad road" << endl; return; } if ((min = getMin(matrix, i, check::Col)) != 0) for (int j = 0; j < matrix.size() - 1; j++) if (matrix[j][i] != INT32_MAX) matrix[j][i] -= min; } // int Max = 0; for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j < matrix[i].size() - 1; j++) if (matrix[i][j] == 0) { matrix[i][j] = INT32_MAX; int max = (getMin(matrix, i, check::Row) == INT32_MAX || getMin(matrix, j, check::Col) == INT32_MAX)? INT32_MAX: getMin(matrix, i, check::Row) + getMin(matrix, j, check::Col); if (max > Max) Max = max; matrix[i][j] = 0; } // Max vector<pair<int, int>> Maxs; for (int i = 0; i < matrix.size() - 1; i++) for (int j = 0; j < matrix[i].size() - 1; j++) if (matrix[i][j] == 0) { matrix[i][j] = INT32_MAX; int max = (getMin(matrix, i, check::Row) == INT32_MAX || getMin(matrix, j, check::Col) == INT32_MAX) ? INT32_MAX : getMin(matrix, i, check::Row) + getMin(matrix, j, check::Col); if (max == Max) Maxs.push_back(pair<int, int>(matrix[i][matrix.size() - 1], matrix[matrix.size() - 1][j])); matrix[i][j] = 0; } // std::cout << "Maxs - "; for (int i = 0; i < Maxs.size(); i++) std::cout << Maxs[i].first << " " << Maxs[i].second << "\t"; std::cout << endl; // showMatrix(matrix); std::cout << endl; // if (Maxs.size() == 0) { std::cout << "Bad road." << endl; return; } for (int i = 0; i < Maxs.size(); i++) { // result.push_back(Maxs[i]); // 1, if (matrix.size() - 1 == 1) { for (int i = 0; i < result.size(); i++) std::cout << "(" << result[i].first << ", " << result[i].second << ")\t"; std::cout << endl; std::cout << "Result: " << getResultSum() << endl; result.pop_back(); return; } // vector<vector<int>> temp(matrix); pair<int, int> elem(INT32_MAX, INT32_MAX), elem1(INT32_MAX, INT32_MAX); for (int j = 0; j < temp[temp.size() - 1].size() - 1; j++) { if (Maxs[i].first == temp[j][temp[j].size() - 1]) elem.first = j; if (Maxs[i].second == temp[j][temp[j].size() - 1]) elem1.first = j; } for (int j = 0; j < temp.size() - 1; j++) { if (Maxs[i].second == temp[temp.size() - 1][j]) elem.second = j; if (Maxs[i].first == temp[temp.size() - 1][j]) elem1.second = j; } for(int i = 0; i < temp.size() - 1; i++) for(int j = 0;j<temp.size() - 1; j++) if(i == elem1.first && j == elem1.second) temp[elem1.first][elem1.second] = INT32_MAX; for (int j = 0; j < temp[temp.size() - 1].size(); j++) temp[j].erase(temp[j].begin() + elem.second); temp.erase(temp.begin() + elem.first); // matrixProcedure(temp); // result.pop_back(); } }
結果
たとえば、マトリックスの場合：
0 5 8 10 0 0 3 6
5 0 2 0 0 0 0 1
8 2 0 4 5 6 0 7
10 0 4 0 12 9 7 0
0 0 5 12 0 9 0 12
0 0 6 9 9 0 8 0
3 0 0 7 0 8 0 2
6 1 7 0 12 0 2 0
結果は次のようになります。
結果
Little algorithm:
Maxs - 1 7 7 1
1 2 3 4 5 6 7 8
______________________________________________________
1 | inf 2 5 5 inf inf 0 3
2 | 3 inf 1 inf inf inf inf 0
3 | 5 0 inf 0 0 0 inf 5
4 | 5 inf 0 inf 5 1 3 inf
5 | inf inf 0 5 inf 0 inf 7
6 | inf inf 0 1 0 inf 2 inf
7 | 0 inf inf 3 inf 2 inf 0
8 | 4 0 6 inf 8 inf 1 inf
Maxs - 7 8
1 2 3 4 5 6 8
________________________________________________
2 | 0 inf 1 inf inf inf 0
3 | 2 0 inf 0 0 0 5
4 | 2 inf 0 inf 5 1 inf
5 | inf inf 0 5 inf 0 7
6 | inf inf 0 1 0 inf inf
7 | inf inf inf 3 inf 2 0
8 | 1 0 6 inf 8 inf inf
Maxs - 8 2
1 2 3 4 5 6
__________________________________________
2 | 0 inf 1 inf inf inf
3 | 2 0 inf 0 0 0
4 | 2 inf 0 inf 5 1
5 | inf inf 0 5 inf 0
6 | inf inf 0 1 0 inf
8 | inf 0 6 inf 8 inf
Maxs - 2 3
1 3 4 5 6
____________________________________
2 | inf 0 inf inf inf
3 | 0 inf 0 0 0
4 | 0 0 inf 5 1
5 | inf 0 5 inf 0
6 | inf 0 1 0 inf
Maxs - 4 1
1 4 5 6
______________________________
3 | inf 0 0 0
4 | 0 inf 5 1
5 | inf 5 inf 0
6 | inf 1 0 inf
Maxs - 5 6 6 4
4 5 6
________________________
3 | inf 0 0
5 | 4 inf 0
6 | 0 0 inf
Maxs - 3 5 6 4
4 5
__________________
3 | inf 0
6 | 0 inf
Maxs - 6 4
4
____________
6 | 0
(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (5, 6) (3, 5) (6, 4)
Result: 41
Maxs - 3 5
5
____________
3 | 0
(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (5, 6) (6, 4) (3, 5)
Result: 41
Maxs - 3 5 5 6
5 6
__________________
3 | 0 0
5 | inf 0
Maxs - 5 6
6
____________
5 | 0
(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (6, 4) (3, 5) (5, 6)
Result: 41
Maxs - 3 5
5
____________
3 | 0
(1, 7) (7, 8) (8, 2) (2, 3) (4, 1) (6, 4) (5, 6) (3, 5)
Result: 41
Maxs - 2 8
2 3 4 5 6 7 8
________________________________________________
1 | 0 3 3 inf inf inf 1
2 | inf 1 inf inf inf inf 0
3 | 0 inf 0 0 0 inf 5
4 | inf 0 inf 5 1 2 inf
5 | inf 0 5 inf 0 inf 7
6 | inf 0 1 0 inf 1 inf
8 | 0 6 inf 8 inf 0 inf
Maxs - 3 2
2 3 4 5 6 7
__________________________________________
1 | inf 0 0 inf inf inf
3 | 0 inf 0 0 0 inf
4 | inf 0 inf 5 1 1
5 | inf 0 5 inf 0 inf
6 | inf 0 1 0 inf 0
8 | inf 0 inf 2 inf inf
Maxs - 1 4 8 5
3 4 5 6 7
____________________________________
1 | inf 0 inf inf inf
4 | 0 inf 5 1 1
5 | 0 5 inf 0 inf
6 | 0 1 0 inf 0
8 | inf inf 0 inf inf
Maxs - 6 7 8 5
3 5 6 7
______________________________
4 | inf 4 0 inf
5 | 0 inf 0 inf
6 | 0 0 inf 0
8 | inf 0 inf inf
Maxs - 4 5 5 3 5 6 8 5
3 5 6
________________________
4 | inf 0 inf
5 | 0 inf 0
8 | inf 0 inf
3 6
__________________
5 | 0 0
8 | inf inf
Bad road
5 6
__________________
4 | 0 inf
8 | 0 inf
Bad road
3 5
__________________
4 | inf 0
8 | inf 0
Bad road
3 6
__________________
4 | inf inf
5 | 0 0
Bad road
Maxs - 4 6 5 6 6 3 6 7
3 6 7
________________________
4 | inf 0 inf
5 | inf 0 inf
6 | 0 inf 0
3 7
__________________
5 | inf inf
6 | 0 0
Bad road
3 7
__________________
4 | inf inf
6 | 0 0
Bad road
6 7
__________________
4 | 0 inf
5 | 0 inf
Bad road
3 6
__________________
4 | inf 0
5 | inf 0
Bad road
Maxs - 1 4
3 4 6 7
______________________________
1 | inf 0 inf inf
4 | 0 inf 1 1
5 | inf 5 0 inf
6 | 0 1 inf 0
Maxs - 4 6 5 6 6 3 6 7
3 6 7
________________________
4 | inf 0 inf
5 | inf 0 inf
6 | 0 inf 0
3 7
__________________
5 | inf inf
6 | 0 0
Bad road
3 7
__________________
4 | inf inf
6 | 0 0
Bad road
6 7
__________________
4 | 0 inf
5 | 0 inf
Bad road
3 6
__________________
4 | inf 0
5 | inf 0
Bad road
当然、ソリューションの完全な結論とすべてのブランチの結論をオフにすることができます。 私は多くの不必要な仕事をしたかもしれませんが、私の記事が何かに役立つことを願っています。
→ ソースファイル