那些遇到过的问题

在网格中找到随机哈密顿路径的算法？

Fej*_*uto 8 algorithm hamiltonian-cycle graph-algorithm

我正在寻找一种有效的算法,能够在双向N*M网格中找到尽可能随机的哈密​​顿路径.

有谁知道我在哪里可以找到,或者如何构建这样的算法？

我已经找到了一种有效的方法(见下图).这里的最终结果是哈密顿循环.删除随机边缘将使其成为哈密尔顿路径.该算法是有效的,但不提供足够的随机性.这种方法总是让路径的起点和终点彼此相邻,而我希望将它们放在随机位置. 空间填充曲线http://img593.imageshack.us/img593/8060/sfc.png 图片取自http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= PDF格式

Fab*_*LIN 6

首先，从pdf文件显示在图像上的算法不是汉密尔顿路径问题的解决方案，而是迷宫生成的解决方案，因为最终路径具有多个分支。

要查找迷宫生成的算法，请参阅：https : //en.wikipedia.org/wiki/Maze_generation_algorithm

现在，这是一个在N * M 2D网格上生成哈密顿路径的简单算法：

1）假设一个N * M网格为（例如4 * 5）：

O-O-O-O-O
| | | | |
O-O-O-O-O
| | | | |
O-O-O-O-O
| | | | |
O-O-O-O-O
Run Code Online (Sandbox Code Playgroud)

2）让我们从东/北角开始，并创建一个向西和向东的简单之字形：

O-O-O-O-O
|
O-O-O-O-O
        |
O-O-O-O-O
|        
O-O-O-O-O
Run Code Online (Sandbox Code Playgroud)

现在我们有了哈密顿路径。

3）让我们搜索两个胶合的边缘，其中一个胶合的边缘彼此相对。它们是循环的开始和结束：

O-O-O-O-O
|        
O-OXO-O-O
        |
O-OXO-O-O
|        
O-O-O-O-O
Run Code Online (Sandbox Code Playgroud)

4）确保回路内至少有一条边缘粘贴到回路外的边缘，否则，请转到步骤3：

O-O-O-O-O
|        
O-OXO-O-O
        |
O-OXOxO-O
|        
O-O-OxO-O
Run Code Online (Sandbox Code Playgroud)

5）简化循环：

O-O-O-O-O
|        
O-O O-O-O
  | |   |
O-O OxO-O
|        
O-O-OxO-O
Run Code Online (Sandbox Code Playgroud)

6）用另外两个粘合的边缘重新连接环：

O-O-O-O-O
|        
O-O O-O-O
  | |   |
O-O O O-O
|   | |  
O-O-O O-O
Run Code Online (Sandbox Code Playgroud)

7）如果哈密顿路径不够随机，请转到步骤3。

只有起点和终点不会移动。要随机化结束或开始，可以用另一种算法替换初始的锯齿形：

  1. 选择四个角之一
  2. 搜索所有未访问的邻居
  3. 如果没有邻居，则填满地图，否则转到步骤4
  4. 仅保留在一侧，左侧或右侧有空白或已访问单元的邻居（换句话说，沿着未访问区域边界行走的邻居）
  5. 选择其中一个邻居，访问它并转到步骤2

结果可能如下所示：

O-O-O-O-O
        |
O-O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O
Run Code Online (Sandbox Code Playgroud)

使用此算法，起点仍在拐角处，但终点可以在任何地方。要随机化起点和终点，您可以应用一种算法，您可以在起点或终点进行任意多次迭代。让我们开始吧：

1）找到起点：

|
v
OOOOO
        |
O
| | |
哦哦
| | | |
OOO OO

2）找到一个未直接与起点连接的邻居（您将始终在2D网格中找到一个）：

  OOOOO
          |
-> OOOO O
  | | |
  哦哦
  | | | |
  OOO OO

3）从头开始（分别从头到尾）查找到达的位置：

OOOOO
        |
OXO-OO O
| | |
哦哦
| | | |
OOO OO

4）剪切此链接，并在此点和起点之间创建一个链接：

OOOOO
| |
O OOO O
| | |
哦哦
| | | |
OOO OO

开始已经移动了两个单元。起点和终点与棋盘一样，它们只能在具有相同颜色的箱子上移动。

现在，您的路径已完全随机化。

这是Python中的整个算法。您可以在此处运行它：http : //www.compileonline.com/execute_python3_online.php

结果存储在数组（self.gameGrid）中，并记录两次（带有箭头以及带有节点和线条的数组）。前两个粘合的边缘称为置换，第二个称为交点。

#!/usr/local/bin/python3

import random

class CellRoom:

  def generateGame(self):
    ## Constants
    self.UNDEFINED = 0
    self.FROM_NOWHERE = 1
    self.FROM_NORTH = 2
    self.FROM_EAST = 3
    self.FROM_SOUTH = 4
    self.FROM_WEST = 5

    self.LEFT = 0
    self.RIGHT = 1

    self.GAME_WIDTH = random.randint(3, 20)
    self.GAME_HEIGHT = random.randint(3, 20)

    self.initGame()

    for i in range(100):
      self.permutate()

    ##self.logGameWithPath()
    ##self.logGameWithArrow()
    for i in range(50):
      self.start = self.moveExtremity(self.start)
    self.logGameWithPath()
    self.logGameWithArrow()
    self.verifyGame()

  ## Print the map of the game on the standard output.
  ## Do not show the orientation.
  def logGameWithPath(self):
    print ('game width: ' + str(self.GAME_WIDTH))
    print ('game height: ' + str(self.GAME_HEIGHT))
    print ('Start [x=' + str(self.start[1]) + ', y=' + str(self.start[0]) + ']')

    gameText = ''

    for i in range(len(self.gameGrid)):
      for j in range(len(self.gameGrid[i])):
        if (self.gameGrid[i][j] == self.FROM_NORTH) or ((i > 0) and (self.gameGrid[i - 1][j] == self.FROM_SOUTH)):
          gameText = gameText + ' |'
        else:
          gameText = gameText + '  '
      gameText = gameText + ' \n'
      for j in range(len(self.gameGrid[i])):
        if (self.gameGrid[i][j] == self.FROM_WEST) or ((j > 0) and (self.gameGrid[i][j - 1] == self.FROM_EAST)):
          gameText = gameText + '-O'
        else:
          gameText = gameText + ' O'
      gameText = gameText + ' \n'

    for j in range(len(self.gameGrid[i])):
      gameText = gameText + '  '
    gameText = gameText + ' \n'

    print (gameText)

  ## Print the map of the game on the standard output.
  ## It shows the orientation.
  def logGameWithArrow(self):
    gameText = ''

    for gameLine in self.gameGrid:
      for j in gameLine:
        if j == self.FROM_NOWHERE:
          gameText = gameText + 'X'
        elif j == self.FROM_NORTH:
          gameText = gameText + 'V'
        elif j == self.FROM_EAST:
          gameText = gameText + '('
        elif j == self.FROM_SOUTH:
          gameText = gameText + '^'
        elif j == self.FROM_WEST:
          gameText = gameText + ')'
      gameText = gameText + '\n'

    print (gameText)

  ## Generate a new map with an extremity (ex. start point) at another place.
  ## It receives and returns a valid map.
  def moveExtremity(self, extremity):
    ## Search the points.
    possibleNewOrigins = []
    if ((extremity[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[extremity[0] + 1][extremity[1]] != self.FROM_NORTH)):
      possibleNewOrigins.append(self.FROM_NORTH)
      besidePoint = [extremity[0] + 1, extremity[1]]
    elif ((extremity[1] > 0) and (self.gameGrid[extremity[0]][extremity[1] - 1] != self.FROM_EAST)):
      possibleNewOrigins.append(self.FROM_EAST)
      besidePoint = [extremity[0], extremity[1] - 1]
    elif ((extremity[0] > 0) and (self.gameGrid[extremity[0] - 1][extremity[1]] != self.FROM_SOUTH)):
      possibleNewOrigins.append(self.FROM_SOUTH)
      besidePoint = [extremity[0] - 1, extremity[1]]
    elif ((extremity[1] < self.GAME_WIDTH - 1) and (self.gameGrid[extremity[0]][extremity[1] + 1] != self.FROM_WEST)):
      possibleNewOrigins.append(self.FROM_WEST)
      besidePoint = [extremity[0], extremity[1] + 1]

    besidePointNewOrigin = possibleNewOrigins[random.randint(0, len(possibleNewOrigins) - 1)]

    if besidePointNewOrigin == self.FROM_NORTH:
      besidePoint = [extremity[0] + 1, extremity[1]]
    elif besidePointNewOrigin == self.FROM_EAST:
      besidePoint = [extremity[0], extremity[1] - 1]
    elif besidePointNewOrigin == self.FROM_SOUTH:
      besidePoint = [extremity[0] - 1, extremity[1]]
    elif besidePointNewOrigin == self.FROM_WEST:
      besidePoint = [extremity[0], extremity[1] + 1]

    ##print ('New start: [' + str(extremity[0]) + ', ' + str(extremity[1]) + ']')
    ##print ('besidePoint: [' + str(besidePoint[0]) + ', ' + str(besidePoint[1]) + ']')

    ## Search the new extremity
    if self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_NORTH:
      newExtremity = [besidePoint[0] - 1, besidePoint[1]]
    elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_EAST:
      newExtremity = [besidePoint[0], besidePoint[1] + 1]
    elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_SOUTH:
      newExtremity = [besidePoint[0] + 1, besidePoint[1]]
    elif self.gameGrid[besidePoint[0]][besidePoint[1]] == self.FROM_WEST:
      newExtremity = [besidePoint[0], besidePoint[1] - 1]

    ## Do the move.
    self.reversePath(extremity, newExtremity)

    self.gameGrid[besidePoint[0]][besidePoint[1]] = besidePointNewOrigin
    self.gameGrid[newExtremity[0]][newExtremity[1]] = self.FROM_NOWHERE
    ##print ('extremity: [' + str(newExtremity[0]) + ', ' + str(newExtremity[1]) + ']')

    return newExtremity

  ## Rewrite the path on the map as the end was the start and vice versa.
  ## The end becomes undefined.
  def reversePath(self, start, end):
    currentPoint = start
    ##print ('start: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
    ##print ('end: [' + str(end[0]) + ', ' + str(end[1]) + ']')
    while (currentPoint[0] != end[0]) or (currentPoint[1] != end[1]):
      ##print ('currentPoint: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
      ## We search the next point, not the point we just have reversed
      if (currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.FROM_NORTH) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_SOUTH):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_SOUTH
        currentPoint[0] = currentPoint[0] + 1
      elif (currentPoint[1] > 0) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.FROM_EAST) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_WEST):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_WEST
        currentPoint[1] = currentPoint[1] - 1
      elif (currentPoint[0] > 0) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.FROM_SOUTH) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_NORTH):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_NORTH
        currentPoint[0] = currentPoint[0] - 1
      elif (currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.FROM_WEST) and (self.gameGrid[currentPoint[0]][currentPoint[1]] != self.FROM_EAST):
        self.gameGrid[currentPoint[0]][currentPoint[1]] = self.FROM_EAST
        currentPoint[1] = currentPoint[1] + 1
    ##print ('reversePath: [' + str(currentPoint[0]) + ', ' + str(currentPoint[1]) + ']')
    self.gameGrid[currentPoint[0]][currentPoint[1]] = self.UNDEFINED

  ## Check that we go on every cell.
  def verifyGame(self):
    moveCount = 0
    currentPoint = [self.start[0], self.start[1]]

    isEnd = 0
    while (isEnd == 0):
      if (currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.FROM_NORTH):
        currentPoint[0] = currentPoint[0] + 1
      elif (currentPoint[1] > 0) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.FROM_EAST):
        currentPoint[1] = currentPoint[1] - 1
      elif (currentPoint[0] > 0) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.FROM_SOUTH):
        currentPoint[0] = currentPoint[0] - 1
      elif (currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.FROM_WEST):
        currentPoint[1] = currentPoint[1] + 1
      else:
        isEnd = 1

      if isEnd == 0:
        moveCount = moveCount + 1

    ## The number of moves should equal to the size of the map minus one cell because we don't arrive on the start
    if moveCount == ((self.GAME_HEIGHT * self.GAME_WIDTH) - 1):
      print ('OK')
    else:
      print ('ko!!!')

  ## Fill the map with void data.
  def initGame(self):
    self.gameGrid = []
    for i in range(self.GAME_HEIGHT):
      gameLine = []
      for j in range(self.GAME_WIDTH):
        gameLine.append(self.UNDEFINED)

      self.gameGrid.append(gameLine)

    self.initComplexMap()

  ## Create a valid simple map.
  ## It uses a complex algorithm.
  def initComplexMap(self):
    startPoint = random.randint(0, 3)
    if startPoint == 0:
      self.start = [0, 0]
    elif startPoint == 1:
      self.start = [0, self.GAME_WIDTH - 1]
    elif startPoint == 2:
      self.start = [self.GAME_HEIGHT - 1, 0]
    elif startPoint == 3:
      self.start = [self.GAME_HEIGHT - 1, self.GAME_WIDTH - 1]

    self.gameGrid[self.start[0]][self.start[1]] = self.FROM_NOWHERE
    currentPoint = [self.start[0], self.start[1]]

    while ((0 < currentPoint[0]) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.UNDEFINED)) or ((currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.UNDEFINED)) or ((0 < currentPoint[1]) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.UNDEFINED)) or ((currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.UNDEFINED)):
      possibilities = []
      if ((0 < currentPoint[0]) and (self.gameGrid[currentPoint[0] - 1][currentPoint[1]] == self.UNDEFINED)) and (((0 == currentPoint[1]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[1] == self.GAME_WIDTH - 1) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] + 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0] - 1, currentPoint[1], self.FROM_SOUTH])

      if ((currentPoint[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[currentPoint[0] + 1][currentPoint[1]] == self.UNDEFINED)) and (((0 == currentPoint[1]) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[1] == self.GAME_WIDTH - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] + 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0] + 1, currentPoint[1], self.FROM_NORTH])

      if ((0 < currentPoint[1]) and (self.gameGrid[currentPoint[0]][currentPoint[1] - 1] == self.UNDEFINED)) and (((0 == currentPoint[0]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] - 1] != self.UNDEFINED)) or ((currentPoint[0] == self.GAME_HEIGHT - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] - 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0], currentPoint[1] - 1, self.FROM_EAST])

      if ((currentPoint[1] < self.GAME_WIDTH - 1) and (self.gameGrid[currentPoint[0]][currentPoint[1] + 1] == self.UNDEFINED)) and (((0 == currentPoint[0]) or (self.gameGrid[currentPoint[0] - 1][currentPoint[1] + 1] != self.UNDEFINED)) or ((currentPoint[0] == self.GAME_HEIGHT - 1) or (self.gameGrid[currentPoint[0] + 1][currentPoint[1] + 1] != self.UNDEFINED))):
        possibilities.append([currentPoint[0], currentPoint[1] + 1, self.FROM_WEST])

      possibility = possibilities.pop(random.randint(0, len(possibilities) - 1))
      currentPoint = [possibility[0], possibility[1]]
      self.gameGrid[possibility[0]][possibility[1]] = possibility[2]

  ## Create a valid simple map.
  ## It uses a basic algorithm.
  def initSimpleMap(self):
    direction = self.RIGHT

    if random.randint(0, 1) == 0:
      for i in range(self.GAME_HEIGHT):
        if direction == self.RIGHT:
          self.gameGrid[i][0] = self.FROM_NORTH
          for j in range(1, self.GAME_WIDTH):
            self.gameGrid[i][j] = self.FROM_WEST
          direction = self.LEFT
        else:
          for j in range(self.GAME_WIDTH - 1):
            self.gameGrid[i][j] = self.FROM_EAST
          self.gameGrid[i][self.GAME_WIDTH - 1] = self.FROM_NORTH
          direction = self.RIGHT

        self.gameGrid.append(gameLine)

      self.gameGrid[0][0] = self.FROM_NOWHERE
    else:
      for j in range(self.GAME_WIDTH):
        if direction == self.RIGHT:
          self.gameGrid[0][j] = self.FROM_WEST
          for i in range(1, self.GAME_HEIGHT):
            self.gameGrid[i][j] = self.FROM_NORTH
          direction = self.LEFT
        else:
          for i in range(self.GAME_HEIGHT - 1):
            self.gameGrid[i][j] = self.FROM_SOUTH
          self.gameGrid[self.GAME_HEIGHT - 1][j] = self.FROM_WEST
          direction = self.RIGHT

      self.gameGrid[0][0] = self.FROM_NOWHERE

  ## Search all the possible permutations.
  ## It doesn't affect the map.
  def listPermutation(self):
    self.permutableZones = []
    for i in range(self.GAME_HEIGHT - 1):
      for j in range(self.GAME_WIDTH - 1):
        if (self.gameGrid[i + 1][j] == self.FROM_NORTH) and (self.gameGrid[i][j + 1] == self.FROM_SOUTH):
          self.permutableZones.append([[i + 1, j], [i, j + 1]])
        elif (self.gameGrid[i][j] == self.FROM_SOUTH) and (self.gameGrid[i + 1][j + 1] == self.FROM_NORTH):
          self.permutableZones.append([[i, j], [i + 1, j + 1]])
        elif (self.gameGrid[i][j] == self.FROM_EAST) and (self.gameGrid[i + 1][j + 1] == self.FROM_WEST):
          self.permutableZones.append([[i, j], [i + 1, j + 1]])
        elif (self.gameGrid[i][j + 1] == self.FROM_WEST) and (self.gameGrid[i + 1][j] == self.FROM_EAST):
          self.permutableZones.append([[i, j + 1], [i + 1, j]])

  ## Permutate the connection of path.
  ## It receives and returns a valid map.
  def permutate(self):
    self.listPermutation()

    if len(self.permutableZones) > 0:
      permutation = self.permutableZones.pop(random.randint(0, len(self.permutableZones) - 1))
      start = permutation[0]
      end = permutation[1]
      ##print ('Entry of the loop: (' + str(start[0]) + ', ' + str(start[1]) + ')')
      ##print ('Exit of the loop: (' + str(end[0]) + ', ' + str(end[1]) + ')')
      if self.isLoop(end, start):
        self.findPermutation(start, end)
      else:
        end = permutation[0]
        start = permutation[1]
        ## Assertion
        if not self.isLoop(end, start):
          print ('Wrong!')
        self.findPermutation(start, end)

  ## It doesn't affect the map.
  def isInLoop(self, searchedPoint):
    found = False
    for point in self.currentLoop:
      if (searchedPoint[0] == point[0]) and (searchedPoint[1] == point[1]):
        found = True

    return found

  ## It doesn't affect the map.
  def isLoop(self, originalPoint, destination):
    self.currentLoop = []

    point = []
    point.append(originalPoint[0])
    point.append(originalPoint[1])
    self.currentLoop.append([originalPoint[0], originalPoint[1]])
    while ((point[0] != destination[0]) or (point[1] != destination[1])) and (self.gameGrid[point[0]][point[1]] != self.FROM_NOWHERE):
      ##print ('Loop point: (' + str(point[0]) + ', ' + str(point[1]) + ')')
      newY = point[0]
      newX = point[1]
      if self.gameGrid[point[0]][point[1]] == self.FROM_SOUTH:
        newY = point[0] + 1
      elif self.gameGrid[point[0]][point[1]] == self.FROM_NORTH:
        newY = point[0] - 1
      elif self.gameGrid[point[0]][point[1]] == self.FROM_WEST:
        newX = point[1] - 1
      elif self.gameGrid[point[0]][point[1]] == self.FROM_EAST:
        newX = point[1] + 1
      point[0] = newY
      point[1] = newX
      self.currentLoop.append([newY, newX])

    return ((point[0] == destination[0]) and (point[1] == destination[1]))

  ## Permutate the connections of path.
  ## It receives and returns a valid map.
  def findPermutation(self, start, end):
    self.findIntersections()
    if len(self.intersections) > 0:
      self.modifyIntersection(start, end)

  ## Permutate the connections of path.
  ## It doesn't affect the map.
  def findIntersections(self):
    self.intersections = []
    for i in range(1, len(self.currentLoop) - 1):
      point = self.currentLoop[i]
      if self.gameGrid[point[0]][point[1]] == self.FROM_NORTH:
        if (0 < point[1]) and (self.gameGrid[point[0] - 1][point[1] - 1] == self.FROM_SOUTH) and not self.isInLoop([point[0] - 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] - 1]])
        elif (point[1] < self.GAME_WIDTH - 1) and (self.gameGrid[point[0] - 1][point[1] + 1] == self.FROM_SOUTH) and not self.isInLoop([point[0] - 1, point[1] + 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] + 1]])

      elif self.gameGrid[point[0]][point[1]] == self.FROM_SOUTH:
        if (0 < point[1]) and (self.gameGrid[point[0] + 1][point[1] - 1] == self.FROM_NORTH) and not self.isInLoop([point[0] + 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] - 1]])
        elif (point[1] < self.GAME_WIDTH - 1) and (self.gameGrid[point[0] + 1][point[1] + 1] == self.FROM_NORTH) and not self.isInLoop([point[0] + 1, point[1] + 1]):
          self.intersections.append([[point[0], point[1]], [point[0] + 1, point[1] + 1]])

      elif self.gameGrid[point[0]][point[1]] == self.FROM_WEST:
        if (0 < point[0]) and (self.gameGrid[point[0] - 1][point[1] - 1] == self.FROM_EAST) and not self.isInLoop([point[0] - 1, point[1] - 1]):
          self.intersections.append([[point[0], point[1]], [point[0] - 1, point[1] - 1]])
        elif (point[0] < self.GAME_HEIGHT - 1) and (self.gameGrid[point[0] + 1][point[1] - 1] == self.FROM_EAST) and not self.isInLoop([point[0] + 1,

Fej*_*uto 2

您可以从您提到的方法开始寻找哈密顿路径。要进一步随机化解决方案，您可以开始旋转边缘，如wiki上所述。更频繁地执行此操作将使解决方案更加随机。将随机边旋转 N*M 次可以使算法保持在有效范围内，同时使找到的哈密顿路径更加随机。

归档时间：

查看次数：

3424 次

最近记录：

11 年，6 月 前
在有向图中求哈密顿路径的随机算法 8
更多相关链接
相关归档
按顺时针顺序排序点？ 148
混淆ID 81
(纯)函数式编程是否与"算法经典"对抗？ 31
查找具有最接近彼此的K个元素的子集 15
有没有有效的方法将一元数转换为二进制数？ 9
SPOJ问题KPRIMES2 8
uint64_t键的最佳哈希函数是0到最大值的范围是多少？ 8
遍历完整的二进制最小堆 8
链接列表分区功能和反转结果 7
Netlogo：计算图/网络的直径（有两个 foreach） -2
难疑归档
在JavaScript中深度克隆对象的最有效方法是什么？ 5181
@staticmethod和@classmethod有什么区别？ 3360
如何使用正则表达式验证电子邮件地址？ 3201
确定已安装的PowerShell版本 2543
PHP'foreach'如何实际工作？ 1926
对于数组,为什么a [5] == 5 [a]？ 1567
将文件从Docker容器复制到主机 1438
传输安全性阻止了明文HTTP 1425
创建将T限制为枚举的通用方法 1122
有哪些常用的命名git分支实例的例子？ 1034