"visit each door once" 问题的规范算法

Question

有许多谜题是经典“柯尼斯堡的 7 座桥”谜题的变体，在这些谜题中，您必须找到一条穿过一组房间的路线，而无需两次使用门。

这是一个没有解决方案的例子。

... 是一个稍微修改过的谜题，确实有一个解决方案，正如您在此处看到的那样。

我对解决这类问题的编程方法很感兴趣，虽然有很多方法可以确定房间和门的特定配置没有解决方案，但我对计算门列表很感兴趣访问以解决难题。查看问题的一种方法是将其配置转换为图形并求解哈密顿量。然而，由于 "U-Turns" 被禁止的约束，这种问题需要解决不优雅的逻辑。

我在几分钟内破解了一个解决方案来说明问题。这是一种将 "rooms" 分组的蛮力解决方案，添加的不变量是您不能在同一个房间中从一个 "door" 移动到另一个 "door" （因为这需要做掉头）。

我觉得必须有一个更好的抽象来表示这个问题，而不是诉诸以下 "tricks":

当路径刚从那个房间出来时，有额外的逻辑来移除同一个房间中的门作为有效选择。
生成与输入房间配置不同构的图形。
过滤所有不满足掉头约束的配置。（#1 的变体）

是否有解决此类问题的现有文献体系？如果有，他们的结论是什么？房间问题是否与最著名的图算法所采用的方法根本不一致，以至于需要这种特殊逻辑？如果有更好的解决方案而不是转换为图表，我也很想听听。

这是有效的现有代码，组代表第一个问题，被注释掉的组代表后一个问题。：

// I renamed "groups" to rooms to make the code more clear.
var rooms = {
    1: ['A','B','C','D'],
    //1: ['A','B','C','D','P'],
    2: ['E', 'D', 'F', 'G'],
    3: ['F','I','J','H'],
    //3: ['F','I','P','J', 'H'],
    4: ['I', 'M', 'N', 'O'],
    5: ['C','J','M','L','K'],
    OUTER: ['A', 'B', 'E', 'G', 'H', 'O', 'N', 'L', 'K']
}

class Graph {
    constructor(rooms) {
        // This is a map of a door letter to the rooms (rooms) that it belongs to.
        this.roomKey = {};
        // The total number of doors
        this.totalNodes = 0;
        this.rooms = rooms;
        // This is only used to produce the number of rooms, but remains in case
        // I need to adapt the algorithm for the classical approach.
        this.vertices = {};
        for (var key in rooms) {
            this.addRoom(key, rooms[key]);
        }
    }

    addRoom(roomName, elements) {
        for (var from of elements) {
            if (!this.roomKey[from]) {
                // initialize
                this.roomKey[from] = [roomName]
            } else {
                this.roomKey[from].push(roomName)
            }
            for (var to of elements) {
                // it doesn't make sense to add a vertex to yourself
                if (from === to) continue
                // otherwise add the vertex
                this.addDoor(from, to)
            }
        }
    }

    addDoor(name, edge) {
        // initialize if empty
        if (!this.vertices[name]) {
            this.vertices[name] = []
            this.totalNodes++
        }

        if (this.vertices[name].indexOf(edge) != -1) {
            console.log(`${name} already has this edge: ${edge}`)
        } else {
            this.vertices[name] = this.vertices[name].concat(edge)
        }
    }

    hamiltonian(current, prevRoom, used) {
        // Find the rooms that this connects to
        var kpossible = this.roomKey[current]

        // Find the rooms that connect to this door, but filter those that are
        // in the room we just came from, this is the hacky part.
        var possibleRoom = kpossible.find((room) => room !== prevRoom)
        // Produce all possible rooms, but if we've already been to a room, remove it.
        var possibleDoors = this.rooms[possibleRoom].filter((elt) => used.indexOf(elt) == -1)

        if (used.length == this.totalNodes) {
            console.log("success!", used)
            return;
        }

        // No more possible rooms, this path is no good.
        if (!possibleDoors || possibleDoors.length === 0)
            return;

        for(var door of possibleDoors) {
            this.hamiltonian(door, possibleRoom, used.concat(door))
        }
    }
}

门的标签如下：

Answer 1

如你所说，门只能使用一次。

我会将数据表示为具有以下属性的邻接表：

每个房间都是一个顶点
Outside是一个顶点
每扇门都是双向边
任何房间都可以有多扇门通往任何其他房间或通往外面

那么你将只跟随每条边一次。

为了将您的数据结构转换为邻接表，我将执行以下操作：

将每扇门的所有标签收集到一个数组中
对于每个门标签，找到两个相连的房间
将这两个房间添加为邻接列表中的条目

这样的事情将从您已有的数据结构构建邻接表：

var groups = {
    1: ['A','B','C','D','P'],
    2: ['E', 'D', 'F', 'G'],
    3: ['F','I','P','J', 'H'],
    4: ['I', 'M', 'N', 'O'],
    5: ['C','J','M','L','K'],
    OUTER: ['A', 'B', 'E', 'G', 'H', 'O', 'N', 'L', 'K']
}

var edges = [];
var adjacency_list = [];

// collect all the doors
for (var room in groups) {
  doors = groups[room];
  for (var door of doors) {
    if (edges.indexOf(door) < 0) {
      edges.push(door); // mark off this door
    }
  }
}

// find the connections between the rooms (build the adjacency matrix)
for (var door of edges) {
  rooms = [];

  // find the two rooms that this door connects
  for (var room in groups) {
    doors = groups[room];
    if (doors.indexOf(door) > 0) {
      rooms.push(room);
    }
  }

  // add these as an edge in our adjacency list
  if (rooms.length == 2) {
    adjacency_list.push(rooms);
  }
  else {
    //TODO: raise an error as the rooms aren't connected properly
  }
}

现在，adjacency_list 是一个边列表，您可以使用它们在房间之间穿行。每扇门将有一个边缘连接两个房间。如果你穿过一条边（穿过一扇门），那么它必须被移除（或标记），这样你就不会再次穿过它（穿过门）。

"visit each door once" 问题的规范算法

Canonical algorithm for "visit each door once" problems

javascript

graph-theory

hamiltonian-cycle