快速哈密顿周期计算

Question

假设有一个有向图由以下指定顶点：

"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个顶点，我需要解决：

Answer 1

从图

哈密顿圈：http://figshare.com/articles/Hamiltonian_Cycle/1228800

如何找到你的图表汉密尔顿的周期在C＃：

第一个文件：

using System; 
using System.Collections.Generic; 

namespace Graph 
{ 
    partial class Program 
    { 
     static List<string> vertices; 
     static void Main(string[] args) 
     { 
      List<int>[] graph = GetGraph(); 
      List<int> HamiltonianCycle = Algorithm(graph); 
      string a = Translate(HamiltonianCycle); 
      Console.Write(a); 
      Console.ReadKey(); 
     } 
     static List<int>[] GetGraph() 
     { 
      List<string> list = new List<string>(){"A","B","C","D","E","F","G","H","I","J"}; 
      vertices = new List<string>(); 
      for(int a=0;a<10;++a) 
       for(int b=0;b<10;++b) 
        for(int c=0;c<10;++c) 
         for(int d=0;d<10;++d) 
      { 
       if(a==b || a== c || a==d || b == c || b == d|| c==d) 
        continue; 
       string vertex = list[a] + list[b] + list[c] + list[d]; 
       vertices.Add(vertex); 
      } 
      List<int>[] graph = new List<int>[vertices.Count]; 
      for(int i=0;i<graph.Length;++i) 
       graph[i] = new List<int>(); 
      foreach(string s1 in vertices) 
       foreach(string s2 in vertices) 
        if(s1 != s2) 
         if(s1[s1.Length-3] == s2[0] && s1[s1.Length-2] == s2[1] && s1[s1.Length-1] == s2[2]) 
      { 
       int v1 = vertices.IndexOf(s1); 
       int v2 = vertices.IndexOf(s2); 
       graph[v1].Add(v2); 
      } 
      return graph; 
     } 
     static string Translate(List<int> HamiltonianCycle) 
     { 
      string a = ""; 
      foreach(int b in HamiltonianCycle) 
       a += vertices[b] + " -> "; 
      return a; 
     } 
    } 
} 

第二个文件：

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace Graph 
{ 
    partial class Program 
    { 
     static List<int>[] graph, oppositeGraph; 
     static List<int> HamiltonianCycle; 
     static bool endOfAlgorithm; 
     static int level, v1, v2; 
     static List<int> Algorithm(List<int>[] graphArgument) 
     { 
      graph = SaveGraph(graphArgument); 
      HamiltonianCycle = new List<int>(); 
      endOfAlgorithm = false; 
      level = 0; 
      RemoveMultipleEdgesAndLoops(graph); //3.1 
      CreateOppositeGraph(graph); 
      bool HamiltonianCycleCantExist = AnalyzeGraph(new List<Edge>()); //6.1.a 
      ReverseGraph(); 
      if (!HamiltonianCycleCantExist) 
       FindHamiltonianCycle(GetNextVertex()); //5.3 
      HamiltonianCycle.Reverse(); 
      return HamiltonianCycle; 
     } 
     static void ReverseGraph() 
     { 
      graph = SaveGraph(oppositeGraph); 
      CreateOppositeGraph(graph); 
     } 
     static void FindHamiltonianCycle(int a) 
     { 
      if (!endOfAlgorithm) 
      { 
       ++level; 
       if (HamiltonianCycleFound()) 
        endOfAlgorithm = true; 
       SortList(a); //5.4 
       while (graph[a].Count > 0 && !endOfAlgorithm) 
       { 
        List<Edge> removedEdges = new List<Edge>(); 
        int chosenVertex = graph[a][0]; 
        graph[a].Remove(chosenVertex); 
        List<int>[] currentGraph = SaveGraph(graph); 
        #region 6.2 
        foreach (int b in graph[a]) 
        { 
         removedEdges.Add(new Edge(a, b)); 
         oppositeGraph[b].Remove(a); 
        } 
        graph[a].Clear(); 
        #endregion 
        graph[a].Add(chosenVertex); 
        v1 = a; 
        v2 = chosenVertex; 
        bool HamiltonianCycleCantExist = AnalyzeGraph(removedEdges); //6.1.b 
        if (!HamiltonianCycleCantExist) 
        { 
         FindHamiltonianCycle(GetNextVertex()); //5.5 
         RestoreGraphs(currentGraph); //6.4 
        } 
        else 
        { 
         foreach (Edge e in removedEdges) //6.3 
         { 
          graph[e.from].Add(e.to); 
          oppositeGraph[e.to].Add(e.from); 
         } 
         RemoveEdge(new Edge(a, chosenVertex), graph, oppositeGraph); 
        } 
       } 
       if (!endOfAlgorithm) 
       { 
        --level; 
        if (level == 0) 
         endOfAlgorithm = true; 
       } 
      } 
     } 
     static bool HamiltonianCycleFound() 
     { 
      foreach (List<int> list in graph) 
       if (list.Count != 1) 
        return false; 
      HamiltonianCycle = GetHamiltonianCycle(graph); 
      return true; 
     } 
     static List<int> GetHamiltonianCycle(List<int>[] graphArgument) 
     { 
      List<int> cycle = new List<int>() { 0 }; 
      while (true) 
      { 
       if (cycle.Count == graphArgument.Length && graphArgument[cycle.Last()].Contains(cycle[0])) 
        return cycle; 
       if (cycle.Contains(graphArgument[cycle.Last()][0])) 
        return new List<int>(); 
       else 
        cycle.Add(graphArgument[cycle.Last()][0]); 
      } 
     } 
     static int GetNextVertex() 
     { 
      List<int> correctOrder = GetCorrectOrder(graph); 
      foreach (int a in correctOrder) 
       if (graph[a].Count != 1) 
        return a; 
      return 0; 
     } 
     static bool AnalyzeGraph(List<Edge> removedEdges) 
     { 
      bool HamiltonianCycleCantExist = false; 
      int a; 
      do 
      { 
       a = removedEdges.Count; 
       HamiltonianCycleCantExist = RemoveUnnecessaryEdges(graph, oppositeGraph, removedEdges, false); 
       if (!HamiltonianCycleCantExist) 
        HamiltonianCycleCantExist = RemoveUnnecessaryEdges(oppositeGraph, graph, removedEdges, true); 
      } 
      while (a != removedEdges.Count && !HamiltonianCycleCantExist); 
      if (!HamiltonianCycleCantExist) 
       HamiltonianCycleCantExist = GraphIsDisconnected(graph); 
      return HamiltonianCycleCantExist; 
     } 
     static bool RemoveUnnecessaryEdges(List<int>[] graphArgument, List<int>[] oppositeGraphArgument, List<Edge> removedEdges, bool oppositeGraph) 
     { 
      bool HamiltonianCycleCantExist = false; 
      for (int a = 0; a < graphArgument.Length; ++a) 
      { 
       if (graphArgument[a].Count == 0 //4.1 
        || (graphArgument[a].Count == 1 && SearchForCycleAmongVerticesOfDegreeEqual1(graphArgument, a)) //4.2.1 
        || (graphArgument[a].Count > 1 && SearchForCycleAmongVerticesOfDegreeGreaterThan1(a, graphArgument, oppositeGraphArgument))) //4.2.2 
        return true; 
       List<Edge> edges = new List<Edge>(); 
       #region 3.2 
       if (graphArgument[a].Count == 1 && oppositeGraphArgument[graphArgument[a][0]].Count != 1) 
       { 
        foreach (int c in oppositeGraphArgument[graphArgument[a][0]]) 
         if (c != a) 
          if (!oppositeGraph) 
           edges.Add(new Edge(c, graphArgument[a][0])); 
          else 
           edges.Add(new Edge(graphArgument[a][0], c)); 
       } 
       #endregion 
       #region 3.4 
       if (graphArgument[a].Count == 1 && graphArgument[graphArgument[a][0]].Contains(a)) 
       { 
        if (!oppositeGraph) 
         edges.Add(new Edge(graphArgument[a][0], a)); 
        else 
         edges.Add(new Edge(a, graphArgument[a][0])); 
       } 
       #endregion 
       foreach (Edge edge in edges) 
       { 
        removedEdges.Add(edge); 
        if (!oppositeGraph) 
         RemoveEdge(edge, graphArgument, oppositeGraphArgument); 
        else 
         RemoveEdge(edge, oppositeGraphArgument, graphArgument); 
       } 
      } 
      return HamiltonianCycleCantExist; 
     } 
     static bool SearchForCycleAmongVerticesOfDegreeEqual1(List<int>[] graphArgument, int a) 
     { 
      if(!(a==v1 || a == v2)) 
       return false; 
      List<int> cycle = new List<int>() { a }; 
      while (true) 
       if (graphArgument[cycle.Last()].Count == 1 && cycle.Count < graphArgument.Length) 
        if (cycle.Contains(graphArgument[cycle.Last()][0])) 
         return true; 
        else 
         cycle.Add(graphArgument[cycle.Last()][0]); 
        else 
         return false; 
     } 
     static bool SearchForCycleAmongVerticesOfDegreeGreaterThan1(int a, List<int>[] graphArgument, List<int>[] oppossiteGraphArgument) 
     { 
      if (!ListsAreEqual(graphArgument[a], oppossiteGraphArgument[a], true)) 
       return false; 
      int b = 1; 
      for (int c = 0; c < graphArgument.Length && graphArgument.Length - c > graphArgument[a].Count - b; ++c) 
      { 
       if (c == a) 
        continue; 
       if (ListsAreEqual(graphArgument[c], graphArgument[a], false) && ListsAreEqual(graphArgument[c], oppossiteGraphArgument[c], true)) 
        ++b; 
       if (b == graphArgument[a].Count) 
        return true; 
      } 
      return false; 
     } 
     static bool ListsAreEqual(List<int> firstList, List<int> secondList, bool EqualCount) 
     { 
      if (EqualCount && firstList.Count != secondList.Count) 
       return false; 
      foreach (int a in firstList) 
       if (!secondList.Contains(a)) 
        return false; 
      return true; 
     } 
     static void SortList(int a) 
     { 
      List<int> correctOrder = GetCorrectOrder(oppositeGraph); 
      for (int b = 1; b < graph[a].Count; ++b) 
       for (int c = 0; c < graph[a].Count - 1; ++c) 
        if (correctOrder.IndexOf(graph[a][c]) > correctOrder.IndexOf(graph[a][c + 1])) 
      { 
       int n = graph[a][c]; 
       graph[a][c] = graph[a][c + 1]; 
       graph[a][c + 1] = n; 
      } 
     } 
     static List<int> GetCorrectOrder(List<int>[] graphArgument) //5.1 
     { 
      Dictionary<int, int> vertices = new Dictionary<int, int>(); 
      List<int> order = new List<int>(); 
      for (int a = 0; a < graphArgument.Length; ++a) 
       vertices.Add(a, graphArgument[a].Count); 
      IEnumerable<int> v = from pair in vertices orderby pair.Value ascending select pair.Key; 
      foreach (int a in v) 
       order.Add(a); 
      return order; 
     } 
     static void RemoveEdge(Edge e, List<int>[] graphArgument, List<int>[] oppositeGraphArgument) 
     { 
      graphArgument[e.from].Remove(e.to); 
      oppositeGraphArgument[e.to].Remove(e.from); 
     } 
     static void RemoveMultipleEdgesAndLoops(List<int>[] graphArgument) 
     { 
      for (int a = 0; a < graphArgument.Length; ++a) 
      { 
       graphArgument[a] = graphArgument[a].Distinct().ToList(); 
       graphArgument[a].Remove(a); 
      } 
     } 
     static void CreateOppositeGraph(List<int>[] graphArgument) 
     { 
      oppositeGraph = new List<int>[graphArgument.Length]; 
      for (int a = 0; a < graphArgument.Length; ++a) 
       oppositeGraph[a] = new List<int>(); 
      for (int a = 0; a < graphArgument.Length; ++a) 
       foreach (int b in graphArgument[a]) 
        oppositeGraph[b].Add(a); 
     } 
     static void RestoreGraphs(List<int>[] graphArgument) 
     { 
      graph = new List<int>[graphArgument.Length]; 
      for (int a = 0; a < graphArgument.Length; ++a) 
      { 
       graph[a] = new List<int>(); 
       graph[a].AddRange(graphArgument[a]); 
      } 
      CreateOppositeGraph(graph); 
     } 
     static List<int>[] SaveGraph(List<int>[] graphArgument) 
     { 
      List<int>[] savedGraph = new List<int>[graphArgument.Length]; 
      for (int a = 0; a < graphArgument.Length; ++a) 
      { 
       savedGraph[a] = new List<int>(); 
       savedGraph[a].AddRange(graphArgument[a]); 
      } 
      return savedGraph; 
     } 
     static bool GraphIsDisconnected(List<int>[] graphArgument) 
     { 
      Stack<int> stack = new Stack<int>(); 
      Color[] colors = new Color[graphArgument.Length]; 
      colors[0] = Color.Gray; 
      stack.Push(0); 
      while (stack.Count > 0) 
      { 
       int a = stack.Pop(); 
       foreach (int b in graphArgument[a]) 
       { 
        if (colors[b] == Color.White) 
        { 
         colors[b] = Color.Gray; 
         stack.Push(b); 
        } 
       } 
       colors[a] = Color.Black; 
      } 
      foreach (Color c in colors) 
       if (c != Color.Black) 
        return true; 
      return false; 
     } 
    } 
    class Edge 
    { 
     public int from, to; 
     public Edge(int f, int t) 
     { 
      from = f; 
      to = t; 
     } 
    } 
    enum Color { White, Gray, Black }; 
} 

我用我的算法的修改版本找到了Hamilonian循环：所做个修改是：

• 算法搜索在相反的图表
• 算法测试了图形断开
• 算法没有测试“唯一邻居”规则
• 算法搜寻周期不在哈密顿，仅从创建当前访问边的顶点开始 - 仅在函数中搜索ForCycleAmongVerticesOfDegreeEqual1

Answer 2

好，计算汉密尔顿周期实际上是NP完全问题。所以没有快速（即多项式时间）算法。

你可以在这里找到更多的信息：http://mathworld.wolfram.com/HamiltonianCycle.html

一些蒙特卡洛算法可能会在这里工作（也许不会给你总是正确的答案） - 所以我想寻找在那里，但不要指望奇迹。这是仍然 NP完全问题。