アルゴリズムの浅い深さからの遡及法

私の理解する遡及法

遡及法は本質的に窮挙法であり、窮挙法の最適化には、どのような状況が考慮する必要がないのかを判断し、これらの不要な状況(剪定)を遍歴しないことが最適化の鍵である.

貧乏挙法を理解し、遡及法を理解するにはまず貧乏挙法を本当に理解しなければならない.貧挙法

を以下の例題で理解する
出力される数字の全配列
入力:1 2 3
出力:

[
[1, 2, 3], 
[1, 3, 2], 
[2, 1, 3], 
[2, 3, 1], 
[3, 1, 2], 
[3, 2, 1]
]

コアステップの疑似コード:

Permutation(array A, array B){
    If Array B is OK
        Return array A
    Else 
        For I in B:
        Permutation(A add I, B remove I)
}

Python実装:

# Full Permutation   
def permute(numbers: list):
    sorted(numbers)
    visited = [0 for i in numbers]
    output = []
    middle = []
    helper(numbers, visited, middle, output)
    return output


def helper(numbers: list, visited: list, middle: list, output: list):
    if len(middle) is len(numbers):
        output.append(middle.copy())
        return
    for i in range(0, len(numbers)):
        if visited[i] is 0:
            visited[i] = 1
            middle.append(numbers[i])
            helper(numbers, visited, middle, output)
            visited[i] = 0
            middle.pop()


if __name__ == '__main__':
    nums = [1, 2, 3]
    print(permute(nums))

N皇后問題、これは遡及法の中で比較的経典で、私たちは貧挙法の全配列を理解して、N皇后問題を理解してみることができて、実は全配列の実現も遡及の思想を使ったのです.

私たちは8皇后を例にして、8*8の碁盤の上で、8つの皇后の駒を置いて、彼らが同業者の同列と対角線の上でできないようにします.
入力:8
出力:92
Python実装:

# N queen n     
def n_queens(n: int):
  output = [0]
  middle = [-1 for i in range(0, n)]
  compute_n_queen(n, 0, middle, output)
  return output[0]
 
 
def compute_n_queen(n: int, row: int, middle: list, output: list):
  if n is row:
    output[0] += 1
    return
  #      
  for column in range(0, n):
    flag = 1
    middle[row] = column
    #            ，          ，         
    for j in range(0, row):
      #             ，            ，         
      #                      
      if middle[row] is middle[j] or row - middle[row] is j - middle[j] or row + middle[row] is j + middle[j]:
        flag = 0
        break
    if flag:
      compute_n_queen(n, row + 1, middle, output)
 
 
if __name__ == '__main__':
  print(n_queens(8))