Есть ли способ перебрать список в определенном порядке индексов в Python - PullRequest
Новая
       53

Есть ли способ перебрать список в определенном порядке индексов в Python

0 голосов
/ 13 октября 2019

Хорошо, прошло много времени с тех пор, как я работал на python. Но в основном я делаю классическую задачу из 8 задач, поэтому с учетом строки, такой как «12-453786», моя программа решает ее для желаемого «12345678-». В настоящее время я использую поиск в ширину, чтобы решить эту проблему, и сохраняю посещенные узлы и узел, полученный в следующем примере. Однако, чтобы проследить путь или количество ходов, которые фактически требуются для завершения головоломки, мне нужно иметь возможность начать с решенного кортежа и проследить мой путь назад через мой список кортежей до начального состояния

Я былподумайте о том, чтобы сделать какое-то время, пока решено! = цикл начального запуска, но это не сработает. 

 def breadth_first_search(puz):
    qu = queue.Queue()
    laststate=""
    qu.put((puz, laststate))
    startstate=puz
    visited=[]
    #visited[puz] = puz

    while queue: 

        puz = qu.get()
        visited.append(puz)

        pos = puz[0].index('-')
        nebs = neighborcells(pos)
        #print(*visited)
        if puz[0] == "12345678-":

            break
        else:
            for i in nebs:

                swapped=swap(puz,i,pos)
                if swapped in visited:
                    pass #?
                else:
                    qu.put((swapped, puz[0]))
     #some sort of linked list like function to get the path of result to start
     #here

ПРИМЕР ПОСЕЩЕННЫХ УЗЕЛ (список кортежей) 

[('12-453786', ''), 
 ('1-2453786', '12-453786'), 
 ('12345-786', '12-453786'), 
 ('-12453786', '1-2453786'), 
 ('12-453786', '1-2453786'), 
 ('1524-3786', '1-2453786'), 
 ('1234-5786', '12345-786'), 
 ('12345678-', '12345-786')]

Ожидаемый результат для этого конкретногоголоволомка должна быть 2 хода

1 Ответ

0 голосов
/ 13 октября 2019

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

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

...