Оптимизация рекурсии

Я пытаюсь найти определенный путь через свой 2d-массив

Мой массив может выглядеть так:

temp = [
    ["placeholder", 2, 0],
    ["placeholder", 1, 7, 3],
    ["placeholder", 4, 5, 8],
    ["placeholder", 6, 3, 5, 2],
    ["placeholder", 7],
    ["placeholder", 3, 0],
]

Внутренние массивы содержат заполнитель, за которым следует переменное количество целых чисел. Эти целые числа находятся в диапазоне значений от 0 до 19 (включая 0 и 19).

Я хочу найти путь сверху вниз через эти внутренние массивы, где ни одно число не используется более одного раза.

В temp[0] я могу выбрать свое 1-е значение либо 2, либо 0
В temp[1] я могу выбрать второе значение 1, 7 или 3
В temp[2] я могу выбрать третье значение 4, 5 или 8
В temp[3] я могу выбрать 4-е значение 6, 3, 5 или 2
Обратите внимание, что на этом шаге я не могу выбрать 2, если я уже выбрал 2 на 1-м шаге
Я не могу выбрать 3, если я уже выбрал 3 на 2-м шаге
Я не могу выбрать 5, если я уже выбрал 5 на 3-м шаге
и т. д.

Вот некоторые законные пути:

  • 2-1-4-6-7-3
  • 0-1-4-5-7-3

Вот некоторые незаконные пути:

  • 2-1-4-2-7-3 (2 касаются дважды)
  • 0-1-4-5-7-0 (0 касается дважды)

Я хочу, чтобы моя функция выводила полностью легальный путь.
Я просто хочу, чтобы моя функция возвращала false, если путь не найден. Я попытался написать свое собственное рекурсивное решение этой проблемы, которое, я думаю, работает, но страдает от большой неэффективности, и поэтому для его завершения требуются буквально годы. Размер моего предполагаемого массива больше похож на 20 x 1..20

Пока мой код выглядит так (написан на Python 3) (и с временным массивом):

temp= [
    ["placeholder", 7, 3],
    ["placeholder", 3, 3],
    ["placeholder", 4, 3],
    ["placeholder", 3, 8],
    ["placeholder", 1, 3],
]

def findpath(array, path = []):
    
    if path and path.count(path[-1]) > 1:
        return False

    if len(path) == len(array):
        print(path)
        return True
    
    routes = array[len(path)][1:]

    for route in routes:
        path.append(route)
        if findpath(array, path):
            return True
        path.pop(-1)

findpath(temp)

Этот код печатает: [7, 3, 4, 8, 1]

Этот подход заключается в переборе всех возможностей, пока не будет найдено решение. В худшем случае мой массив temp будет содержать 20 массивов, каждый из которых будет содержать 20 значений, что составит 20! возможных решений, или другими словами 2.432.902.008.176.640.000 возможных путей. Давайте утрируем и скажем, что моему компьютеру требуется 1 мс для обработки одной итерации этой функции. Моя математика может быть неправильной, но это будет означать, что этот процесс может занять 77 146 816,6 лет (без учета високосных лет), и, честно говоря, у меня нет такого времени.

Должен быть более разумный способ подойти к этой проблеме. Я заметил одну вещь: если функция встречает внутренний массив на шаге, например. 15, содержащий только одно целое число, например. 2, то функция попытается настроить свои последние выборки (сначала шаг 14, затем шаг 13) по одному, не осознавая, что она уже выбрала 2 на шаге 2. В этой ситуации вернемся к шагу 2 и изменим значение с 2 на что-то другое сэкономит чертову тонну итераций. Единственная проблема в том, что я понятия не имею, как это реализовать, и не знаю, как оптимизировать это дальше.

Вот реальный пример массива (не уверен, что он содержит решение)

temp = [
['placeholder', 2, 6, 11, 14, 15, 16, 18], 
['placeholder', 2, 6, 7, 10, 11, 14, 15, 16, 17, 18, 19], 
['placeholder', 2, 6, 10, 11, 14, 15, 16, 18, 19], 
['placeholder', 2, 6, 11, 14, 15, 16, 18, 19], 
['placeholder', 2, 6, 11, 14, 15, 16], 
['placeholder', 2, 6, 7, 10, 11, 14, 15, 16, 18, 19], 
['placeholder', 2, 6, 7, 8, 9, 10, 11, 14, 15, 16, 17, 18, 19], 
['placeholder', 11, 15, 16], 
['placeholder', 11, 14, 15, 16], 
['placeholder', 0, 1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 11, 15], 
['placeholder', 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 2, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 15], 
['placeholder', 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19], 
['placeholder', 2, 11, 14, 15, 16], 
['placeholder', 2, 6, 7, 8, 10, 11, 14, 15, 16, 17, 18, 19]
]

Надеюсь, вы поможете мне научиться <3

Можете ли вы уточнить, что является допустимым «перемещением» из одной строки в следующую строку и столбец? И если нет действительного пути, что будет на выходе?

Daniel Hao 17.12.2020 21:26

Я немного отредактировал сообщение, надеюсь, это имеет больше смысла :)

pluto9800 17.12.2020 21:41

Итак, результат - это то, что вы ожидаете? В чем проблема? Если эффективность, можете ли вы привести конкретный пример, когда это становится проблемой?

trincot 17.12.2020 21:48

Эй, я снова изменил пост, спасибо за вклад :)

pluto9800 17.12.2020 22:27

Вы знакомы с алгоритмом «возврата»? Вы можете изучить его и применить ту же технику здесь. Просто погуглите тему. Вы узнаете больше. Если вы все еще застряли позже, вы можете опубликовать дополнительные вопросы.

Daniel Hao 17.12.2020 22:40

Спасибо большое, посмотрю

pluto9800 17.12.2020 22:44

@ pluto9800 pluto9800 Я внес некоторые изменения в свой пост, увидев ваш реальный пример ввода. Если у вас есть какие-либо вопросы по моему сообщению, я буду рад помочь :D

Mulan 18.12.2020 16:40

Большое спасибо за ваше время и усилия. Сейчас я просмотрю ваш пост и обязательно дам вам знать, если мне понадобится дополнительная помощь :)

pluto9800 18.12.2020 19:03
Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
0
8
83
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

функциональное наследие

Рекурсия — это функциональное наследие, поэтому ее использование с функциональным стилем дает наилучшие результаты. Это означает избегать мутаций, таких как .append и .pop, и других побочных эффектов.

Ниже мы используем set для эффективного пропуска недопустимых комбинаций и tuple для сохранения пути. Для каждой рекурсии создаются новый набор и кортеж.

def traverse(t, s = set(), p = ()):
  if not t:
    yield p
  else:
    [ [_, *values], *more ] = t
    for v in values:
      if v not in s:
        yield from traverse(more, {*s, v}, (*p, v))

Использование данных в вашей примерной программе -

temp = \
  [ ["placeholder", 7, 3]
  , ["placeholder", 3, 3]
  , ["placeholder", 4, 3]
  , ["placeholder", 3, 8]
  , ["placeholder", 1, 3]
  ]

for p in traverse(temp):
  print(p)
(7, 3, 4, 8, 1)
(7, 3, 4, 8, 1)

И используя данные в вашем исходном вопросе -

temp = \
  [ ["placeholder", 2, 0]
  , ["placeholder", 1, 7, 3]
  , ["placeholder", 4, 5, 8]
  , ["placeholder", 6, 3, 5, 2]
  , ["placeholder", 7]
  , ["placeholder", 3, 0]
  ]

for p in traverse(temp):
  print(p)
(2, 1, 4, 6, 7, 3)
(2, 1, 4, 6, 7, 0)
(2, 1, 4, 3, 7, 0)
(2, 1, 4, 5, 7, 3)
(2, 1, 4, 5, 7, 0)
(2, 1, 5, 6, 7, 3)
(2, 1, 5, 6, 7, 0)
(2, 1, 5, 3, 7, 0)
(2, 1, 8, 6, 7, 3)
(2, 1, 8, 6, 7, 0)
(2, 1, 8, 3, 7, 0)
(2, 1, 8, 5, 7, 3)
(2, 1, 8, 5, 7, 0)
(2, 3, 4, 6, 7, 0)
(2, 3, 4, 5, 7, 0)
(2, 3, 5, 6, 7, 0)
(2, 3, 8, 6, 7, 0)
(2, 3, 8, 5, 7, 0)
(0, 1, 4, 6, 7, 3)
(0, 1, 4, 5, 7, 3)
(0, 1, 4, 2, 7, 3)
(0, 1, 5, 6, 7, 3)
(0, 1, 5, 2, 7, 3)
(0, 1, 8, 6, 7, 3)
(0, 1, 8, 5, 7, 3)
(0, 1, 8, 2, 7, 3)

генераторы ленивы

Поскольку мы используем генератор, мы можем остановить создание путей в любое время. Возможно, вы хотите найти только первый правильный путь -

def first_valid_path(t):
  for path in traverse(t):
    return path

temp = \
  [ ["placeholder", 2, 0]
  , ["placeholder", 1, 7, 3]
  , ["placeholder", 4, 5, 8]
  , ["placeholder", 6, 3, 5, 2]
  , ["placeholder", 7]
  , ["placeholder", 3, 0]
  ]

print(first_valid_path(temp))
(2, 1, 4, 6, 7, 3)

оптимизация

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

temp.sort(key=len)
print(temp)
[ ['placeholder', 15]
, ['placeholder', 11, 15] 
, ['placeholder', 11, 15, 16] 
, ['placeholder', 11, 14, 15, 16] 
, ['placeholder', 2, 11, 14, 15, 16] 
, ['placeholder', 2, 6, 11, 14, 15, 16] 
, ['placeholder', 2, 6, 11, 14, 15, 16, 18] 
, ['placeholder', 2, 6, 11, 14, 15, 16, 18, 19] 
, ['placeholder', 2, 6, 10, 11, 14, 15, 16, 18, 19] 
, ['placeholder', 2, 6, 7, 10, 11, 14, 15, 16, 18, 19] 
, ['placeholder', 2, 6, 7, 10, 11, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 2, 6, 7, 8, 10, 11, 14, 15, 16, 17, 18, 19]
, ['placeholder', 2, 6, 7, 8, 9, 10, 11, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 2, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]  
, ['placeholder', 1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 0, 1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19] 
, ['placeholder', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
]

Не замерял, но решение находится моментально (менее секунды) -

print(first_valid_path(temp))
(15, 11, 16, 14, 2, 6, 18, 19, 10, 7, 17, 8, 9, 13, 12, 4, 1, 0, 5, 3)

Чтобы привести путь в правильном порядке, он должен быть не отсортирован. Это можно сделать несколькими способами, и я рассмотрю возможность обновления поста позже предлагаемым решением. Пока это остается в качестве упражнения для читателя :D


несортировать

Если вы зашли так далеко, отлично! Выше я предложил процесс сортировки и несортировки, а ниже я покажу один из таких способов обработки несортировки -

def traverse(init):
  def sort(t):
    z = list(enumerate(t))
    z.sort(key=lambda _: len(_[1]))
    return z

  def unsort(p):
    p.sort(key=lambda _: _[0])
    return tuple(v for (_, v) in p)

  def loop(t, s, p):
    if not t:
      yield unsort(p)
    else:
      [ (k, [_, *values]), *more ] = t
      for v in values:
        if v not in s:
          yield from loop(more, {*s, v}, [*p, (k, v)])
  
  yield from loop(sort(init), set(), [])

Это работает путем создания промежуточного представления с помощью sort -

[ (16, ['placeholder', 15])
, (10, ['placeholder', 11, 15])
, (7, ['placeholder', 11, 15, 16])
, (8, ['placeholder', 11, 14, 15, 16])
, (18, ['placeholder', 2, 11, 14, 15, 16])
, (4, ['placeholder', 2, 6, 11, 14, 15, 16])
, (0, ['placeholder', 2, 6, 11, 14, 15, 16, 18])
, (3, ['placeholder', 2, 6, 11, 14, 15, 16, 18, 19])
, (2, ['placeholder', 2, 6, 10, 11, 14, 15, 16, 18, 19])
, (5, ['placeholder', 2, 6, 7, 10, 11, 14, 15, 16, 18, 19])
, (1, ['placeholder', 2, 6, 7, 10, 11, 14, 15, 16, 17, 18, 19])
, (19, ['placeholder', 2, 6, 7, 8, 10, 11, 14, 15, 16, 17, 18, 19])
, (6, ['placeholder', 2, 6, 7, 8, 9, 10, 11, 14, 15, 16, 17, 18, 19])
, (14, ['placeholder', 2, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19])
, (11, ['placeholder', 2, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
, (15, ['placeholder', 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
, (12, ['placeholder', 1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
, (9, ['placeholder', 0, 1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
, (17, ['placeholder', 0, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
, (13, ['placeholder', 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
]

Пути состоят из кортежей (sort_key, value) и unsort, объединенных с помощью sort_key -

[(16, 15), (10, 11), (7, 16), (8, 14), (18, 2), (4, 6), (0, 18), (3, 19), (2, 10), (5, 7), (1, 17), (19, 8), (6, 9), (14, 13), (11, 12), (15, 4), (12, 1), (9, 0), (17, 5), (13, 3)]

Наконец, sort_key удаляется, и остается только тот путь значений, который нас интересует. Теперь мы можем видеть путь в правильном порядке. Результат вычисляется мгновенно (менее одной секунды) -

print(first_valid_path(temp))
(18, 17, 10, 19, 6, 7, 9, 16, 14, 0, 11, 12, 1, 3, 13, 4, 15, 5, 2, 8)

все допустимые пути

Выше мы использовали find_first_path, но наша техника сортировки/несортировки также эффективна при поиске всех решений —

for p in traverse(temp):
  print(p)

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

Для небольшого ввода, такого как тот, что в посте, он работает нормально. Однако для большего 2D-массива (20x20), как спрашивал @pluto9800, кажется, что это занимает гораздо больше времени - 368,528 секунды на моем ПК Acer Aspire E15? Это ожидается?

Daniel Hao 18.12.2020 05:43

Дэниел, 7 минут, чтобы перебрать все решения или найти только первое? Тем не менее, это улучшение по сравнению с 77 миллиардами лет. Одна оптимизация, о которой я подумал, но не реализовал здесь, заключалась в следующем: 1) сначала отсортировать входной массив с наименьшим количеством возможностей, поскольку эти требования сложнее выполнить, 2) выполнить обход, 3) отменить сортировку пройденных путей, чтобы восстановить их первоначальный порядок. Опубликуйте данные, с которыми вы работали, и, возможно, я сделаю снимок позже сегодня. Спасибо за комментарий :)

Mulan 18.12.2020 14:01

Спасибо! @Спасибо. Это действительно значительное улучшение. Просто интересно, есть ли место для дальнейшего повышения производительности... (поскольку автор публикует вопрос для массива 20x20). Отличные идеи - тоже попробую. Недурно!

Daniel Hao 18.12.2020 14:04

Строка [ [_, *values], *more] = t также может быть оптимизирована. Вместо деструктуризации, создающей промежуточные значения, можно использовать индекс. Это добавляет больше концептуальных накладных расходов, но вычитает пространство и время из вычислительного процесса.

Mulan 18.12.2020 14:08

Дэниел, я быстро проверил теорию сортировки, и она работает для большого набора данных, предоставленного OP. Этап отмены сортировки не будет слишком сложным и не потребует значительных затрат времени/пространства для процесса. Я буду продолжать ломать голову над этим, пока позволяет время.

Mulan 18.12.2020 15:48

Удивительно быстро сейчас! Поздравляю! Несортировка будет работать лучше всего, потому что она сохраняет порядок обхода. Теперь время - общее время: 0,0119. Предложения: для автора (как широкой публики) - возможно, написать подробный анализ и оптимизацию, это развивается. Спасибо! @ Спасибо. Отличная работа.

Daniel Hao 18.12.2020 16:41

Давайте продолжим обсуждение в чате.

Daniel Hao 18.12.2020 16:42

Другие вопросы по теме