旅行机票问题

Question

您将获得一堆旅行票，这些票可以让您通过途中的几个站点从A点到达B点。所有的车票都是无序的，您不知道旅程从哪里开始，也不知道它在哪里结束。请对车票进行排序，以完成您的旅程。

tickets = [
  {from: "Barcelona", to: "New York"}
  {from: "Barcelona", to: "Gerona"},
  {from: "Madrid",    to: "Barcelona"},
  {from: "Gerona",    to: "Barcelona"}
]

我认为正确的顺序应该是这样的:

tickets = [
  {from: "Madrid",    to: "Barcelona"},
  {from: "Barcelona", to: "Gerona"},
  {from: "Gerona",    to: "Barcelona"},
  {from: "Barcelona", to: "New York"}
]

因为没有去马德里的车票，也没有从纽约出发的车票。

对于这个任务，最好的算法是什么？

语言是JavaScript，但是通用的解决方案也足够好。

更新: 我更改了示例数据，以免与单程飞行问题混淆。

- NVI

---

你必须经过所有城市吗？你必须使用所有的机票吗？ - IVlad

是的。同时，所有的票务必须被使用。 - NVI

你是一个手头有太多机票、有点懒惰的旅行代理吗？;-) - kasperjj

可能最简单的方法是按航班起飞时间对机票进行排序。虽然这样做有点作弊 ;) - Dirk Vollmar

我已投票支持重新开放。这不是同一个问题。 - Aryabhatta

Answer 1

如果您可以多次访问一个节点（城市），那么这就是欧拉路径问题。 这里有两种简单的算法来解决它，取决于您拥有的图形类型。您可以在第3页这里找到递归实现。

- IVlad

Answer 2

这不就是一个双向链表吗？将每个项目添加到列表中，并适当地链接每个项目；完成后，您将拥有两个具有未连接链接的条目（一个没有任何连接到其“from”节点的连接，另一个没有连接到其“to”节点的连接）。这些是链的起点和终点，并且您可以通过从缺少“from”链接的条目开始，并按顺序跟随一个条目到下一个条目来读取它们。

- Eight-Bit Guru

---

只有在保证每个城市最多被访问一次的情况下才成立。 - Chowlett

真 - 我的建议是基于给定的示例，而不是适应进一步未指定的条件。 - Eight-Bit Guru

Answer 3

1. 从您的票据中创建一个有向图。
2. 找到入度为0的节点
3. 通过图边遍历所有节点以创建您的结果

更新：根据原帖中添加的信息，此解决方案无法解决正确的问题。请查看IVLad的response。

- kasperjj

---

一些问题：你是否考虑过拓扑排序？如果是的话，你如何使用所有的边？如果不是，你能详细说明第三个问题吗？你是如何迭代的？ - IVlad

这是他们那些花哨的技术术语，意思是“在from列表中查找未出现在to列表中的城市，然后开始跟踪您的路线”吗？;-) - scunliffe

@IVlad 我可能从帖子中的示例数据中做出了太多的假设，但如果有多个票据共享相同的源节点，则需要进行拓扑排序，这将使我的第三步骤变得不那么明显 :-) - kasperjj

@scunliffe 差不多了... 我可能会使用哈希表构建有向图，这样可以得到一个O(n)的解决方案，而不是嵌套循环的O(n^2)。 - kasperjj

Answer 4

你手头有一个有向图，希望在其中找到欧拉路径。链接的文章描述了找到欧拉路径的算法，基本上是：

1. 找到入度小于出度的城市（如果没有，则从任意城市开始）
2. 选择一张不会使图断开的票（边）进行旅行；除非不存在这样的票，否则使用该票。
3. 删除该票（边）并重复

最终你应该会使用所有的票，并到达目的地。

- Chowlett

Answer 5

以下是 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));

- vimalpt

Answer 6

1. 起始地点没有机票。因此，首先我会通过比较“从”条目和“到”条目来找到起始地点。这样我们就得到了第一张机票。
2. 将第一张机票添加到新列表中（也称为sortedList）
3. 在while循环中，将ticketList中的机票添加到sortedList最后一张机票的“to”处，直到ticketList和sortedList长度相同

以下是用Dart编写类似任务的代码：

  Map<String, String> ticket1 = {'from': 'st_p','to':'msc'}; //1
  Map<String, String> ticket2 = {'from': 'izh','to':'sam'}; //3
  Map<String, String> ticket3 = {'from': 'kzn','to':'sch'}; //5
  Map<String, String> ticket4 = {'from': 'sam','to':'kzn'}; //4
  Map<String, String> ticket5 = {'from': 'msc','to':'izh'}; //2
  
  List<Map<String, String>> tickets = [ticket1,ticket2,ticket3,
                                       ticket4,ticket5];
  
  List<String> citiesFrom = [];
  List<String> citiesTo = [];
  
  for (var ticket in tickets) {
    citiesFrom.add(ticket['from']!);
    citiesTo.add(ticket['to']!);
  }
  
  String beginDestination = citiesFrom.firstWhere(
    (element) => !citiesTo.contains(element));
  
  List<Map> sortedTickets = [];
  
  sortedTickets.add(tickets.firstWhere(
    (element) => element['from']==beginDestination));
  
  while(sortedTickets.length != tickets.length) {
    sortedTickets.add(
      tickets.firstWhere(
        (element) => element['from']==sortedTickets.last['to'])
    );
  }
  
  print(sortedTickets);

- Gerri

Answer 7

    function fullPath(path) {
    let startingPoints = [];
    let endingPoints = [];
    let result = [];

    for (let i = 0; i < path.length; i++) {
        startingPoints.push(path[i].from);
        endingPoints.push(path[i].to);
    }

    for (let i = 0; i < path.length; i++) {
        if (!endingPoints.includes(path[i].from)) {
            result.push(path[i].from);
            break;
        }
    }

    for (let i = 0; i < path.length; i++) {
        if (startingPoints.includes(result[i])) {
            let indexOfPoint = startingPoints.indexOf(result[i]);
            result.push(endingPoints[indexOfPoint]);
        }
    }
    return result;

}

- Mahmoud Alsalmo