Проблема состоит в том, чтобы найти самую длинную последовательность чисел от 1 до 100, чтобы каждое число было много или дивизором, либо предыдущим, и без повторения. Например, 50 25 5 35 7 63 21 - это действительная последовательность < /p>
Я считаю эту проблему найти самый длинный путь на графике. Все узлы графа представляют собой целые числа от 1 до 100, а узлы x и y связаны, если x делит y или y делят x.
Эта проблема хорошо известна как NP-proplem: https://en.wikipedia.org/wiki/longest_path_problem. Сообщение: https://stackoverflow.com/a/30747003/16673579
и создал соответствующий график с этим кодом:
connections = []
for i in range(1,101):
for j in range(1,101):
if math.gcd(i,j) in [i,j] and i!=j:
connections.append((i,j))
my_graph = Graph(connections=connections)
< /code>
(я знаю, что этот код может быть оптимизирован, но это не главное) < /p>
Теперь я ищу способ разработки такого алгоритма. Я искал множество ссылок на текущий самый быстрый алгоритм, чтобы найти самый длинный путь на графике, даже если я ожидаю, что он может быть невозможно из -за сложности и размера данных, но я не могу найти надежный источник и реализацию Python
Подробнее здесь: https://stackoverflow.com/questions/797 ... in-a-graph
