7

有许多谜题是经典的“柯尼斯堡 7 桥”谜题的变体，您必须在不使用两次门的情况下找到穿过一组房间的路线。

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

...并且是一个稍微修改的难题，确实有解决方案，如您在此处看到的。 伪造的

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

我在几分钟内破解了一个解决方案来显示问题。这是一种蛮力解决方案，将“房间”分组，并增加了不变量，即您不能在同一个房间中从一个“门”移动到另一个“门”（因为这需要进行 U 形转弯）。

我觉得必须有一个更好的抽象来表示这个问题，而不是诉诸以下“技巧”：

  1. 当路径刚刚来自那个房间时，有额外的逻辑来移除同一个房间中的门作为有效选择。

  2. 生成与输入房间配置不同的图形。

  3. 过滤所有不满足 U 形转弯约束的配置。（#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))
        }
    }
}

门的标签如下： 贴有标签的门

4

1 回答 1

5

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

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

  • 每个房间都是一个顶点
  • 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 是可用于在房间之间遍历的边列表。每扇门将有一个边缘连接两个房间。如果你穿过一条边（穿过一扇门），那么它必须被移除（或标记），这样你就不会再次穿过它（穿过门）。

于 2016-05-18T03:42:22.890 回答