Ускорение поиска проблем N (P) - Задача суммы квадратов
Мне было интересно, может ли кто-нибудь помочь мне найти способы ускорить небольшую программу, над которой я работал.
Задача - математическое упражнение, которое называется «Сумма квадрата» (https://youtu.be/G1m7goLCJDY).).
Итак, вы берете список непрерывных целых чисел, начиная с 1 до N, и смотрите, можете ли вы изменить их порядок так, чтобы сумма каждой пары составляла квадрат.
Так, например:
1-3-6-10-15-
или
1-15-10-6-3-13-12-4-5-11-14-2-7-9-
Хитрость заключается в том, чтобы использовать все числа в домене [1, N]. Очевидно, что вы можете найти только одно решение, доказывающее, что есть решение для [1, N], или вы можете показать все решения для этой области. В последнем случае вы получите обратное решение для каждого решения, очевидно, плюс вы можете получить так называемые циклические решения, где начало и конец также составляют квадрат.
Теперь увеличение N (после 23, кажется, есть решение для каждого N - не доказано), экспоненциально увеличивает число возможных ветвей или путей, которые вы можете попробовать.
Сначала моей программой были простые циклы, которые проверяли практически все параметры. Это означало, что мой компьютер (простое ядро i9) начал бороться (обработка> 1 часа) примерно при N = 30. Затем я изменил метод и сначала создал таблицу или матрицу, содержащую только те числа, которые будут создавать квадрат для каждого числа [1, N]. Таким образом, для N = 15 (первое возможное N с решением) вы получите:
Для N = 15 возможны квадраты: 4, 9, 16, 25
1 - 3, 8, 15
2 - 7, 14
3 - 1, 6, 13
....
15 - 1, 10
Затем я просмотрел эту таблицу, чтобы найти возможные решения. Если путь тупиковый, программа откатывается до тех пор, пока не появится другая ветвь, не попробует ее, откат и т. Д.
Это заняло у меня примерно N = 50, прежде чем это заняло слишком много времени (> 1 часа) на мой вкус.
До этого я работал со списками (используя C #), поэтому я попробовал HashSets, который поднялся примерно до N = 70. Теперь я, похоже, застрял.
Я либо:
1) нужно найти другую функцию, которая может быстрее обрабатывать списки и пути, или
2) придумать совершенно иной подход к математическому решению этого
3) увеличить вычислительную мощность
Есть ли у кого-нибудь более умные предложения, чем те, которые я думал о себе?
Мой код (C #):
using System;
using System.Collections.Generic;
namespace SumSquare
{
public class CalculateHash
{
List<List<int>> matrix = new List<List<int>>();
List<int> squares = new List<int>();
List<int> branch = new List<int>();
HashSet<int> defaultList = new HashSet<int>();
HashSet<int> worklist = new HashSet<int>();
int currentN, currentSet, currentIndex; //, prevIndex;
int max;
List<int> prevIndexSet = new List<int>(); //Holds prevSet index
bool going, going2;
DateTime startTime;
int successes = 0;
int cyclic = 0;
TimeSpan elapsed;
public void Calculate(int maxNum)
{
max = maxNum;
squares = FillSquares(max);
matrix = CreateMatrix(squares, max);
startTime = DateTime.Now;
for (int i = 1; i <= max; i++)
{
branch.Clear();
worklist.Clear();
branch.Add(i);
worklist = FillDefaultList(max);//Fill with all but current start number
worklist.Remove(i);
currentIndex = 0;
currentN = matrix[i][0]; //Get first element
currentSet = i; //remember current set, starting number
going = true;
while (going)
{
if (worklist.Contains(currentN))//Is this number still available?
{
branch.Add(currentN); //add currentN
worklist.Remove(currentN);//Clean up worklist
if (worklist.Count == 0) //All numbers processed! HIT
{
successes++;
ShowSucces();
//to quit at the first success
//going = false; //Quit at first success
//i = max + 1; //quit programm
}
prevIndexSet.Add(currentIndex);
currentSet = currentN;
currentN = matrix[currentSet][0];
currentIndex = 0;//reset for next Set
}
else //number already in use!
{
currentIndex++;
going2 = true;
if (currentIndex == matrix[currentSet].Count) //Used up all the numbers in this set?
{
while (going2)
{
int prevSet = branch[branch.Count - 1];//get the last number added at which this branch halted
branch.RemoveAt(branch.Count - 1); //remove this last number
//We need to add the number prevSet back into the workList BUT
//it needs to go at the correct location!! To keep the numbers in order
worklist.Add(prevSet); //Add the number back
if (branch.Count == 0) //We've exhausted all the possible paths starting with number (i)
{
going2 = false; //break out if this while
going = false; //break out of parent while
}
else
{
currentSet = branch[branch.Count - 1]; //Get the last number of the previous set
currentIndex = prevIndexSet[prevIndexSet.Count - 1] + 1; //Get the position in that set whee we last stopped and get the next position
prevIndexSet.RemoveAt(prevIndexSet.Count - 1);//remove that index reference
if (currentIndex < matrix[currentSet].Count) //No more numbers in this set
{
currentN = matrix[currentSet][currentIndex]; //carry on
going2 = false;
}
}
}
}
else
{
currentN = matrix[currentSet][currentIndex]; //Get the next number in this Set
}
}
}
}
TimeSpan elapsedTime = DateTime.Now - startTime;
Console.WriteLine("Time elapsed: " + elapsedTime.TotalSeconds);
Console.WriteLine("Number of successes: " + (successes * 0.5));
Console.WriteLine("Number of cyclic successes: " + cyclic);
Console.ReadKey();
}
List<List<int>> CreateMatrix(List<int> s, int m)
{
//This creates a 2-dimensional List, First dimension is [1,max], Second dimension the number need to get a sum when added to the current number
List<List<int>> t = new List<List<int>>();
t.Add(new List<int>()); //Element 0 is empty
for (int i = 1; i <= max; i++)
{
List<int> tt = new List<int>();
for (int j = 0; j < s.Count; j++)
{
int difference = s[j] - i;
if ((difference > 0) && (difference <= max) && difference != i) //Needs to be >0 and <=max
{
tt.Add(s[j] - i); //Now add the result: Square - currentINT
}
}
t.Add(tt); //Now stuff it into the parent List where INT=1 is Index=0
}
return t;
}
HashSet<int> FillDefaultList(int maxInt) //Fills a List with [1,max] integers
{
HashSet<int> l = new HashSet<int>();
for (int i = 1; i <= max; i++)
{
l.Add(i);
}
return l;
}
List<int> FillSquares(int max) //Creates a list of the squares of all values from [2,max] below the max + max-1 sum
{
List<int> l = new List<int>();
int maxSum = max + (max - 1);
for (int i = 2; i < max; i++)
{
if ((i * i) <= maxSum)
{
l.Add(i * i);
}
}
return l;
}
List<int> RemoveElement(List<int> list, int number)
{
List<int> l = new List<int>();
for (int i = 0; i < list.Count; i++)
{
if (list[i] != number)
{
l.Add(list[i]);
}
}
return l;
}
HashSet<int> FillWorklist(HashSet<int> defList, int cNum)
{
HashSet<int> l = defList;
l.Remove(cNum);
return l;
}
void ShowSucces()
{
Console.Write("Found a path with starting number: " + branch[0]);
if (squares.Contains(branch[0] + branch[branch.Count - 1])) //Is it cyclic?
{
cyclic++;
Console.WriteLine(" - This branch is cyclic! ");
}
else
{
Console.WriteLine();
}
for (int i = 0; i < max - 1; i++)
{
Console.Write(branch[i] + ",");
}
Console.WriteLine(branch[max - 1]);
}
}
}