典型算法为"每次访问一次门"的问题

Question

有许多谜题是经典的"7 Bridges of Konigsberg"拼图的变体,你必须在没有两次使用门的情况下找到通过一组房间的路线.

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

...... 正如你在这里看到的那样,它是一个有一点解决方案的解决方案.

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

我在几分钟内修复了一个解决方案以显示问题.这是一个蛮力的解决方案,将"房间"分组,增加的不变量,你不能从一个"门"移动到同一个房间的另一个"门"(这将需要做一个掉头).

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

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

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

3. 过滤所有不满足掉头约束的配置.(#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 是可用于在房间之间遍历的边列表。每扇门将有一个边缘连接两个房间。如果你穿过一条边（穿过门），那么它必须被移除（或标记），这样你就不会再次穿过它（穿过门）。