![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
kaz-orphan2.livejournal.com posting in ![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
useless_faqизвестно, что судоку - NP-полная задача. Следовательно единственным методом решения является полный перебор. А все увлеченно пытыются решить эту задачу типа в голове. это напоминает поиск шестого эвклидового тела.
но, с другой стороны, мы повсеместно имеем страницы в журналах и всяческие программы генерирующие экзамплы, действительно решаемые в голове. это порождает у меня вопросы:
1.(психология) а какой достоверно зарегистрированный уровень перебора реализуемый системой глаз-мозг? т.е. человек смотрит и решает, ничего никуда не записывая и впоследствии не обращаясь к записям. Здорово, если бы такие данные были бы дифференцированы как для задач решаемых перебором в ширину, так для задач решаемым перебором в глубину. в первую очередь - применительно к судоку, но применительно к любой визуально наблюдаемой задаче тоже интересно.
2.(геймдизайн, статистика) в связи с этим, не следует ли пересмотреть критерии сложности судоку? их ранжировать то, надо по глубине необходимого для решения полного перебора. 1-детский, 2-легкий и т.д. а так же процент решаемых в системе глаз-мозг задач с 17...90 предзаданными цифрами.
3. (математика,биология, физика) известно, что минимальное количество цифр при котором судоку решается - 17. какой достоверно подтвержденный процент решаемых в системе глаз-мозг решаемых задач с 17-ю предзаданными цыфрами? (и далее - с 18-ю, 19-ю и т.д.). я вот уже 3 года решаю судоки из 21-26 цифр и не могу достичь 100%-ой решаемости. решаю максимум 10% из задач (хотя они и повторяются!) и быстрее меня решают как минимум 30% участников социума. понятно, что большинство из них пользуются компютерными подсказками, но не все же!
в общем и целом - статистика выше описанная и плюс еще что-то, позволит британским ученым понять: может ли человеческий мозг решать NP-полные задачи за не NP-полное время .А это уже интересно, всем - философам, математикам, физикам, биологам.
но, с другой стороны, мы повсеместно имеем страницы в журналах и всяческие программы генерирующие экзамплы, действительно решаемые в голове. это порождает у меня вопросы:
1.(психология) а какой достоверно зарегистрированный уровень перебора реализуемый системой глаз-мозг? т.е. человек смотрит и решает, ничего никуда не записывая и впоследствии не обращаясь к записям. Здорово, если бы такие данные были бы дифференцированы как для задач решаемых перебором в ширину, так для задач решаемым перебором в глубину. в первую очередь - применительно к судоку, но применительно к любой визуально наблюдаемой задаче тоже интересно.
2.(геймдизайн, статистика) в связи с этим, не следует ли пересмотреть критерии сложности судоку? их ранжировать то, надо по глубине необходимого для решения полного перебора. 1-детский, 2-легкий и т.д. а так же процент решаемых в системе глаз-мозг задач с 17...90 предзаданными цифрами.
3. (математика,биология, физика) известно, что минимальное количество цифр при котором судоку решается - 17. какой достоверно подтвержденный процент решаемых в системе глаз-мозг решаемых задач с 17-ю предзаданными цыфрами? (и далее - с 18-ю, 19-ю и т.д.). я вот уже 3 года решаю судоки из 21-26 цифр и не могу достичь 100%-ой решаемости. решаю максимум 10% из задач (хотя они и повторяются!) и быстрее меня решают как минимум 30% участников социума. понятно, что большинство из них пользуются компютерными подсказками, но не все же!
в общем и целом - статистика выше описанная и плюс еще что-то, позволит британским ученым понять: может ли человеческий мозг решать NP-полные задачи за не NP-полное время .А это уже интересно, всем - философам, математикам, физикам, биологам.
no subject
Date: 2014-02-09 12:46 pm (UTC)no subject
Date: 2014-02-09 02:43 pm (UTC)no subject
Date: 2014-02-12 07:24 pm (UTC)no subject
Date: 2014-02-09 12:53 pm (UTC)Судоку - np-complete задача. Определение победителя в шахматной позиции - np-complete задача. Но из этого совсем не следует, что для решения конкретного судоку нужен полный перебор. А победителя в эншпиле "ферзь+король против короля" сможет определить даже новичок.
no subject
Date: 2014-02-09 12:55 pm (UTC)no subject
Date: 2014-02-09 03:17 pm (UTC)практически всегда нужны допущения.
no subject
Date: 2014-02-09 09:05 pm (UTC)Это не верно. Доказательство теорем (например арифметики) это вообще алгоритмически неразрешимая задача. В арифметике Пресбургера (арифметика Пеано без умножения) алгоритм доказывающий формулы существует, но требует времени как минимум 2^(2^cn), что намного сложнее чем NP..
no subject
Date: 2014-02-09 02:40 pm (UTC)давайте рассмотрим судоку.
есть ровно 81 конфигураций с 80 предзаданными цифрами (с точностью до переобозначений). решаются все они ровно за один ход. любым.
есть ровно 81 исходная конфигурация с одной исходной цифрой. они не решаются.
есть примерно 10^77 промежуточных вариантов. И среди них есть те, которые я решаю, а вася пупкин не решает. или наоборот. вася решает, а я нет.
с другой стооны, если мы привлечем комбираторику, то для конфигурации с 80 предзаданными цифрами глубина необходимого перебора = 0.
а для 16 предзаданных цифр,глубина перебора - бесконечность.
зададим n цифр - x% нерешаемых, y% решаемых с 1 уровнем переюора, z% с двумя и т.д.
я вопервых хотел сказать, что уровень перебора 2+ большинству людей не по силам. мне не по силам оказался, хоть я и тренировался...
а вовторых все же надеялся, что найдутся люди этот уровень преодолевшие. Ассоциативно. ну в общем интересно, какой уровень перебора с возвратом по силам чиста интеллекту? без внешней памяти.
no subject
Date: 2014-02-09 03:48 pm (UTC)no subject
Date: 2014-02-09 04:11 pm (UTC)физиологически - количество развилок "если-то".
ну например - если в паре ячеек - (х,у), то во второй паре - (z,w). ну тд.
no subject
Date: 2014-02-09 05:05 pm (UTC)Сижу, экспериментирую, пытаюсь осмыслить как самому посчитать уровень перебора. В простых развилках не получается )))) Получается что-то вроде: если X тут и еще X здесь, а тут X быть не может потому что он обязан быть где-то здесь, то следовательно в этой клетке точно Х.
Как это формализовать, совершенно не понимаю. Хотя давно уже интересно )))
no subject
Date: 2014-02-09 06:50 pm (UTC)Нет, это более сложная задача, как минимум PolySpace-complete (если используется аналог правила 50 ходов).
может ли человеческий мозг решать NP-полные задачи за не NP-полное время
Это бессмысленный вопрос. Понятно, что человек никогда не решит судоку размером 1000000х1000000. Так что в принципе нельзя узнать, требуется ли человеку для решения судоку nxn время экспоненциально зависящее от n.
no subject
Date: 2014-02-09 07:03 pm (UTC)Ой, и правда. Там же "отрицание" можно проверить за полиномиальное время (в смысле, что мы проиграли). Спасибо!
(frozen) no subject
Date: 2014-02-09 02:21 pm (UTC)(frozen) no subject
Date: 2014-02-09 03:09 pm (UTC)(frozen) no subject
Date: 2014-02-09 03:14 pm (UTC)(frozen) no subject
Date: 2014-02-09 03:21 pm (UTC)no subject
Date: 2014-02-09 02:35 pm (UTC)no subject
Date: 2014-02-09 03:07 pm (UTC)no subject
Date: 2014-02-09 03:18 pm (UTC)no subject
Date: 2014-02-09 03:30 pm (UTC)no subject
Date: 2014-02-09 09:58 pm (UTC)no subject
Date: 2014-02-12 07:23 pm (UTC)это чушь несусветная
no subject
Date: 2014-02-12 07:25 pm (UTC)