algorithm - 神经网络能否找到固定大小列表的第 i 个排列？

Question

简单介绍

神经网络能否模拟阶乘分解(或其他一些方法)以提供给定排列唯一索引的列表排列？

申请

我有一个包含 10 件事的 list ，它们是什么无关紧要。我关心的是我的 10 个东西可以放入 3628800(或 10!)个唯一顺序，因为这样我就可以使用无符号整数和阶乘分解来表达我的 10 个东西的任何列表顺序:

Order 0: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Order 1: 0, 1, 2, 3, 4, 5, 6, 7, 9, 8
Order ....
Order 3628799: 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

这允许对我的 10 件事的不同列表顺序进行并行分布分析。

一个常见的例子是旅行商问题:

1. I give 500 different computers each a range of unsigned integers:
   0    -> 7257  for computer 0, 
   7257 -> 14516 for computer 1, 
   etc.

2. Each computer first calculates the list order from it's unsigned integer 
   index by using factorial decomposition.
   ie. Order 1 -> 0, 1, 2, 3, 4, 5, 6, 7, 9, 8

3. The distance between the cities placed in the order described is calculated.

4. The shortest distances from each computer is collected, and the shortest 
   of those is taken. Leaving us with a single unsigned integer index that 
   describes the shortest possible permutation of cities.

相同的过程可用于解决几乎任何有边界的误差表面，通常提供的计算能力远远超过可行的计算能力。

递归算法解决方案

我们可以使用阶乘分解 (outlined here in php) 计算任何固定大小列表的第 N 次排列(假设我们需要大整数支持更大的列表)，为了清楚起见，在 javascript 中提供:

function ithPermutationOfNElements (n, i)
{
   var j, k = 0;
   var fact = [];
   var perm = [];

   // compute factorial numbers
   fact[k] = 1;
   while (++k < n)
      fact[k] = fact[k - 1] * k;

   // compute factorial code
   for (k = 0; k < n; ++k)
   {
      perm[k] = Math.floor(i / fact[n - 1 - k]);
      i = i % fact[n - 1 - k];
   }

   // readjust values to obtain the permutation
   // start from the end and check if preceding values are lower
   for (k = n - 1; k > 0; --k)
      for (j = k - 1; j >= 0; --j)
         if (perm[j] <= perm[k])
            perm[k]++;

   return perm;
}
console.log(ithPermutationOfNElements(4, 23)); // [ 3, 2, 1, 0 ]

神经网络解决方案？

在给定 i 的情况下，任何神经网络架构和训练组合都可以模拟此函数吗？因为它只有输入神经元和 n 个输出神经元，代表排列的每个元素？

Answer 1

A neuron can operate as a logic gate ，因此神经网络可以执行计算机可以执行的任何计算。然而，从这个意义上讲，它只是使用高级代码低效地模拟逻辑门，因此不是解决此问题的好方法。

一般来说，神经网络适用于“真实”或“自然”数据。它们通常也使用 float 而不是整数进行操作。因此，如果有一种模式需要学习，神经网络可能会学习它，但您将获得的输出答案将是例如 0.783267。然后您可以将其反规范化为 89743，但它不太可能完全正确。根据您的要求，正确答案的一个整数是完全错误的。

相比之下，对于特定图像的人脸识别神经网络返回 0.787 或 0.786，两者都可以被认为是正确的。

您的问题更适合传统的程序代码解决方案，每个输入只有一个正确答案。通常在 AI 中，您正在寻找特定范围或概率分布内的正确答案。

关于使用神经网络实现算法:
你可以有许多神经元充当逻辑门，所以现在你有神经元与非门/触发器等充当加法器/乘法器/锁存器等，直到你基本上构建了一个图灵机，但明确使用高级代码。它绝不会像普通的神经网络，因为大多数人工智能世界都在使用它们。此外，您面前已经有了一台非常好的图灵机。

这是 Matlab 中神经网络与门的代码。无需培训。我使用 configure 而不是 train，并且只是手动设置权重。因此，创建其他逻辑类型，您可以构建一个完整的图灵机。

and = feedforwardnet(1);

truthTable = [0 0 1 1; 0 1 0 1];
and_out = [0 0 0 1];

and = configure(and, truthTable, and_out);

vals = [-2 -2 -1  2 0];

and.IW{1} = vals(1:2); % input1 to hidden, input2 to hidden
and.LW{2,1} = vals(3); % hidden to output
and.b{1} = vals(4);     % bias to hidden
and.b{2} = vals(5);     % bias to output

y = sim(and, truthTable)
round (y)
mse = mean ((y - and_out) .^ 2)


y =
    0.0000    0.0180    0.0180    0.9820
ans =
     0     0     0     1
mse =
   2.4263e-04