Поиск в глубину в Python

Question

Я пытаюсь выполнить поиск в глубину в Python, но он не работает.

По сути, у нас есть доска для пасьянсов:

[1,1,1,1,1,0,1,1,1,1]

1 представляют колышки,и 0 это открытое место.Вы должны перемещать колышек по одному ДВУХ СЛОТОВ назад или вперед ТОЛЬКО в пустое место.Если вы перепрыгиваете через другой колышек в процессе, он становится пустым слотом.Вы делаете это, пока не останется один колышек.В общем, игра выглядит так:

[1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 1, 1, 0, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 0, 1, 1, 1]
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1, 0, 1] #etc until only 1 peg left

Вот что у меня есть:

class MiniPeg():
    def start(self):
        ''' returns the starting board '''
        board = [1,1,1,1,1,0,1,1,1,1]
        return board

    def goal(self, node):
        pegs = 0

        for pos in node:
            if pos == 1:
                pegs += 1

        return (pegs == 1) # returns True if there is only 1 peg

    def succ(self, node):
        pos = 0
        for peg in node:
            if peg == 1:                
                if pos < (len(node) - 2):  # try to go forward
                    if node[pos+2] == 0 and node[pos+1] == 1:
                        return create_new_node(node, pos, pos+2)

                if pos > 2: # try to go backwards 
                    if node[pos-2] == 0 and node[pos-1] == 1:
                        return create_new_node(node, pos, pos-2)
        pos += 1

def create_new_node(node, fr, to):
    node[fr] = 0
    node[to] = 1
    if fr > to:
        node[fr-1] = 0
    else:
        node[fr+1] = 0
    return node

if __name__ == "__main__":
    s = MiniPeg()
    b = s.start()

    while not s.goal(b):
        print b
        b = s.succ(b)

Итак, теперь мои вопросы:

1. Правильно ли этоспособ выполнить поиск в глубину для этого?
2. Мой алгоритм не работает !!!Это застревает.Я боролся с этим несколько дней, прежде чем спрашивать здесь, поэтому, пожалуйста, помогите.
3. Похоже, я не следую за СУХОЙ, какие-либо предложения?
4. Боже, помогите мне?

Answer 1

Обычный способ реализации DFS в ситуации, когда каждый шаг - это «переход» от «позиции доски» к некоторому возможному следующему, пока не будет достигнута цель, заключается в следующем (псевдокод)

seenpositions = set()
currentpositions = set([startingposition])
while currentpositions:
  nextpositions = set()
  for p in currentpositions:
    seenpositions.add(p)
    succ = possiblesuccessors(p)
    for np in succ:
      if np in seenpositions: continue
      if isending(np): raise FoundSolution(np)
      nextpositions.add(np)
  currentpositions = nextpositions
raise NoSolutionExists()

Вы, вероятно, также хотите сохранить обратные ссылки, чтобы в конце они могли генерировать серию ходов, ведущих к найденному решению (если есть), но это вспомогательная проблема.

Я не узнаю следов этой общей структуры (или ее разумного варианта) в вашем коде. Почему бы не попробовать записать это таким образом? Вам нужно всего лишь кодировать possiblesuccessors и isending (если вы настаиваете на сохранении позиции в виде списка, вам придется превратить ее в кортеж, чтобы проверить членство в наборе и добавить в набор, но это довольно незначительно; - ).

Answer 2

Не похоже, что вы создаете новые узлы, просто повторно используете существующие DFS требует какой-то стек (либо стек вызовов, либо ваш собственный стек). Где это?

Answer 3

Основная алгоритмическая проблема заключается в том, что функция succ всегда производит только один возможный ход для данного состояния доски. Даже если будет несколько возможных ходов, функция succ просто возвращает первый найденный ход. Поиск в глубину требует обработки всех возможных ходов в каждом состоянии.

Дальнейшие проблемы могут возникнуть из-за того, что create_new_node, несмотря на его имя, на самом деле не создает новый узел, а модифицирует существующий. Для глубокого поиска сначала, где вы хотите сохранить предыдущий узел, было бы лучше, если бы эта функция фактически создала копию списка, который она получает в качестве параметра.

Кроме того, при проверке возможности вернуться назад в succ, вы пытаетесь сделать это только если pos > 2. Это слишком ограничительно, pos > 1 также будет в порядке.

Answer 4

Ну, прежде всего поиск в глубину предполагает дерево. Теперь это имеет смысл, поскольку в большинстве случаев у вас есть несколько возможных ходов. При первом поиске глубины просто делается попытка первого возможного хода, а затем первого возможного хода в новой ситуации и первого возможного хода в этой новой ситуации, пока не будет достигнут успех или больше нет возможных ходов, и в этом случае он будет возвращаться до он находит ход, который еще не пробовал, и снова падает.

«Правильный» способ сделать это с помощью рекурсии. Насколько я вижу, в вашей системе нет рекурсии.

Как-то так будет работать (pythonic psuedo codeish english):

def try_next_move(self, board):
    for each of the pegs in the board:
        if the peg can be moved:
            new_board = board with the peg moved
            if new_board is solved:
                return True
            if self.try_next_move(new_board):
                return True
            # That move didn't lead to a solution. Try the next.
    # No move  worked.
    return False