Испытаем ИИ в решении логических задач



Книга Испытаем ИИ в решении логических задач

Нужно признать, что алгоритмические задачи  —  одна из излюбленных тем программистов. Это такой тип задач, которые можно найти на CodeChef, Codeforces, на HackerRank и на прочих подобных сайтах. В таких задачах нужны не столько прикладные знания, сколько наличие развитого логического мышления. Даже если вы не любитель соревнований по программированию, иногда стоит тренироваться на подобных задачках, чтобы поддерживать ум в хорошей форме.

Потерянные два часа

Какое-то время назад на CodeChef появилась простая с виду задачка под названием “Две группы”.

Вот в чем ее суть:

Мультимножество S содержит A копий целого числа 1, B копий целого числа 2 и C копий целого числа 3. Нужно определить, можно ли разделить S на две группы мультимножеств так, чтобы сумма первой группы была равна сумме второй группы.

К примеру, если в мультимножестве S находятся такие числа: {1, 1, 1, 2, 2, 2, 3, 3, 3, 3}, то ответ ДА, потому что можно разделить S на {1, 1, 2, 2, 3} и на {1, 2, 3, 3}.

На решение этой задачи у меня ушло два часа.

Вот в чем загвоздка:

  1. Если сумма S  —  нечетное число, тогда ответом будет НЕТ
  2. Если сумма S  —  четное число, тогда: 
  • нужно поместить A/2 значений 1 в первую группу и A/2 значений 1 во вторую группу. Если A  —  четное число, то нужно поместить три значения 1 в первую группу и одно значение 3 во вторую группу
  • нужно поместить B/2 значений 2 в первую группу и A/2 значений 2 во вторую группу. Если B  —  нечетное число, то нужно поместить два значения 1 в первую группу и одно значение 2 во вторую группу
  • нужно поместить C/2 значений 3 в первую группу и C/2 значений 3 во вторую группу. Если C  —  четное число, то нужно поместить одно значение 1 и одно значение 2 в первую группу, а также одно значение 3 во вторую группу.

Компилятор CodeChef в ответ на этот алгоритм выдал сообщение об ошибке.

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

Решение показалось довольно странным:

def solve(a, b, c):
tot = a + 2*b + 3*c
if (tot % 2) != 0:
return 0
if a == 0 and c == 0 and (b % 2) != 0:
return 0
if (a == 0 and b == 1) or (a == 1 and b == 0):
return 0
return 1

ИИ умнее человека?

После всей этой истории я решил, что интересной задумкой будет дать компьютеру решить эту задачу самостоятельно.

Идея была в том, чтобы внедрить алгоритм машинного обучения, который бы научился решать такой тип задач. Как и любому другому алгоритму машинного обучения, ему нужен набор данных, на котором можно начать обучение. Для этого был написан генератор случайных мультимножеств:

def generate_random_data(limit, max):
X = []
y = []
for i in range(limit):
a = randint(1, max)
b = randint(1, max)
c = randint(1, max)
tmp = [a, b, c , a, 2*b, 3*c, a + 2*b + 3*c]
X.append(np.array(tmp))
y.append(np.int(solve(a,b,c)))
X = np.array(X)
y = np.array(y)
return X, y

Выбранный алгоритм был довольно простым  —  метод k-ближайших соседей (вот как он выглядит):

X, y = generate_random_data(1000000, 50)
scaller = StandardScaler()
scaller.fit(X)
X = scaller.transform(X)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33)
clf = KNeighborsClassifier(1)
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
acc = accuracy_score(y_test, y_pred)
print(acc)
print(confusion_matrix(y_pred, y_test))

Точность модели алгоритма оказалась в районе 99%. А вот как выглядела матрица несоответствий:

[[164421    726]
[ 798 164055]]

Заключение

Все то, что я не мог решить в течение нескольких часов, алгоритму удалось сделать всего за секунду. Для этого потребовалось всего несколько образцов решений, а остальным занялся сам алгоритм. Он оказался умнее человека.


Перевод статьи: Mihail-Iulian Pleșa: Smarter than me

17   0  
    Ничего не найдено.

Добавить ответ:
Отменить.