Поиск в глубину в 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. Похоже, я не слежу за DRY. Есть предложения?
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

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

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

Что-то вроде этого будет работать (питонический псевдокодовый английский):

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

Answer 4

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

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

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