Вопросы Теги

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

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

В основном у нас есть плата пасьянса штепселя:

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

1's представляют штепсель, и 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. omg помогают мне?
5
задан SilentGhost 26 January 2010 в 16:51
поделиться

4 ответа

Обычный способ реализации 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 (если вы настаиваете на хранении позиции в виде списка, вам придется превратить ее в кортеж для проверки принадлежности к множеству и добавления к множеству, но это довольно незначительно;-)).

10
ответ дан 13 December 2019 в 19:27
поделиться

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

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

Что-то вроде этого будет работать (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
0
ответ дан 13 December 2019 в 19:27
поделиться

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

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

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

0
ответ дан 13 December 2019 в 19:27
поделиться

Я не уверен, имеют ли они какое-либо значение, за исключением того, что они находятся в sys/stat.h , поэтому S может означать «stat».

Я пытался выполнить некоторые детективные работы, например, запись IEEE Std 1003,1, 2004 Edition для sys/stat.h говорит следующее: Впервые выпущено в выпуске 1. Производный от выпуска 1 SVID.

Затем Спецификации разработчика для двоичного интерфейса приложения System V (см. Том 1a [pdf]), стр. 95 и даже с именами, начинающимися с S _ . Я не смог вернуться дальше этого.

О вашем вопросе в целом: большая часть - история. Например, creat () находится в POSIX, но имя происходит из истории . Многие имена функций POSIX (и поведение) происходят от стандарта C. Фактически их описание обычно имеет текст , например :

Функциональные возможности, описанные на этой справочной странице, соответствуют стандарту ISO C. Любое противоречие между описанными здесь требованиями и стандартом ISO C является непреднамеренным. Этот объем IEEE Std 1003.1-2001 относится к стандарту ISO C.

Я думаю, что единственный способ найти какую-либо логику за POSIX API - это прочитать историю Unix.

Это может помочь:

-121--4244717-

В коде вы можете сделать все, что угодно с белыми местами. Однако с некоторыми браузерами, если вы написали что-то вроде: 

<a href="http://example.com">foobar
</a>

Новая строка может иметь (небольшой) инцидент с тем, как ваша ссылка отображается, особенно на «активный» статус.

-121--3909841-

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

1
ответ дан 13 December 2019 в 19:27
поделиться
Другие вопросы по тегам:

Похожие вопросы: