旅行门票问题

5 回答

• 1

  如果您可以多次访问节点（城市），则为eulerian path problem .

  Here是解决它的两种简单算法，具体取决于您拥有的图形类型 . 您有第3页here的递归实现 .

  回复于 2024-04-29T23:47:29+08:00
• 0

  这不仅仅是一个双重链接列表吗？将每个项目添加到列表中，并根据需要链接每个项目;当你完成后，你将有两个带有未连接链接的条目（一个没有连接到它的'“from”节点，一个没有连接到它的'“to”节点 . 这些是它们的起点和终点 . 通过从缺少“from”链接的条目开始，并按照从一个条目到下一个条目的链接，您可以按顺序读取它们 .

  回复于 2024-04-29T23:47:29+08:00
• 1

  你得到的是有向图，你希望在其中找到Eulerian Path . 链接的文章描述了找到一个的算法，基本上是：

  • 找一个路线少于外出的城市（如果没有，从任何地方开始）

  • 乘坐机票（边缘），在那里赢得了_1678060吨;除非不存在此类票证，否则使用该票证 .

  • 删除票证（边缘）并重复

  您最终应该使用所有门票，并在最终目的地 .

  回复于 2024-04-29T23:47:29+08:00
• 8

  • 从票证中创建有向图 .

  • 查找具有indegree 0的节点

  • 通过图形边缘迭代所有节点以创建结果

  更新：通过原始帖子中添加的信息，此解决方案无法解决正确的问题 . 而是看看IVLad的response .

  回复于 2024-04-29T23:47:29+08:00
• 1

  以下是javascript实现的示例 .

  var un  =
  [
   { from:'c',to:'d'},
   { from:'a',to:'b'},
   { from:'b',to:'c'},
   { from:'z',to:'a'},
   { from:'d',to:'m'},
  ]
  
  function buildTable( un ){
  return un.reduce(function(previousValue, currentValue, currentIndex ){
  
  //build the table.
      previousValue.from[currentValue['from']] = currentValue;
      previousValue.to[currentValue['to']] = currentValue;
  
  //to find start and end.    
      if( !previousValue.from[currentValue['to']] )  previousValue.from[currentValue['to']]= false;
      if(!previousValue.to[currentValue['from']])  previousValue.to[currentValue['from']]= false;
  
      return previousValue;
  
  },{to:{},from:{}} );
  
  
  }
  
  function getStart(nodes){
  //find start node indx.
      for(var i  in nodes)
      if( !nodes[i] )return i;
  }
  
  
  function print(start,nodes ){
  
  
  var sorted = [];
  //while detecting false from buildTable structure.
      while(start){
          var  node = nodes[start];
          sorted.push(node)
          start = node['to'];
  //console.log(start)
      }
  
  return sorted;
  }
  
  var sorted = buildTable(un);
  console.log(print(getStart(sorted.to),sorted.from));
  

  回复于 2024-04-29T23:47:29+08:00