如何找到最小值而不必尝试所有可能性

我正在试图编写一个程序，（用 Lua 编写，但我想这更多是一个数学问题），计算一组数字之间的总距离，并且对于某些数字有两个或三个不同的可能性。

例如，一组数字是：2、5、0、1。在这种情况下，距离的总和为 9。（5-2 + 5-0 + 1-0） 第一行的备选项为：5、-、3、2。 第二行备选项为：3、-、-、3 两行之间距离最小的组合为：5、5、3、3，距离总和为 2。

我的第一次尝试是编写一个尝试所有可能迭代的程序，但是对于大约 40 个数字的集合，有太多的可能性，以至于我的电脑崩溃了…

这是那个版本的代码，它首先创建所有不同的可能性，然后计算差异并将它们放入第 0 列。之后，我可以轻松地找到最小值并看到产生那个值的数字组合。

local table1 = {2, 5, 0 ,1}
local table2 = {5, nil, 3, 2}
local imax = 1
local solution = {}
local answer = table1[1]

for x = 1,#table1 do
    solution[x]={}
    for i= 1, (2^imax)/2 do
        solution[x][i] = table1[x]
    end
    if table2[x] ~= nil then -- there is an alternative number
        for y = 1, x-1 do -- copy all the previous table entries except the last one
            for j = ((2^imax)/2)+1, 2^imax do -- the number of new rows increases exponentially
                solution[y][j] = solution[y][j-imax]
            end
        end
        for j = ((2^imax)/2)+1, 2^imax do -- create the new table entry with the alternative number
            solution[x][j] = table2[x]
        end
        imax = imax + 1 -- this number is to remind how many alternative numbers where found
    end
end

solution[0]={}
for x = 1, #table1 do
    for i = 1, (2^imax)/2 do
        if x < #table1 then answer = math.sqrt((solution[x+1][i]-solution[x][i])^2) else answer = 0 end
        if solution[0][i] == nil then solution[0][i] = answer else solution[0][i] = solution[0][i] + answer end
    end
end

在阅读了有关动态编程的资料之后，我编写了这个程序的一个新版本。它计算差异的最小总和，但我还想知道那个总和的路径（数字的组合）…还有工作要做…

local table1 = {2, 5, 0 ,1}
local table2 = {5, nil, 3, 2}
local solution = {}
local smallestsolution = {}
solution[1]={}
solution[2]={}
solution[3]={}
solution[4]={}

for i = 1, (#table1-1) do
    solution[1][i] = math.sqrt((table1[i+1]-table1[i])^2)
    if table2[i] ~= nil then solution[2][i] = math.sqrt((table1[i+1]-table2[i])^2) end
    if table2[i+1] ~= nil then solution[3][i] = math.sqrt((table2[i+1]-table1[i])^2) end
    if table2[i] ~= nil and table2[i+1] ~= nil then solution[4][i] = math.sqrt((table2[i+1]-table2[i])^2) end
end

for i = 1, (#table1-1) do
    smallestsolution[i]=100000
    for j = 1, 4 do
        if solution[j][i] ~= nil and solution[j][i] < smallestsolution[i] then smallestsolution[i]=solution[j][i] end
    end
end

local smallestsum = 0
for i = 1, (#table1-1) do
    smallestsum = smallestsum + smallestsolution[i]
end

谢谢，

Emile