7

ドアを 2 回使用せずに部屋のセットを通るルートを見つける必要がある、古典的な「ケーニヒスベルクの 7 つの橋」パズルの変形であるパズルがいくつかあります。

これは、解決策のない例です。 テスト

...そして、ここでわかるように、解決策 があるわずかに変更されたパズルです。偽

この種の問題を解決するためのプログラムによるアプローチに興味があります。部屋とドアの特定の構成に解決策がないことを判断する方法はいくつかありますが、解決するために訪問するドアのリストを計算することに興味があります。パズル。問題を表示する 1 つの方法は、その構成をグラフに変換し、ハミルトニアンを解くことです。ただし、この種の問題は、「Uターン」が禁止されているという制約があるため、洗練されていないロジックに取り組む必要があります。

問題を示すために、数分で解決策をハックしました。これは、「部屋」をグループに入れる力ずくのソリューションであり、同じ部屋の 1 つの「ドア」から別の「ドア」に移動できないという不変条件が追加されています (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頂点です
  • 各ドアは双方向エッジです
  • どの部屋にも、他の部屋または外側に通じる複数のドアを設けることができます

次に、各エッジを 1 回だけたどります。

データ構造を隣接リストに変換するには、次のようにします。

  • 各ドアのすべてのラベルを配列に収集します
  • 各ドア ラベルについて、2 つのコネクティング ルームを見つけます。
  • 2 つの部屋を隣接リストのエントリとして追加します。

このようなものは、すでに持っているデータ構造から隣接リストを構築します。

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 部屋間を移動するために使用できるエッジのリストを示します。2 つの部屋を接続するドアごとに 1 つのエッジがあります。エッジをトラバースする (ドアを通過する) 場合は、再度トラバース (ドアを通過) しないように、エッジを削除 (またはマーク) する必要があります。

于 2016-05-18T03:42:22.890 に答える