Комментарии 32
наивный подход предполагает перебор всех возможных последовательностей, однако, этот метод предпологает перебор
n!
Мне кажется вы недооцениваете наивность. Даже очень наивный программист не будет строить сначала факториал всех последовательностей, а потом их проверять. По мне, наивный метод будет заключаться в попытках на каждом шаге просто поставить все возможные числа, которые дают квадрат (в сумме с предыдущим) и не были уже использованы.
А чем ваш метод отличается от того, что я написал выше? Возможность выбрать следующее число в цепочке вы берете через матрицу. Выглядит как вполне компромисс проверки квадратности не через сумму, а через пространство (память). Хз, как по мне, предварительный расчет возможных квадратов уже достаточен для оптимизаций, вряд ли операция суммы настолько затратнее индекса.
Казалось бы,
1) получаем множество квадратов
2) получаем таблицу смежности
3) делаем рекурсивную функцию, строящую цепочки (W - множество использованных в цепочке чисел)
4) запускаем её для всех стартовых значений
Это будет тупой перебор, но в нём не будет ничего лишнего :)
Представление таблицы смежности как двоичной матрицы - не очень эффективно, потому что заставит бегать по строке матрицы, в которой порядка √n единичек и (n-√n) ноликов.
Простите, а что у Вас в верхнем выражении за фигурной скобкой написано?
Во-первых, спасибо за символьное описание. Намного меньше вопросов вызывает. Во-вторых, солидарен с таким подходом - тут сразу руки чешутся рекурсию написать. В-третьих, NIT, я бы квантор всеобщности местами убрал.
Ну и P.S. в языках без хвостовой рекурсии, корутин и т.д. придется в цикл всё переводить. Но рассуждать и строить решения в рамках рекурсии, а потом переводить в цикл, мне кажется, проще в таких задачах.
Вы в правильную сторону думаете: надо построить граф, где вершины - числа, а ребра есть между двумя числами, если их сумма - квадрат. В графе будет что-то порядка n sqrt(n)/2 ребер.
Надо в этом графе найти все пути, проходящий через все вершины. Это почти что задача коммивояжора на очень специфичном графе. У вас n, похоже, весьма небольшое, поэтому лучшим решением тут было бы динамическое программирование.
F(S, a, b) - есть ли путь из a в b, проходящий через вершины из множества S. Пересчет прост: перебираем следующую вершину v в пути из S/{a,b}, в которые есть ребра из a, и смотрим, есть ли оставшийся путь через F(S/{a}, v, b}. Ну и база, когда S={a, b}.
А вот потом это ДП можно использовать для отсечения вообще всех тупиков в переборе. Перебрали начало и конец всего пути, а потом рекурсивно перебирайте следующую вершину в пути, если ДП говорит, что путь там существует.
Это все будет за O(n^3 2^n)
За такое время, кажется, можно найти один путь.
А вот всего путей может быть аж (sqrt(n)!)^sqrt(n), что примерно (n/c)^(n/2) (и гораздо больше чем n^3 * 2^n): если граф распадается на почти полные компоненты по sqrt(n) вершин, где у каждой компоненты есть "первая" и "последняя", при этом "последняя" очередной компоненты связанна с "первой" следующей. По каждой компоненте будет sqrt(n)! путей, компонент sqrt(n), что даёт оценку вначале.
А почему у Вас получилась такая оценка? всего вариантодля еще дают , и для построения каждого надо примерно операций (примерное количество ребер из ). То есть, получается
И кажется, можно обойтись без - если взять - количество гамильтоновых путей в , начинающихся в .
Я сильно сверху оценивал количество вариантов для следующей вершины. Так-то, вы правы, можно и корнем ограничиться. И вторая ваша идея тоже отличная. Действительно, не важно же где путь закончится, мы все-равно все возможные концы перебираем. В итоге вы степень n до 1.5 уменьшили.
Некий китаец посчитал количество решений до n=59 (oeis.org/A071983), и у меня нет идей, как он в принципе мог это сделать.
Там похоже, что количество решений растет как 4^n, поэтому любое перечисление решений будет неэффективно.
Тем не менее, простой DFS с оптимизациями (представление ребер графа и подмножеств вершин битовыми масками) на практике оказался почти самым быстрым: 4 часа для n=46 (во всех алгоритмах я считаю однопоточное исполнение). До этого его скорость растет примерно как 3^n, но понятно, что на больших n она выростет как минимум до 4^n.
DP оказалось неэффективно: для n=39 у меня уже не хватает памяти (растет экспоненциально), а решение для n=38 занимает 4.5 минуты.
Самое эффективное решение, которое я нашел, - комбинация DFS и DP: для нечетного n ищем с помощью DFS количество цепочек F(a, S), начинающихся в a, для всех подмножнств S мощности (n+1)/2. Эти позволяет рассчитать количество гамильтоновых путей, имеющих a ровно посередине. Ищет n=47 за 6 часов, до этого растет примерно как (1.7)^n. К сожалению, память растет тоже экспоненциально (но медленнее, чем стандартный DP).
Самый лучший теоретический алгоритм основан на принципе inclusion/exclusion, он имеет сложность (2^n)*(n^3) при полиномиальной памяти, но он требует возведения матриц nxn в степень n, поэтому он на практике слишком медленный (реализация на питоне не доходит даже до n=30). Рано или поздно он обгонит по скорости все прочие алгоритмы, но, скорее всего, время работы будет превышать время существование вселенной.
Для этого алгоритма, правда, есть огромное поле оптимизаций (полное распараллеливание на 2^n умножений матриц, которые можно делать на GPU) - но по моим подсчетам, все равно будет слишком медленно, если только не найти эвристик, которые позволят не считать большую часть подмножеств.
Это не совсем задача коммивояжёра. Тут строятся все пути, включая и не проходящие через все вершины. Разнообразные тупики тоже допускаются.
Например, пусть у нас n=10. Тогда квадраты - это 4, 9, 16, а смежные числа -
1 -> 3, 8
2 -> 7
3 -> 1, 6
4 -> 5
5 -> 4
6 -> 3, 10
7 -> 2, 9
8 -> 1
9 -> 7
10 -> 6
Как минимум, мы видим, что граф многосвязный - есть изолированные островки {1, 3, 6, 8, 10}, {2, 7, 9} и {4, 5}.
Полный список самых длинных цепочек:
1, 3, 6, 10
1, 8
2, 7, 9
3, 1, 8
3, 6, 10
4, 5
5, 4
6, 3, 1, 8
6, 10
7, 2
8, 1, 3, 6
9, 7, 2
10, 6, 3, 1
Если избавиться от подцепочек и отзеркаливаний, то получим
8, 1, 3, 6, 10
2, 7, 9
4, 5
Зачем матрица с суммами i и j чисел, если требуется сумма соседних чисел и j=i+1?
К чему вообще такие сложности?
Может я чего не понял?
Квадрат натурального числа не будет больше чем 2n-1 значит можно взять цикл на round(sqrt(2n-1)/2)=m повторов и пробежаться по квадратам натуральных нечётных чисел в диапазоне от 3 до 2m+1.
For i:=1 to m
X:=(sqr((i*2)+1)-1)/2;
Print(X,X+1)
При n = 65535 получаем цикл на 128 операций.
Я тоже так сначала подумал. Фишка в том, что соседними числа должны быть не в диапазоне, а в найденной последовательности, на это намекает первая пара результата 16 и 9 на скриншоте.
Хорошо. Если нужны все возможные варианты пар чисел из диапазона 1..n, то дополним цикл следующими операциями
Y:=X+1;
repeat
Print (X,Y);
Print(Y,X);
Dec(X);
Inc(Y)
until (X>=1) & (Y<=n)
Цикл выдаст все возможные варианты пар чисел, сумма которых даёт квадрат натурального числа найденного в вышестоящем цикле.
Аналогичный алгоритм делается для нахождения пар чисел сумма которых равна квадрату чётного натурального числа, только Y:=Х;
В итоге затрат по памяти никаких, все вычисления выдают только правильные результаты, а значит и по времени затраты не велики.
Или я опять чего-то не понял? Тогда прошу привести контрпример в виде пары произвольных чисел от 1 до n, которые нельзя найти указанным способом.
А что если развернуть задачу в сторону суммы квадратов натуральных чисел?
1. Очевидно, что сумма последовательности чисел от 1 до n равна n*(n+1)/2. Сумма квадратов должна быть равна этой сумме или меньше неё на одно из чисел для нечётного n.
2. Количество квадратов известно - это n/2
3. Квадраты натуральных чисел можно вычислить даже без умножения как сумму натуральных нечётных чисел (ряд 1+3+5+7+9+11... на каждом шаге выдает как раз квадраты 4, 9, 16, 25, 36...). Заполняем до 2*n-1
Далее пытаемся заполнить сумму квадратами и проверяем, что используются все числа.
P.S. А вы заметили, что на скриншоте с результатами вторая последовательность - это первая, развёрнутая в обратную сторону?
кому эта хрень нужна? где ее применить в жизни?
Есть ли какой-нибудь изящный способ перечислить все наиболее длинные цепочки неповторяющихся чисел для произвольной матрицы смежности? Или для конкретно этой?
Не тупым перебором с последующей сортировкой и фильтрацией.
перечислить все наиболее длинные цепочки неповторяющихся чисел для произвольной матрицы смежности
Есть Динамическое Программирование (смотрите мой пост выше). Кроме этого остается перебор с отсечениями и различные его вариации.
Конкретно для этой матрицы смежности, возможно, могут быть более хитрые решения. Граф не очень плотный. Можно, например, посмотреть на компоненты двусвязности, вдруг граф распадается на путь и там понятно, где надо начать и закончить в каждой компоненте.
Начал тупо рисовать на бумаге. Связность графа образуется только при n=14. При n=15, 16, 17 появились гамильтоновы пути - наши решения. Однако при n=18..21 их снова нет. Интрига...
Если сформулировать задачу по другому - у вас есть граф, в котором вершины имеют значения от 1 до N, а ребра проходят между вершинами, в сумме дающими квадрат. В общем смысле, вы пытаетесь найти все гамильтоновы пути данного графа (но вы также должны доказать, что для конкретного числа в принципе есть такой путь, потому что это не гарантируется для графа, например для 14 или для 22).
Но даже поиск одного гамильтонова пути не эвристическими методами будет занимать много времени, как, например, задача на CodeWars: https://www.codewars.com/kata/5a667236145c462103000091 .
На нём, кстати, дается уточнение, что вы не решите эту задачу для чисел больше 50 в лоб. Т.е. вы не сможете алгоритмически найти ВСЕ такие пути в графе. А для маленьких чисел вы можете сделать обход в ширину для каждой вершины.
А не могли бы вы для джунов выложить тесты. Хоть на github.
Мой вариант кода
import scala.io.StdIn.readInt
val userInput = readInt.abs
val pairs: Seq[(Int, Int)] = for {
sq <- (2 to userInput).map(x => x * x)
if (sq <= 2*userInput - 1)
ps <- (1 to userInput).map(x => (x, sq-x))
if (ps._2 > 0) & (ps._1 != ps._2) & (ps._1 <= userInput & ps._2 <= userInput)
} yield ps
val matrix: Map[Int, Seq[Int]] = pairs.groupMap(_.1)(._2)
def findAllChains(ms: Map[Int, Seq[Int]]): List[Seq[Int]] = {
def loop(cursor: Int, acc: Seq[Int] = Nil, nums: Seq[Int]): List[Seq[Int]] = {
val numsToChain = ms(cursor).filter(x => nums.contains(x)).toList
if numsToChain.isEmpty then List(acc)
else
numsToChain.flatMap(x => loop(x, acc ++ Seq(x), nums.filter(_ != x)))
}
val allNums = ms.keys.toList
allNums.flatMap(x => loop(x, Seq(x), allNums.filter(_ != x)))
}
findAllChains(matrix).filter(_.size == userInput).foreach(println)
Поиск всех последовательностей чисел от 1 до n, где сумма соседних чисел является квадратом