Страницы

Поиск по вопросам

пятница, 12 июля 2019 г.

Есть ли смысл использования ИНС? - обобщение задачи о ранце

Имеется список/массив произвольной длины с целочисленными значениями. Необходимо составить из элементов минимальное количество групп, в которых сумма чисел не больше заданного значения. Есть написанный алгоритм, который сортирует и формирует данные группы, но он достаточно громоздкий и может медленно работать в случае большого количества данных. Есть ли смысл для решения использовать искусственную нейронную сеть? Возможно ли ее натренировать, если входные данные и максимальная сумма чисел в группе может быть любой?
Пример: Входные данные: Список чисел: [6, 1, 6, 2, 4, 3, 1, 2, 2, 3, 2]. Максимальная сумма группы: 10. Задача: сформировать минимальное количество групп, все группы должны быть максимально заполнены, кроме одной (минимальный остаток). Правильный ответ: [1, 1, 2, 6], [2, 2, 6], [3, 3, 4], [2] Решение: Сумма чисел в списке равна 32. Соответственно, минимальное число групп - 4; минимальный остаток - 2; 3 группы чисел, где сумма чисел равна 10. Проблема в том, что таких чисел может быть очень много и не все можно идеально разложить по группам. Задачу я решил без каких-либо шаблонов программирования. Мне просто интересны возможность и целесообразность использования ИНС или чего-либо подобного для более качественного решения задачи.


Ответ

Рассматриваемая задача - обобщение известной задачи о ранце, для решения которой ИНС обычно не применяют.
В то же время можно порекомендовать "жадные" стратегии, не использованные в ОП, при которых заполнение массивов ведётся перебором в порядке убывания элементов.
Вариант реализации (C#):
public static void Move(ref int[] from, ref int[] to, int index) { int lenfrom = from.Length, lento = to.Length;
Array.Resize(ref to, lento + 1); to[lento] = from[index]; for (int i = index; i < lenfrom - 1; i++) from[i] = from[i + 1]; Array.Resize(ref from, lenfrom - 1); }
public static void ArShow(string txt, int[] ardesc, int[] res) { Console.Write(txt + "
last group: "); foreach (int val in res) { Console.Write(" " + val); } Console.Write("
data array: "); foreach (int val in ardesc) Console.Write(" " + val); Console.WriteLine(); }
public static void Knapsack(int sum, ref int[] ardesc, ref int[] res) { int ind = 0, sres = res.Sum(), arlen = ardesc.Length, reslen = res.Length; int[] newdesc, newres;
Array.Copy(ardesc, newdesc = new int[arlen], arlen); Array.Copy(res, newres = new int[reslen], reslen); foreach (int value in ardesc) { if (sum == sres) break; if (sum >= sres + value) { Move(ref newdesc, ref newres, ind); Knapsack(sum, ref newdesc, ref newres); break; } ind++; } ardesc = newdesc; res = newres; }
static void Main(string[] args) { int[] arrdesc, arr = new int[] { 6, 1, 6, 2, 4, 3, 1, 2, 2, 3, 2 }; int rquant, arrlen = arr.Length, sum = 10; int[][] result = new int[0][];
Array.Copy(arr, arrdesc = new int[arrlen], arrlen); Array.Sort(arrdesc); arrdesc = arrdesc.AsEnumerable().Reverse().ToArray(); Console.Write("
sum = {0}
issue array: ", sum); foreach (int val in arr) Console.Write(" " + val); Console.WriteLine("

***result.Length = " + result.Length); Console.Write("sorted array: "); foreach (int val in arrdesc) Console.Write(" " + val); Console.WriteLine(); while (arrdesc.Length > 0) { rquant = result.Length; Array.Resize(ref result, rquant + 1); result[rquant] = new int[0]; Knapsack(sum, ref arrdesc, ref result[rquant]); ArShow("
*** result.Length = " + result.Length, arrdesc, result[rquant]); } }
Результат:
sum = 10 issue array: 6 1 6 2 4 3 1 2 2 3 2
***result.Length = 0 sorted array: 6 6 4 3 3 2 2 2 2 1 1
*** result.Length = 1 last group: 6 4 data array: 6 3 3 2 2 2 2 1 1
*** result.Length = 2 last group: 6 3 1 data array: 3 2 2 2 2 1
*** result.Length = 3 last group: 3 2 2 2 1 data array: 2
*** result.Length = 4 last group: 2 data array:

Комментариев нет:

Отправить комментарий