1

この発電機はどのように機能しますか? 外側の for ループ中に明らかに切り替わりました。ジェネレーターは for ループ中に評価しますか?

コードはhttp://rosettacode.org/wiki/N-queens_problem#Pythonから適応されます
コードをインポートすると、次のように表示されます:
[[1, 3, 0, 2], [2, 0, 3, 1]]

コードの前に、
「上記のコードを驚くほど単純に変更する (リスト内包表記をジェネレーター式に変更する) ことで、バックトラッキング ソリューションが生成されます。」 

class Solution:
    # @return a list of lists of string
    def under_attack(self, col, queens):
        return col in queens or any(abs(col - x) == len(queens)-i for i,x in enumerate(queens))

    def solve(self,n):
        solutions = [[]]
        for row in range(n):
            solutions = (solution+[i] for solution in solutions
                                      for i in range(n)    
                                      if not self.under_attack(i, solution))
        print(list(solutions))
        return solutions


A=Solution()
list(A.solve(4))
4

1 に答える 1

3

このアルゴリズムは、リスト内包表記を使用するアルゴリズムとまったく同じように機能します。唯一の違いは、ジェネレーター式を使用することです。実際には、より多くのジェネレーターが内部にネストされたジェネレーターを作成します! そのため、考えられるすべての解を一度にリストする代わりに、必要に応じてより多くの解を遅延して生成します。

under_attackこれは、グローバルに定義されたカウンター変数が呼び出されるたびに増加し、このカウンターが増加した回数を確認することで簡単に確認できます。

gen = solve(8) # just create the generators, under_attack called 0 times
next(gen)      # first solution,             under_attack called 876 times
list(gen)      # all remaining solutions,    under_attack called 15720

を実行するとlist(gen)、すべての解が生成されますが、next(gen)計算されるのは 1 つだけです。

さて、実際のアルゴリズムです。これは、非ジェネレーター バージョンの方が簡単に説明できます。また、クラスは必要ありません。

def under_attack(col, queens):
    return col in queens or any(abs(col - x) == len(queens)-i         # (1)
                                for i,x in enumerate(queens))         # (2)

def solve(n):
    solutions = [[]]
    for row in range(n):                                              # (3)
        solutions = [solution+[i] for solution in solutions           # (4)
                                  for i in range(n)                   # (5)
                                  if not under_attack(i, solution)]   # (6)
        print solutions # remove this when using generator!           # (7)
    return solutions

まず、under_attack関数。クイーンの列と既に配置されているクイーンの列が与えられた場合、これは、同じ列に既にクイーンがあるかどうか ( 1、 before or)、またはanyクイーンが同じ対角線上にあるかどうか ( ) をチェックします2。

これでsolve: これはボードのすべての行をループし、各行に 1 つのクイーンを配置します。solutions各サブリストは、これまでに配置されたクイーンの列を保持する部分的なソリューションのリストです。[[3,1]]行0、列3、および行1、列1にクイーンを持つ1つの（部分）ソリューションを意味します。ここで、各行（3）について、行の部分ソリューションの各組み合わせで部分ソリューションを更新します。そのクイーンが攻撃を受けない場所( )4の新しいクイーン ( ) の列( ) とその列 ( )。56

説明するために非ジェネレーター バージョンを選択した理由は、このようにして、ループの各反復で部分的な解決策を出力できるためです ( 7)。ジェネレーターを使用すると、これは不可能です。リストを印刷するだけではジェネレーターが使い果たされ、構築する部分的なソリューションがなくなるためです。の場合n=4:

[[0],            [1],          [2],         [3]]               # 1st queen 
[[0, 2], [0, 3], [1, 3],       [2, 0],      [3, 0], [3, 1]]    # 2nd queen 
[[0, 3, 1],      [1, 3, 0],    [2, 0, 3],   [3, 0, 2]]         # 3rd queen 
[                [1, 3, 0, 2], [2, 0, 3, 1]]                   # 4th queen

最初のクイーンはどの列にも配置できます。これにより、2 番目のクイーンの可能な位置がすでに制限されており、現在は 1 つまたは 2 つの可能な場所しかありません。3 番目のクイーンはさらに制限されており、クイーン 1 と 2 のいくつかの位置では、まったく位置が見つかりません。最後に、最後のクイーンが配置され、これがソリューション セットです。

于 2014-07-31T08:49:54.530 に答える