-3

わかりましたので、ボードのすべての可能なソリューションを出力するコードを C で作成します。ボードは次のような行を持つ nxn ボードです (3x3): AA BA BB。

ゲームの目的は、ボードを垂直または水平に移動するだけで、ボード内のすべての位置を訪れることです。また、最初または2番目の文字が同じ場合にのみ次の位置に移動できるため、AAからBAには移動できますが、AAからBBには移動できず、各位置に1回しかアクセスできません. 開始位置は常に左上隅または 00 の位置です。

とにかく、コンピューターが 00 から開始し、次の有効な位置、たとえば 01 をチェックするアルゴリズムを考えました。次に、コンピューターは、00 と 01 のチェーンを開始位置として使用して、すべての可能なソリューションをチェックします。それ以上ない場合、コンピューターは新しいチェーンをチェックします。たとえば、00、10 などです。以前の解決策を繰り返さないようにするにはどうすればよいでしょうか? 私は再帰で何かを考えていました。私のもの以外に、より効率的な経路探索アルゴリズムはありますか?

4

2 に答える 2

0

Re:以前の解決策を繰り返さないようにするにはどうすればよいですか?

深さ優先検索アルゴリズムの一部には、訪問したノードを 2 回訪問しないようにマークすることが含まれます。これは、さまざまな方法で実行できます。ノード自体のスペア ビット、すべての検索の前に初期化、または検索対象のグラフの外部にある動的なデータ構造を設定します。

ちなみに、問題はグレイコードに関連しています。これは、連続するコード間で1ビットだけが変化するようにバイナリワードのコードを配置する方法です。例: 000 001 011 010 110 100 101 111。

これが意味することは、ボードでは、それが 2 ビットのグレイ コードの後継者または先行者である場合にのみ、隣接する正方形に移動できるということです。

しかし、グレイ コードはシーケンスを形成します。したがって、この問題は、0 から 3 までの単純な番号付けがあり、N から N+1 の後継者または N-1 の前任者まで許可される問題と同型です。

これは、問題について考えるのに役立ちます。

于 2012-04-10T02:11:53.803 に答える
0

これは、Python での非常に非効率的なソリューションです。あなたは従うことができるはずです。私はあなたの母国語で答えを教えたくありませんでした:P

class Finder:
    def __init__(self, board, n, x, y):
        self.board = board
        self.n = n

        # Create a copy of the board.
        self.copy = []
        for i in range(n):
            row = []
            self.copy += [row]
            for j in range(n):
                row += [False]

        # The best move sequence (longest).
        self.best = []
        # The current move sequence.
        self.move = []

        self.find(x, y)

    def valid_move(self,x1, y1, x2, y2):
        # Don't move off the board!
        if x2 < 0 or x2 > self.n - 1 or y2 < 0 or y2 > self.n - 1:
            return False

        # Don't go somewhere we've gone before!
        if self.copy[y2][x2]:
            return False

        # See if this is a valid move.
        a = self.board[y1][x1]
        b = self.board[y2][x2]
        return a[0] == b[0] or \
               a[0] == b[1] or \
               a[1] == b[0] or \
               a[1] == b[1] 

    def find(self,x, y):
        self.move += [(x, y, board[y][x])]
        self.copy[y][x] = True

        # If this is the best path, then create a copy.
        if len(self.move) > len(self.best):
            self.best = list(self.move)

        # Short-circuit if the optimal route is found.
        if len(self.best) == self.n * self.n:
            return

        newX = x - 1
        newY = y
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        newX = x
        newY = y - 1
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        newX = x + 1
        newY = y
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        newX = x
        newY = y + 1
        if self.valid_move(x, y, newX, newY):
            self.find(newX, newY)

        # Clean up by removing the last move.
        self.move = self.move[:-1]
        self.copy[y][x] = False

 # The board
board = \
[["AB", "XX", "DE"],
 ["BB", "FE", "DD"],
 ["BC", "CC", "CD"],
 ]

# The size of the board.
n = 3

# Find!!
finder = Finder(board, n, 0, 0)

for row in board:
    print(row)

# Print empty line.
print()

for move in finder.best:
    print(move)

出力は次のとおりです。

['AB', 'XX', 'DE']
['BB', 'FE', 'DD']
['BC', 'CC', 'CD']

(0, 0, 'AB')
(0, 1, 'BB')
(0, 2, 'BC')
(1, 2, 'CC')
(2, 2, 'CD')
(2, 1, 'DD')
(2, 0, 'DE')
于 2012-04-10T02:53:16.513 に答える