Нужно признать, что алгоритмические задачи — одна из излюбленных тем программистов. Это такой тип задач, которые можно найти на 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}.
На решение этой задачи у меня ушло два часа.
Вот в чем загвоздка:
- Если сумма S — нечетное число, тогда ответом будет НЕТ
- Если сумма 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]]Заключение
Все то, что я не мог решить в течение нескольких часов, алгоритму удалось сделать всего за секунду. Для этого потребовалось всего несколько образцов решений, а остальным занялся сам алгоритм. Он оказался умнее человека.
Читайте также:
- Блокчейн и искусственный интеллект - мощный тандем
- Как ИИ влияет на развитие NFT
- SpineNet: нетрадиционная архитектура backbone-сети от Google Brain
Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Mihail-Iulian Pleșa: Smarter than me
