Comments 54
То ли я чего-то не понял, то ли операция «нажать на барабан» коммутативна, и всего вариантов 3^5 (да и их перебирать не надо).
+5
Второй, четвёртый и пятый барабаны тыкнуть дважды, третий один раз. Если я правильно понял запись паттернов (а не транспонированно).
+1
Всего 5 секций и 4 масти. Теорема о числе комбинаций: 4^5.
Почему вы взяли 3?
Почему вы взяли 3?
+5
Ну, конкретно для этой задачи можно составить систему линейных уравнений, которая примитивно решается за N^3 ( можно и быстрей ), в то время как ваш способ имеет экспоненциальную сложность.
А вообще не понял, о чем статья. О том, что интуиция рулит? Ну, так вы написали программу которая делает тупые действия, а не ищет решение данной проблемы, поэтому неудивительно, что она действовала так тупо.
Разумеется, что программа написанная за 5 минут на коленке не может сравниться в изощренности с человеческим мозгом.
А вообще не понял, о чем статья. О том, что интуиция рулит? Ну, так вы написали программу которая делает тупые действия, а не ищет решение данной проблемы, поэтому неудивительно, что она действовала так тупо.
Разумеется, что программа написанная за 5 минут на коленке не может сравниться в изощренности с человеческим мозгом.
+21
Согласен, линейные уравнения — первое что приходит в голову.
from sympy import *
A = Matrix([[1, -1, 1, 0, 0],
[1, 1, 0, 0, -1],
[0, -1, 1, -1, 0],
[-1, 0, 0, 1, 1],
[0, 0, -1, 1, 1]]).T
b = Matrix([0,0,0,-3,-1])
sol = A.LUsolve(b)
print map(lambda a: a % 4, sol)
[2, 1, 3, 3, 1]
+5
Причем здесь линейные уравнения? Это поисковая задача.
Решение:
1 1 1 2 3 3 3 4 4 4
Я немного ошибся с статье (давно дело было, детали забыл). Кратчайшее решение имеет длину не 14, а 10, но это сути не меняет.
Решение:
1 1 1 2 3 3 3 4 4 4
Я немного ошибся с статье (давно дело было, детали забыл). Кратчайшее решение имеет длину не 14, а 10, но это сути не меняет.
-4
При том, что решение может быть представлено как решение системы линейных уравнений.
Как верно заметили выше — операции поворота барабанов коммутативны, то есть не имеет значения, в каком порядке крутить выбирать барабаны — важно только то, сколько раз каждый будет повернут. Если количество поворотов каждого из барабанов обозначить переменными xi — как раз СЛАУ из пяти уравнений и получится.
Как верно заметили выше — операции поворота барабанов коммутативны, то есть не имеет значения, в каком порядке крутить выбирать барабаны — важно только то, сколько раз каждый будет повернут. Если количество поворотов каждого из барабанов обозначить переменными xi — как раз СЛАУ из пяти уравнений и получится.
+8
Ну вы же сами изобразили повороты как +1 и -1, и получилась матрица. К тому же, через уравнения сразу находится кратчайшее решение.
PS накосячил с данными, там не [0,0,0,-3,-1] а [0, -2, 2, -3, -1]. И получается как раз [0, 3, 1, 3, 3]
PS накосячил с данными, там не [0,0,0,-3,-1] а [0, -2, 2, -3, -1]. И получается как раз [0, 3, 1, 3, 3]
+3
ОК, я понял ваше решение (без объяснения оно выглядит странно). Еще я вспомнил, один наш бизнес-аналитик решил задачу в Excel-е. Он скорее всего использовал ваш метод.
В общем, да, задачу можно решить оптимально несколькими способами, но суть не в том можно или нельзя ее решить, а в том как ее решает обычный, случайный человек без математического образования, а именно в методе тыка и его эффективности у разных людей.
Решая задачу методом тыка, человек (в данном случае я) перебирает комбинации, не задумываясь о коммутативности и тем более не решая систем уравнений. Я помню, что перебирал варианты, возвращаясь к предыдущим, и я точно не перебирал сотни комбинаций (это заняло бы больше времени). Барабанов в этой задаче не просто так пять, именно это число образов человек может одновременно держать в памяти, поэтому предсказать ходы более чем на один шаг здесь очень сложно. Парадокс заключается в том, что я делал ходы без всяких рассчетов, на основании внутреннего ощущения, и это дало результат. Объяснить это удачей сложно, потому что уж слишком малая здесь вероятность попасть пальцем в небо.
В конце концов, ваше решение тоже как-то пришло к вам в голову или вы его вспомнили, но тогда оно как-то пришло в голову кому-то другому. Не известно формального способа решить любую задачу, но задачи как-то решаются, и в этом заключается загадка.
В общем, да, задачу можно решить оптимально несколькими способами, но суть не в том можно или нельзя ее решить, а в том как ее решает обычный, случайный человек без математического образования, а именно в методе тыка и его эффективности у разных людей.
Решая задачу методом тыка, человек (в данном случае я) перебирает комбинации, не задумываясь о коммутативности и тем более не решая систем уравнений. Я помню, что перебирал варианты, возвращаясь к предыдущим, и я точно не перебирал сотни комбинаций (это заняло бы больше времени). Барабанов в этой задаче не просто так пять, именно это число образов человек может одновременно держать в памяти, поэтому предсказать ходы более чем на один шаг здесь очень сложно. Парадокс заключается в том, что я делал ходы без всяких рассчетов, на основании внутреннего ощущения, и это дало результат. Объяснить это удачей сложно, потому что уж слишком малая здесь вероятность попасть пальцем в небо.
В конце концов, ваше решение тоже как-то пришло к вам в голову или вы его вспомнили, но тогда оно как-то пришло в голову кому-то другому. Не известно формального способа решить любую задачу, но задачи как-то решаются, и в этом заключается загадка.
0
Ваше «поисковое» решение нашло неоптимальный вариант. Кратчайшее решение имеет длину 10 (см. товарища hellman ниже) и находится как решение СЛУ [0;2;2;1;3]=K*M, где M — Ваша транспонированная матрица паттернов. Проблема не в отсутствии алгоритмов, а в Вашем неумении их использовать.
Любая задача математики может быть сформулирована как поисковая. «найти верное решение». Можно даже пространство поиска соорудить, а потом обвинять компьютер, что он дурак и ничего не может решить.
Любая задача математики может быть сформулирована как поисковая. «найти верное решение». Можно даже пространство поиска соорудить, а потом обвинять компьютер, что он дурак и ничего не может решить.
+2
А в чем парадокс то?
+8
У машины нет фантазии для гипотезы
+1
зачем брут-форс? почитайте ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83
+2
Поиск в ширину без априорной оценки и есть brute force. Подбор числа можно реализовать оптимальней и распаралелить.
-2
Это не будет брутфорсом, если не заходить повторно в уже посещенные состояния — это уже будет динамическое программирование, с асимптотическим временем работы O(M^N) = O(1024).
-2
Прямой последовательный перебор тоже не заходит в пройденные состояния.
-2
это называется распаралеленный обход в ширину :) и не спорьте, я прав
+3
Если бы ваш перебор не заходил в пройденные состояния, он бы и одной секунды не проработал.
Потому что вообще всего состояний тысяча — ему просто негде было бы еще ходить :)
Потому что вообще всего состояний тысяча — ему просто негде было бы еще ходить :)
-2
в общих чертах да, но динамическое программирование в данной ситуации неприменимо — граф состояниий цикличен
-1
Как несложно заметить, у нас всего 4^5 = 1024 вершины. Любой разумный алгоритм поиска решит задачу мгновенно.
Так что пример неудачный. Если Вы не смогли придумать эффективный алгоритм — это не значит, что его нет.
Общая же мысль довольно очевидна. Существование алгоритмически неразрешимых задач — один из краеугольных камней фундаментальной математики (с его помощью например доказываются теоремы Геделя о неполноте).
На практике, если «не очень длинная» машина Тьюринга — это машина Тьюринга длиной <= 100500 бит, то вполне есть алгоритм, который по каждой такой МТ скажет, останавливается она или нет)
Так что пример неудачный. Если Вы не смогли придумать эффективный алгоритм — это не значит, что его нет.
Общая же мысль довольно очевидна. Существование алгоритмически неразрешимых задач — один из краеугольных камней фундаментальной математики (с его помощью например доказываются теоремы Геделя о неполноте).
На практике, если «не очень длинная» машина Тьюринга — это машина Тьюринга длиной <= 100500 бит, то вполне есть алгоритм, который по каждой такой МТ скажет, останавливается она или нет)
+2
Тоже не понял, в чем собственно парадокс. Приведенная задача с машиной Тьюринга не решается алгоритмически в общем случае, для частных случаев решение находится. С человеком так же, некоторые задачи веками ждут решения и не доказана их неразрешимость. Приведите хоть одну задачу, которая неразрешима алгоритмически, но решена человеком в общем виде.
Касательно математики — да, многие задачи изначально решались с привлечением интуиции, но любое доказательство принимается только тогда, когда имеет строго формальную форму. А за пределами математики полной достоверности нет вообще.
Касательно математики — да, многие задачи изначально решались с привлечением интуиции, но любое доказательство принимается только тогда, когда имеет строго формальную форму. А за пределами математики полной достоверности нет вообще.
+1
> Приведите хоть одну задачу, которая неразрешима алгоритмически, но решена человеком в общем виде.
Тест Тьюринга.
Тест Тьюринга.
0
Все алгоритмы придуманы людьми, но не придумано алгоритма, построения других алгоритмов, потому что невозможно создать алгоритм строящий сам себя.
-1
Простите, что Вы понимаете под «построить алгоритм»? Только формально, пожалуйста.
0
бездоказательное утверждение.
а алгоритмы, строящие другие алгоритмы, существуют. пример — генетическое программирование
а алгоритмы, строящие другие алгоритмы, существуют. пример — генетическое программирование
+1
Моделирование эволюции — это совсем другая материя. Эволюционные процессы фундаментально недетерминированы, поэтому не могут считаться классическими вычислительными процессами.
-1
Что за бред, простите? С каких пор вероятностные алгоритмы перестали быть алгоритмами, и уж тем более вычислительными процессами (которые, кстати, и есть «другая материя»)? Вы не хотите ли перечитать определение алгоритма и вычислительного процесса, прежде чем писать такую чушь?
0
«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)
«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)
«Алгоритм — точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. М. М. Розенталя)
«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович, учебник «Информатика и информ. технологии»)
0
Детерминированный порядок выполнения и детерминированность алгоритма — не одно и то же. Если Вы помните, у Кнута второй том посвящен вероятностным алгоритмам. Ни в одном из приведенных определений нет ни слова об эквивалентности алгоритма вычислительным процессам и отрицания возможности использования случайных величин.
0
Хорошо, тогда как получить криптографическое случайное число, не имея источника энтропии?
0
Начнем с того, что Вы понимаете под источником энтропии. Про генераторы псевдослучайных чисел слышали?
0
С псевдослучайными числами есть одна проблема — рано или поздно они начинают повторяться и в долгосрочной перспективе процесс все равно становится детерминорованным.
Источники энтропии, в контексте криптографии, — это то, что генерирует действительно случайные величины, паттерн которых гарантированно никогда не повторяется. К примеру, перепады напряжения в сети, потеря IP пакетов, движения мышкой и т.д. Из этих данных в операционных системах генерируются криптографические ключи.
Если нам нужны случайные данные для вычисления со сколь угодно большим количеством обращений к генератору случайных чисел, нам нужен генератор действительно случайных чисел, то есть криптографический генератор.
Источники энтропии, в контексте криптографии, — это то, что генерирует действительно случайные величины, паттерн которых гарантированно никогда не повторяется. К примеру, перепады напряжения в сети, потеря IP пакетов, движения мышкой и т.д. Из этих данных в операционных системах генерируются криптографические ключи.
Если нам нужны случайные данные для вычисления со сколь угодно большим количеством обращений к генератору случайных чисел, нам нужен генератор действительно случайных чисел, то есть криптографический генератор.
0
Последовательность случайных чисел, взятых извне, может считаться исходными данными алгоритма. Это никак не противоречит определению алгоритма. При этом сам алгоритм не изменится. Это и есть «детерминированный порядок выполнения» — структура алгоритма не изменяется в зависимости от входных данных. Это могут быть даже не случайные числа. Представьте машину Тьюринга, которая читает ленту нулей и единиц и останавливается тогда, когда встретит первую единицу на ленте. Длина и содержание ленты при этом никак не влияет на структуру самой машины Тьюринга. Любые взятые извне данные в принципе могут считаться случайными
+1
выделяемое Вами слово определённость говорит только о конечности множества операций, составляющих носитель алгоритма
0
Не совсем
"Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного".
"Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного".
0
И в чем противоречие? если считать начальное значение генератора псевдослучайных чисел или само случайное число входными данными, вероятностный алгоритм выродится в обычный детерминированный
0
Кстати, от куда это определение? Оно не совсем верно в части В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. Это не так, если нет оговорки, что различные реализации используют одно мультимножество операций и на множестве операций определено транзитивное отношение.
0
А давайте теперь вспомним строгое, принятое в математике определение алгоритма (точнее вычислимой функции) (там их несколько, но все они в смысле вычислимости эквивалентны).
Итак. Функция называется вычислимой, если существует вычисляющая ее машина Тьюринга. В понятии МТ случайности нет, да она там и не нужна.
Хотя есть и вариант со случайностью. Как правило, он реализуется путем дополнительного входа, содержащего «результаты бросания монетки».
Обычное требование к вероятностному алгоритму — он дает правильный ответ чаще, чем неправильный. В этом случае наличие случайности на вычислимость никак не влияет. Ибо никто не мешает нам перебрать все возможные варианты выпадения монетки.
Итак. Функция называется вычислимой, если существует вычисляющая ее машина Тьюринга. В понятии МТ случайности нет, да она там и не нужна.
Хотя есть и вариант со случайностью. Как правило, он реализуется путем дополнительного входа, содержащего «результаты бросания монетки».
Обычное требование к вероятностному алгоритму — он дает правильный ответ чаще, чем неправильный. В этом случае наличие случайности на вычислимость никак не влияет. Ибо никто не мешает нам перебрать все возможные варианты выпадения монетки.
+2
Ксати, приведенный «универсальный алгоритм, которым любой обычный человек решает любую головоломку» по-сути есть эвристический поиск в пространстве состояний. Вы просто не определили эвристики «хорошая комбинация» и «оценка состояния».
+2
Описанную ситуацию можно назвать парадоксом, если считать компьютер волшебной палочкой, а не высокотехнологичным молотком. :)
+3
UFO just landed and posted this here
Sign up to leave a comment.
Интуиция, головоломки и вычислимость