Эффективная сортировка через генератор путей, чтобы найти самый длинный ⇐ Python

[Гость]

Я пытаюсь написать функцию, которая вычисляет максимальное количество неисследованных ячеек в сетке, достижимое в пределах заданного лимита топлива. Например, у меня есть сетка 10х10, каждая ячейка которой соединена друг с другом, а их вес равен манхэттенскому расстоянию между ними. Из этой сетки я создаю матрицу смежности размером 100x100 и создаю график из матрицы смежности, используя библиотеку networkx. Затем я использую функцию all_simple_paths, которая возвращает генератор, содержащий все пути от источника к целевому узлу.
Теперь возникает проблема при попытке отсортировать этот генератор, чтобы найти Если путь содержит наибольшее количество неисследованных ячеек (в данном случае он равен длине пути), моей программе либо не хватает памяти, либо ее выполнение занимает очень много времени.
I Я попытался преобразовать генератор в список, а затем отсортировать список от самого длинного до самого короткого пути, но это просто приводит к тому, что размер памяти скрипта Python продолжает расти, пока он не займет всю доступную память на моем компьютере (16 ГБ). Я также пробовал использовать функцию sorted для сортировки генератора, как показано ниже, но это занимает слишком много времени и в конечном итоге заканчивается нехватка памяти.

Код: Выделить всё

G = nx.from_numpy_array(A)
sorted_paths = sorted(nx.all_simple_paths(G, source=current_node, target=target_node), key=len, reverse=True)

Если у кого-нибудь есть какие-либо предложения относительно того, как я могу решить свою проблему, я буду очень признателен. Будь то сортировка генератора или, может быть, другая функция внутри networkx/другой библиотеки Python, которая могла бы помочь мне найти максимальное количество неисследованных ячеек в сетке.

Подробнее здесь: https://stackoverflow.com/questions/781 ... longest-on