Представляю Вашему вниманию несколько тестовых задач, которые имеют, как мне кажется, прямое отношение к ИИ. Их можно достаточно строго сформулировать (формализовать), однако стандартного способа их решения не существует (или я о нем не знаю). Мне кажется странным, что этими задачами мало занимаются.

Задача 1.

Существует некоторая, неизвестная «интеллектуальному агенту», функция F(X,Y). Здесь X и Y – вектора (вообще говоря, разной размерности). Агенту последовательно предъявляют на вход различные вектора Х_i.  Агент «в ответ» дает вектора Y_i (на ответ агента накладываются некоторые покомпонентные ограничения – каждая компонента вектора Y_i должна принадлежать некоторому), после чего агенту сообщают значение F_i = F(Х_i, Y_i). Задача агента – постепенно научиться максимизировать эти F_i выбором подходящих Y_i.

Считается, что функция F(X,Y) «достаточно гладкая» (но, возможно, имеет разрывы). Однако пользоваться этим фактом можно только для ускорения обучения (то есть, агент должен уметь работать и со сложными функциями, но, возможно, менее эффективно).

Если это поможет решению, можно считать, что компоненты вектора Х также ограничены.

Задача 1*. (Более сложная модификация задачи 1)

О функции F(X,Y) дополнительно известно, что она обладает некими инвариантами: т.е. есть такие преобразования G₁: X → X, и G₂: Y → Y, что F(G₁(X), G₂(Y)) = F(X,Y) ± ε, где ε – некоторое небольшое число. Возможно, пара (G₁, G₂) с такими свойствами не единственна.

Требуется построить алгоритм, использующий этот факт при решении задачи 1.

Задача 2.

(Возможно, решение этой задачи даст идеи, необходимые для решения задачи 1*)

Даны N пар векторов (X₁,Y₁), … (X_N,Y_N). Требуется найти преобразование F: X → Y такое, что равенство F(X_i) = Y_i выполнено для как можно большего количества индексов i от 1 до N. При этом предполагается, что это равенство не может быть выполнено для всех i от 1 до N (например, X₁ = X₂, но Y₁ ≠ Y₂).

Как и в задаче 1, считается, что существует «достаточно гладкая» функция F с таким свойством. Однако пользоваться этим фактом можно только для ускорения обучения (то есть, алгоритм должен работать и в том случае, когда функция с такими свойствами оказывается очень сложной, но, возможно, гораздо менее эффективно).