假設有一個有向圖由以下指定頂點:快速哈密頓週期計算
"ABC", "ABD", "ACB", "ACD", "ADB", "ADC", "BAC", "BAD",
"BCA", "BCD", "BDA", "BDC", "CAB", "CAD", "CBA", "CBD",
"CDA", "CDB", "DAB", "DAC", "DBA", "DBC", "DCA", "DCB"
這些都是在4個不同的字母的3個字母的排列。 (total = 4*3*2=24
) 頂點的名稱也描述了它們之間的邊緣。任意兩個頂點被連接到彼此,如果源的最後兩個字符等於目的地這樣的頭兩個字符作爲
甲BC - >BC d
或
d CB - >CB A
該圖與De Burjin's或Kautz's非常相似,但不相同。它是強有力的連接,我知道它有哈密爾頓循環。
爲了解決這個問題,我不是在算法方面的專家,我只是經歷了最新的增強圖形庫,發現hawick_unique_circuits()函數枚舉所有周期,這是我的例子代碼:
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/hawick_circuits.hpp>
#include "combination.hpp" // from http://howardhinnant.github.io/combinations.html
using namespace std;
using namespace boost;
typedef boost::adjacency_list<vecS, vecS, directedS, no_property, property<edge_weight_t, uint32_t> > TGraph;
TGraph m_Graph;
vector<string> m_StrVertexList;
void CreateStringVertexList(vector<string>& vl, uint32_t n, uint32_t k)
{
vl.clear();
if ((k > 0) && (n > k))
{
string code = "A";
while (--n)
{
code += code.back() + 1;
}
// for_each_permutation from Howard Hinnant
// http://howardhinnant.github.io/combinations.html
for_each_permutation(code.begin(), code.begin() + k, code.end(),
[&](string::iterator first, string::iterator last)->bool{ vl.push_back(string(first, last)); return(false); });
}
}
void AddEdgesFromStringVertex(TGraph& g, const vector<string>& vl)
{
uint32_t connection_len = vl.begin()->size() - 1;
g.clear();
for (uint32_t f = 0; f < vl.size(); f++)
for (uint32_t t = 0; t < vl.size(); t++)
{
if ((f != t) &&
(vl[f].substr(1, connection_len) == vl[t].substr(0, connection_len)))
{
add_edge(f, t, 1, g);
}
}
}
class hawick_visitor
{
public:
void cycle(const vector<TGraph::vertex_descriptor>& circuit, const TGraph& graph) const
{
if (circuit.size() == m_StrVertexList.size())
{
for (auto ii = circuit.begin(); ii != circuit.end(); ++ii)
{
cout << m_StrVertexList[*ii] << " -> ";
}
cout << endl;
}
}
};
void Circuits(const TGraph& g)
{
hawick_unique_circuits(g, hawick_visitor());
cout << "- end of hawick_unique_circuits() -" << endl;
}
void main(void)
{
//CreateStringVertexList(m_StrVertexList, 10, 4);
CreateStringVertexList(m_StrVertexList, 4, 3);
AddEdgesFromStringVertex(m_Graph, m_StrVertexList);
Circuits(m_Graph);
}
hawick_visitor類只檢查發現的循環是否與Graph的頂點相同。如果有的話,那意味着我們找到了我們需要的哈密爾頓循環之一。
它完全適用於24個頂點是3字符由4個獨特的字符選擇,這裏是輸出一個:
ABC -> BCA -> CAD -> ADB -> DBC -> BCD -> CDA -> DAC ->
ACB -> CBD -> BDC -> DCB -> CBA -> BAC -> ACD -> CDB ->
DBA -> BAD -> ADC -> DCA -> CAB -> ABD -> BDA -> DAB -> ABC
但是,當我試圖解決類似圖4炭選自已命名的5040個頂點10個唯一字符,這個函數永遠不會返回。應該有一個比hawick_unique_circuits()更好的算法來做到這一點。因爲我知道人們對10,000個頂點的計算不到一分鐘,但我不知道如何計算。任何想法高度讚賞。
這裏是有圖有5040個頂點,我需要解決:
這太神奇了!我確認了輸出。我要研究你的算法。 – 2014-11-09 08:33:46