Какая?
Задачки, загадки, головоломки Диалога
- Автор темы Стержень
- Дата начала
- Ответы 641
- Просмотры 30 тыс.
Для тех, кто устал от политики, политических баталий и сопутствующего негатива, я открываю ресурс нового формата.
Наш новый, мирный, комфортный, домашний, интересный, творческий
Форум БЕЗ ПОЛИТИКИ.
Гостям форум недоступен, но после регистрации вас ждёт уютная душевная атмосфера и интересное дружелюбное общение.
Наша закрытость - наша свобода. Стучите - и вам откроют.
Похоже, это пипец какая сложная задача. Во всяком случае, я не нашёл простого способа её решить. И не стал заморачиваться, а написал вчера программу для подбора искомых значений методом генетических алгоритмов. Написание основной части заняло что-то меньше часа - это включая многократные запуски, наблюдения и исправления.
И потом несколько часов заняли многократные запуски и то, что можно назвать подбором настроек. То есть, основная часть уже работала, без ошибок и не требовала изменений, но нужно было утрясти некоторые нюансы.
Первой моей ошибкой была попытка поиска в дробных числах. Сначала с точностью до 0.01 - и программа действительно быстро находила очень близкие варианты, но каждый раз "застревала" в какой-то области, где немножечко недотягивала до точного решения.
Вот моё первое почти-решение:
0 | -5,16 | -4 | x1 = 4 |
10,32 | -20,05 | 17,73 | x2 = 8 |
9 | 33,21 | 7,73 | x3 = 8,001003 |
| y1 = 9 | y2 = 8 | y3 = 6 |
Для получения этого решения программа непрерывно работала что-то более получаса и за это время сменилось чуть более 35000 поколений.
Моя прога обсчитывает популяцию из 300 членов. Каждый член популяции кодируется цепочкой из 9 чисел, а его выживание зависит от того, насколько близкий к искомому результат дают эти числа. Каждый раз 100 лучших выживают и дают 200 потомков, так сменяются поколения.
Затем я попробовал поиск с точностью до 0.1, тоже прекратил работу программы после более 35000 поколений, на этот раз решение получилось чуть менее точным:
-36,2 | 0 | -4 | x1 = 4 |
-45,3 | 35 | 18,3 | x2 = 8 |
8,2 | -27 | 8,3 | x3 = 7,996296 |
| y1 = 8,999117 | y2 = 8 | y3 = 6 |
Обнаружив, что поиск в дробных числах не приходит к точному решению, я таки решился поискать в целых. Не делал этого сразу, потому что считал, что метод генетических алгоритмов будет неэффективен для случая, когда значения можно подбирать не постепенно, а только резкими "прыжками". Однако, внезапно получилось очень даже хорошо. Видимо, получилось потому, что изменчивость оказалась достаточно хорошей, так как внесение мутаций в цепочку из 9 цифр может давать большое количество разных вариантов.
Итак, моё первое точное решение:
Итак, моё первое точное решение:
5 | 1 | 1 | x1 = 4 |
-5 | 5 | 8 | x2 = 8 |
10 | 2 | 3 | x3 = 8 |
| y1 = 9 | y2 = 8 | y3 = 6 |
При том, что для нахождения каждого решения требовалось около получаса непрерывной работы программы, на самом деле, на то, чтобы прийти к первому точному ответу понадобилось что-то более трёх часов. Это те самые "настройки" - то есть, время ушло на то, чтобы понять, как лучше сформировать начальную конфигурацию и как организовать механизм мутаций, чтобы решение не растягивалось на долгие часы, а чтобы шло достаточно быстрое приближение к результату и не зависало бы где-то в его окрестностях, а приходило бы к точному решению.
Замечу, что решение задачи методом генетических алгоритмов вовсе не похоже на моделирование биологической эволюции. Потому что, если мы моделируем, то мы подсматриваем механизмы мутаций и прочего у природы и наблюдаем то, что получается. И если получается не какая-то жесть, а какое-то шевеление похожее на правду, то нас это устраивает. Я, правда, не знаю такого, чтобы кто-то именно пытался бы моделировать биологическую эволюцию. Обычно это просто незачем, потому что эволюция даже простейших бактерий достаточно сложна для моделирования, зато её прекрасно можно наблюдать в лабораторных условиях и даже выводить новые виды бактерий.
А мне, раз уж я решаю задачу, важно не просто обеспечить "похожие на правду" механизмы эволюции, а добиться, чтобы они приходили к точному решению. Заяц на поляне не будет горевать от того, что он получился не идеально приспособленным. Более приспособлен, чем его менее удачные родственники - и ладно, этого вполне достаточно для успешного продолжения рода. Ну а мне нужно именно точное решение.
Замечу, что решение задачи методом генетических алгоритмов вовсе не похоже на моделирование биологической эволюции. Потому что, если мы моделируем, то мы подсматриваем механизмы мутаций и прочего у природы и наблюдаем то, что получается. И если получается не какая-то жесть, а какое-то шевеление похожее на правду, то нас это устраивает. Я, правда, не знаю такого, чтобы кто-то именно пытался бы моделировать биологическую эволюцию. Обычно это просто незачем, потому что эволюция даже простейших бактерий достаточно сложна для моделирования, зато её прекрасно можно наблюдать в лабораторных условиях и даже выводить новые виды бактерий.
А мне, раз уж я решаю задачу, важно не просто обеспечить "похожие на правду" механизмы эволюции, а добиться, чтобы они приходили к точному решению. Заяц на поляне не будет горевать от того, что он получился не идеально приспособленным. Более приспособлен, чем его менее удачные родственники - и ладно, этого вполне достаточно для успешного продолжения рода. Ну а мне нужно именно точное решение.
- увидев это решение, первое что я подумал: "ну надо же, умник, придумавший задачу, ещё, блин, вставил отрицательное число, чтобы усложнить решение - типа, догадайтесь, что числа решения могут быть и отрицательными".
Но, всё же, из интереса, решил выполнить поиск в целых положительных числах. С ними возник ещё один небольшой нюанс - при постепенном приближении к решению, популяция упиралась в "нулевую стенку" - то есть, уменьшение какого-то значения приводило к всё лучшему и лучшему результату и - останавливалось в нуле, потому что отрицательные значения на этот раз были исключены.
Однако же, в итоге, всё получилось.
Моё первое решение в натуральных числах:
15 | 1 | 11 | x1 = 4 |
5 | 1 | 2 | x2 = 8 |
6 | 6 | 7 | x3 = 8 |
| y1 = 9 | y2 = 8 | y3 = 6 |
и моё второе решение в натуральных числах:
15 | 1 | 11 | x1 = 4 |
3 | 3 | 2 | x2 = 8 |
4 | 4 | 7 | x3 = 8 |
| y1 = 9 | y2 = 8 | y3 = 6 |
- после этого я внёс ещё некоторые изменения, чтобы расширить область поиска, из-за чего поиск решения замедлился, а результат - моё третье решение в натуральных числах совпало с первым ))
да, спасибо за такую задачу, было над чем голову поломать. Разобрался в некоторых нюансах генетических алгоритмов. В-общем, полезная оказалась задачка!
Ну а сейчас у нас на очереди следующая задачка:
Дошёл до меня слух, что в этой задаче в квадраты можно подставлять не более одного раза каждую цифру, кроме ноля!
Однако, в такой формулировке это получается задача с подвохом: Оффтоп
У меня один ноль получился. )
Серьёзно? Хмм... кто-то из нас ошибается.
Блин, сейчас подставил в Excel моё решение с цифрами - и увидел, что я там ошибся, не сходится решение. Но ранее я перебирал варианты, с учётом зависимостей в этой схеме и, вроде бы, у меня получалось, что решения, где все цифры разные - не существует.
В любом случае, я не хочу сейчас смотреть твой ответ, а пока подумаю ещё. А когда решу, то ещё и прогу напишу, чтобы она перебрала все варианты - для только цифр это должно быть недолго - там миллиард вариантов всего, программно можно легко их все перебрать.
Не знаю, что в этом здорового, но, раз такое дело, постарался написать программу покрасивше:
( на этом форуме предусмотрена возможность вставлять код на разных языках, ничо себе!)
C++:
#include <iostream>
int main()
{
int a = 0, b = 10;
for(int i0 = a; i0<b; i0++)
for (int i1 = a; i1 < b; i1++)
for (int i2 = a; i2 < b; i2++)
for (int i3 = a; i3 < b; i3++)
for (int i4 = a; i4 < b; i4++)
for (int i5 = a; i5 < b; i5++)
for (int i6 = a; i6 < b; i6++)
for (int i7 = a; i7 < b; i7++)
for (int i8 = a; i8 < b; i8++)
if (i3 != 0 && i7 != 0)
if ((i0 * i1 - i2) == 4)
if ((i3 + i4 + i5) == 8)
if ((i1 + i4 + i7) == 8)
if ((i2 + i5 - i8) == 6)
if ((i6 % i7) == 0 && (i6 / i7 + i8) == 8)
if ((i0 % i3) == 0 && (i0 / i3 + i6) == 9)
std::cout << i0 << " * " << i1 << " - " << i2 << " = 4\n"
<< "/ + +\n"
<< i3 << " + " << i4 << " + " << i5 << " = 8\n"
<< "+ + -\n"
<< i6 << " / " << i7 << " + " << i8 << " = 8\n"
<< "= = =\n"
<< "9 8 6\n" << std::endl;
return 0;
}Увы, но среди результатов нет таких, в которых бы все цифры были различны. Так что, я в своих прикидках был прав. Но, да - есть такие, где всего один ноль.
Ну и поскольку искать решение для случая, где цифры могут повторяться, слишком муторно, то сразу даю все найденные ответы:
Код:
1 * 5 - 1 = 4
/ + +
1 + 2 + 5 = 8
+ + -
8 / 1 + 0 = 8
= = =
9 8 6
3 * 3 - 5 = 4
/ + +
1 + 4 + 3 = 8
+ + -
6 / 1 + 2 = 8
= = =
9 8 6
3 * 3 - 5 = 4
/ + +
3 + 4 + 1 = 8
+ + -
8 / 1 + 0 = 8
= = =
9 8 6По примерным прикидкам, полный перебор 9 вариантов от 0 до 20 займёт порядка 15 минут. Но незачем этого делать, когда эти 6 уравнений с 9 неизвестными можно преобразовать в уравнения с 3 неизвестными и подбирать эти всего 3 значения. Чтобы полный перебор за разумное время (15 - 45 минут) мог охватить б0льший диапазон.
Оффтоп