Существует ли алгоритм, восстанавливающий неизвестную функцию из множества векторов входных и выходных значений?

 

К примеру, есть неизвестная функция f(x) = y, для неё известна таблица:

f(0) = 0;

f(1) = 2;

f(2) = 4;

На основе этих данных можно предположить, что f(x) = 2x. Так вот, существует ли алгоритм, который по конечному набору векторов входных и выходных значений мог бы выдать функцию, верную для всех этих векторов?

Провести полином нужного порядка через известные точки, что ли? Ну так это не алгоритм, это аналитически решаемая задача. Тот же wolframalpha это спокойно делает.

 

Вообще, как бы очевидно, что для любого набора точек таких функций бесконечно много. Так что очень многое зависит от того, в каком виде искать и какие нужны ограничения.

Не совсем, я привёл простой пример. Скажем так, нужна достаточно оптимальная функция. Притом, может быть множество входных аргументов. К примеру f(x1,x2,...,xN) = y. Или результат не вычисляется явно, типа f(5678) = 3, f(7890) = 4, f(5326) = 1 (подсчитывает количество замкнутых контуров в числе) - т.е. тут уже нужен алгоритм, как я понимаю, и надо его найти, вычислить. Возможно ли это для общего случая, когда мы не знаем в чём состоит задача, а знаем только входные и выходные данные?

Нет, в общем случае эта задача не решается.

Возможно ли это для общего случая, когда мы не знаем в чём состоит задача, а знаем только входные и выходные данные?

Вообще, как бы очевидно, что для любого конечного набора точек таких функций бесконечно много.

 

Сможете сформулировать критерий отсечения неподходящих или сравнения между собой - будет о чем разговаривать.

А вообще, вы мне очень вот эту тему напомнили.

Критерий сравнения - количество операций, соответственно, чем их меньше, тем лучше. Для моего первого примера можно сказать, что f(x) = 2x, или что f(x) = x^2 + x * sin (pi/2 * x) - оба варианта верны, но первый лучше, потому как количество операций меньше. Насколько я понимаю, задачу можно решить перебором (который становится неэффективным очень быстро), а есть ли более оптимальный алгоритм?

Т.е. для таблицы

f(0) = 0;

f(1) = 2;

f(2) = 4;

f(3) = 6;

Алгоритм должен выдать ответ f(x) = 2x, а если мы добавим

f(4) = 16;

То должен уметь выдать что f(x) = x^2 + x * sin (pi/2 * x), ну или хотя-бы:

для x=0..3, f(x) = 2x;

для x=4, f(x) = x^2; (или хотя-бы = 16)

И опять таки, мне не нужно решение с точки зрения математика (т.е. получение набора функций и условий их применения) или функционального программирования, а достаточно получить решение точки зрения бухгалтера или же императивного программирования, оптимизированное по времени исполнения.

Полином нужной степени чем не угодил?

А разве полином нужной степени решит задачку с подсчётом замкнутых контуров в числе? С другой стороны, алгоритм:

1. Разбить число на цифры

2. 1..5,7 = 0; 0,6,9 = 1; 8 = 2

3. Просуммировать результат

По сути нужен алгоритм построения алгоритмов =)

И опять таки, мне не нужно решение с точки зрения математика (т.е. получение набора функций и условий их применения) или функционального программирования, а достаточно получить решение точки зрения бухгалтера или же императивного программирования, оптимизированное по времени исполнения.

Вам уже указали, что это приближение полиномом. Выберите нужную степень, нужную точность, и вперед. С задачей даже Excel справляется, не говоря про более заточенные тулзы.

Аналитического решения без дополнительной априорной инфы не существует. Только случайное совпадение в том случае, когда исходная функция сама полином.

 

Полином хорош для простейшего примера, а если f(x, y, z) = x (z) y, где z = {0 = +, 1 = -, 2 = *, 3 = /}, но мы не знаем самой функции, а только некоторый набор входных и выходных данных?

...а если f(x, y, z) = x (z) y, где z = {0 = +, 1 = -, 2 = *, 3 = /}, но мы не знаем самой функции, а только некоторый набор входных и выходных данных?

Что вы тут написали не понял даже я, куда уж там алгоритму.

 

В общем, насколько я вижу, задача эквивалентна написанию ИИ. Если не по сути, то уж по сложности точно. И перспективы такие же.

Да, я понимаю, что в общем случае задача пока не решаема. Но если вернуться к той теме, которую вам напомнил мой вопрос. Предположим, что нужно решить вот эти самые задачки на продолжение ряда. По сути надо выяснить что может являться входными данными, что выходными и найти самую простую из возможных зависимостей между ними. Эта задача теоретически достаточно легко решается перебором всех возможных сочетаний входных значений и простых операций над ними. Но неужели не существует более оптимального алгоритма?

Эта задача теоретически достаточно легко решается перебором всех возможных сочетаний входных значений и простых операций над ними.

Ну как бэ нет, не то что нелегко, она вообще так не решается :)

Почитайте про интерполяцию... Линейными функциями, полиномами, синусами или чем вам ещё понравится.... Простейший пример - ломаная, соединяющая соседние результаты.