Головоломка

GOGI> А что такое NP-полная?
GOGI> А у человека еще и неалгоритмизируемые методы поиска решения есть

В данном случае (для 16 ферзей) программа 160712 раз проверяла, можно ли поставить на данную позицию, 10052 раза ставила ферзя и 10036 раз снимала. Скажем, если потренироваться, наверное, можно оценивать позицию за полсекунды, ставить и снимать - за секунду. Получается 27 часов примерно (на одну позицию). Если искать все позиции.. эээ... их (разных) примерно 15 миллионов, из них примерно 1.5 миллионов существенно разных (т.е. исключая те, что получаются вращением/отражением). Значит, имеем 15млн*27 часов = примерно сорок пять тысяч лет чтобы получить все решения. Каждое надо сравнить со списком предыдущих дабы исключить вращения/отражения. То есть, в среднем, надо будет искать в списке из примерно 600000 позиций не переходит ли твоя в готовую отражением/поворотом. Я бы оценил в самый минимум 30 секунд на сравнение отражение/повороты одной позиции. В среднем будем сравнивать с 300000 позиций (иногда будет везти - будем находить в числе первых, иногда наоборот - будем все 600 тысяч шарашить). Получается 30 секунд*300000 позиций * 15 миллионов найденных позиций = 4.28 миллионов лет. Первоначальные 45 тысяч лет можно уже и не учитывать. То есть, вот примерно столько занял бы пересчет. Заметь, что компьютер справляется с этим за ~400 секунд. То есть, компьютер соображает
примерно в 300 с лишком миллиардов раз быстрее человека.

Сергей-4030> NP-полная значит - нет никаких методов, хоть алгоритимизируемых, хоть неалгоритмизируемых.
Судя по википедии, это все же немного не так. Имеются ввиду именно алгоритмизируемые задачи. Тем более, что наука пока даже близко не знает, как находят решения существа разумные.
Это конечно не значит, что я сходу найду решение для доски 16*16, но исключать того, что есть люди для которых эта задача элементарна - нельзя.
В те же шахматы компьютер научился играть лучше сильнейших игроков всего несколько лет назад. При этом нет никакой гарантии, что среди остальных 6 млрд. людей не нашлось бы тех, кто бы выиграли эту программу, вероятно, они вообще в шахматы ни разу не играли.
Но в любом случае считать, что человек будет решать эту задачу тупым перебором - как-то очень механистично.

GOGI> Но в любом случае считать, что человек будет решать эту задачу тупым перебором - как-то очень механистично.

И тем не менее, есть класс задач, которые никак иначе решить нельзя.

Сергей-4030> И тем не менее, есть класс задач, которые никак иначе решить нельзя.
Пример?

Сергей-4030>> И тем не менее, есть класс задач, которые никак иначе решить нельзя.
GOGI> Пример?

Приведен выше. Или, скажем, укладка ранца. Скорее всего, шахматы падают в ту же категорию. Да-да, шахматы. Ты скажешь - сильные шахматисты пока еще могут играть с компьютерами. Да, могут. Потому, что задача еще не решена. Поэтому мы можем спекулировать всякими эмпириками и думать, что занятый центр - это хорошо и правильно. Но это совсем не значит, что это на самом деле так при правильной игре сторон. Шахматы НЕ решены. Когда будут решены - человек, со всеми его неалгоритмизируемыми достоинствами, будет всегда проигрывать. Не способен человек решать такие задачи полным перебором, а никак иначе (что в будущем покажут бесславные проигрыши чемпионов ) решить эту задачу так-таки нельзя. Задача о 16 ферзях (как показано ) - решена. Тут не нужны уже никакие гипотезы.

GOGI> Сергей, ты не о том споришь. Я не говорю, что человек может решить эти задачи лучше компьютера. Я говорю, что человек может решать такие задачи не прибегая к полному перебору вариантов. Может у него в мозгу задействуется мат. аппарат, до которого современная математика просто не дошла, ХЗ, но то что может - я уверен.

Из практики такого не следует. Не видал и не слыхал о таких людях в приложении к конкретной задаче (скажем, какую-нибудь задачу о 20 ферзях возьмем). Андрей, нынешняя математика очень много чего может. Она иногда может, в частности доказать, что такую-то задачу невозможно решить никаким другим путем, кроме такого-то. Не то, что математика не в курсе пока, как это сделать, а совсем наоборот - математика совершенно точно и строго доказала, что никак не сделать.

Murkt> Задача о н-цати ферзях решается перебором с отходом назад.

Что и обеспечивается рекурсией — точнее возвратом.

Серёг, вы говорите немного о разном. GOGI хочет найти хоть какое-то решение. Ты толкуешь о решении с математической точки зрения — либо все решения, либо оптимальное в широком понимании (или не хуже оптимального в n раз). Поэтому и разногласия.

У меня, кстати, вопрос по задачке — ты рассматривал только простые преобразования — поворот, осевая симметрия (горизонтальная, вертикальная, левая и правая диагональные). Мне стало интересно рассмотреть суперпозиции их. Чего мне кажется, что оригинальных решений будет ещё меньше. А проверок больше.

Mishka> Серёг, вы говорите немного о разном. GOGI хочет найти хоть какое-то решение.
Что значит "хоть какое-то"? Звучит как "может не самое удачное, неизящное, тупое и банальное". Нормальное решение, единственное, которые нужное в реальной жизни. А постановки типа "найти все решения и доказать, что больше их нет", это сами математики придумали, чтобы довод был, почему мы их всех до сих пор не расстреляли

Mishka>> Серёг, вы говорите немного о разном. GOGI хочет найти хоть какое-то решение.
GOGI> Что значит "хоть какое-то"? Звучит как "может не самое удачное, неизящное, тупое и банальное". Нормальное решение, единственное, которые нужное в реальной жизни. А постановки типа "найти все решения и доказать, что больше их нет", это сами математики придумали, чтобы довод был, почему мы их всех до сих пор не расстреляли

А зачем тебе в реальной жизни вообще решать задачу о восьми ферзях?

Mishka> У меня, кстати, вопрос по задачке — ты рассматривал только простые преобразования — поворот, осевая симметрия (горизонтальная, вертикальная, левая и правая диагональные). Мне стало интересно рассмотреть суперпозиции их. Чего мне кажется, что оригинальных решений будет ещё меньше. А проверок больше.

Вроде бы, нет. Я на это обращал внимание, все вроде как покрывается. Собственно, два поворота есть центральная симметрия, правильно? Все преобразования циклические, поэтому можно особо не париться. Вернее, конечно, у меня проверяется суперпозиция, но собственно разных преобразований (и "простых" и суперпозиций) не очень много. Собственно, можно проверить - список решений для размера 8 я публиковал. Или, например, возьмем размер 5. Если не проверять преобразования:

1. 5 queens.
2. Started at:Fri Feb 08 10:37:52 EST 2008
3. Finished at:Fri Feb 08 10:37:52 EST 2008, after 63 ms.
4. 10 solutions found.
5.   ----------
6. 05       FF
7. 04   FF
8. 03         FF
9. 02     FF
10. 01 FF
11.    A B C D E
12.   ----------
13.  
14.   ----------
15. 05     FF
16. 04         FF
17. 03   FF
18. 02       FF
19. 01 FF
20.    A B C D E
21.   ----------
22.  
23.   ----------
24. 05         FF
25. 04     FF
26. 03 FF
27. 02       FF
28. 01   FF
29.    A B C D E
30.   ----------
31.  
32.   ----------
33. 05       FF
34. 04 FF
35. 03     FF
36. 02         FF
37. 01   FF
38.    A B C D E
39.   ----------
40.  
41.   ----------
42. 05         FF
43. 04   FF
44. 03       FF
45. 02 FF
46. 01     FF
47.    A B C D E
48.   ----------
49.  
50.   ----------
51. 05 FF
52. 04       FF
53. 03   FF
54. 02         FF
55. 01     FF
56.    A B C D E
57.   ----------
58.  
59.   ----------
60. 05 FF
61. 04     FF
62. 03         FF
63. 02   FF
64. 01       FF
65.    A B C D E
66.   ----------
67.  
68.   ----------
69. 05   FF
70. 04         FF
71. 03     FF
72. 02 FF
73. 01       FF
74.    A B C D E
75.   ----------
76.  
77.   ----------
78. 05   FF
79. 04       FF
80. 03 FF
81. 02     FF
82. 01         FF
83.    A B C D E
84.   ----------
85.  
86.   ----------
87. 05     FF
88. 04 FF
89. 03       FF
90. 02   FF
91. 01         FF
92.    A B C D E
93.   ----------

Если проверять:

1. 5 queens.
2. Started at:Fri Feb 08 10:40:05 EST 2008
3. Finished at:Fri Feb 08 10:40:05 EST 2008, after 63 ms.
4. 2 solutions found.
5.   ----------
6. 05 FF
7. 04     FF
8. 03         FF
9. 02   FF
10. 01       FF
11.    A B C D E
12.   ----------
13.  
14.   ----------
15. 05   FF
16. 04         FF
17. 03     FF
18. 02 FF
19. 01       FF
20.    A B C D E
21.   ----------

Вроде как, решения совершенно различные. Конечно, это случа тривиальный, но вроде как при размерностях выше получается то же. Опять же, каков "цикл" поворотов? После 4 поворотов ситуация замыкается. Центральную симметрию вовсе можно не рассматривать (центральная симметрия - 2 поворота). Осевая "горизонтальная" - 2 состояния, "вертикальная" - еще 2. Еще две диагональные - 2 и 2. Получается 4 * 4 * 4 = 64 "транзиции" максимум. Но на самом деле их меньше, потому что отдельные суперпозиции равны.

Murkt>> Задача о н-цати ферзях решается перебором с отходом назад.
Mishka> Что и обеспечивается рекурсией — точнее возвратом.
Но полным перебором не является

Полл> Небольшая поправка: как я помню, восьмиклеточные шахматы просчитаны.

В смысле, просчитаны? Чего просчитаны?

GOGI> Что значит "хоть какое-то"? Звучит как "может не самое удачное, неизящное, тупое и банальное". Нормальное решение, единственное, которые нужное в реальной жизни. А постановки типа "найти все решения и доказать, что больше их нет", это сами математики придумали, чтобы довод был, почему мы их всех до сих пор не расстреляли

Не-а. Та же задача об укладке ранца — как-то уложить можно. Хочется, чтобы вошло побольше. Или эквивалентная задача — из листа железа надо вырезать штучки сложной формы. Просто вырезать легко. Однако задача — минимизировать отходы, время на смену листа и т.д. Поэтому эти задачки, как раз, очень из жизни. Поэтому подход один — математический.


Ну и с шахматами — если задача найти хоть какое-то решение, то и в этом случае машина тебя побъёт с вероятностью 99.9999%

Сергей-4030> ЗЫ Кстати, шашки уже почти решены, Андрей, знаешь? Ходишь первый раз, машина тебе тут же: ошибся, батенька, не позже, чем через пятьсот ходов тебе придет кирдык. Вот когда шахматные программы так же будут отвечать на e2-e4 - тут-то ты меня попомнишь.
Дык, её решили. Есть только одна стратегия, ЕМНИП, сыграть в ничью. Дерево составлено полностью.

Murkt> Но полным перебором не является

Здрасьте, батенька. У тебя понятие полного перебора вовсе не математическое. Полный перебор в математике — это перебор всех возможных значений, а не всех, какие Бог на душу положит. Поэтому как только постановка ферзя становится невозможной, так дальше и не идём. Но, чтобы дойти до этой ситуации — мы берём все возможные значения. Это и есть полный перебор. Не полный перебор — это, к примеру, жадный алгоритм. Он может давать сколь угодно далёкое решение от оптимального (за исключением матроидов), но даёт чёткое направление как из нескольких возможных альтернатив взять одну. т.е. не перебирая их все.

Сергей-4030>> ЗЫ Кстати, шашки уже почти решены, Андрей, знаешь? Ходишь первый раз, машина тебе тут же: ошибся, батенька, не позже, чем через пятьсот ходов тебе придет кирдык. Вот когда шахматные программы так же будут отвечать на e2-e4 - тут-то ты меня попомнишь.
Mishka> Дык, её решили. Есть только одна стратегия, ЕМНИП, сыграть в ничью. Дерево составлено полностью.

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

Murkt>> Но полным перебором не является
Mishka> Здрасьте, батенька. У тебя понятие полного перебора вовсе не математическое.
Ой, эта ж тема не в "Программировании"

Сергей-4030> Вроде бы, нет. Я на это обращал внимание, все вроде как покрывается. Собственно, два поворота есть центральная симметрия, правильно?

Да, поэтому я её и не упомянул.

Сергей-4030> Все преобразования циклические, поэтому можно особо не париться. Вернее, конечно, у меня проверяется суперпозиция, но собственно разных преобразований (и "простых" и суперпозиций) не очень много.

Простых 5 — 4 осевые и 1 поворотная. Надо будет посчитать варианты выражения через другие. Как с центральной. Приду домой — займусь.
Пока вышло так
H - Horizontal flip
V — Vertical flip
Dl — Diagonal — top left upper bottom right
Dr — Diagonal — top right bottom left
R — Rotation from X to Y 90⁰

HV=RR
VH=RR
DlDr=RR
DrDl=RR
VDr=RRR=R^-1
VDl=R
HDr=R
HDl=RRR=R^-1
VR=Dl
RV=Dl
HR=Dr
RH=Dr
DlR=H
RDl=V
DrR=V
RDr=H

Всякие RRRH рассматривать неинтересно — сокращается легко RRRH=RRDr=RH=Dr. Да, ты прав, никаких других суперпозиций не надо. Итого, H, V, Dl, Dr, R, RR, RRR. Для проверок R, RR, RRR даже не надо копии массива каждый раз. С ростом размера может оказаться. что сделать H, проверить, HV проверить будет быстрее, чем сделать копию H, проверить, на копии проверить V.

Похоже, что это будет просто быстрее в любом случае, т.к. при создании нового объекта приходится в него копировать циклом в любом случае. Оставим копирование только для запоминания результата.

Т.е., что-то вроде (HFlip, VFlip, DlFlip, DrFlip, Rotate выдают reference на себя, CheckSolution выдает true, если решение надо добавить; в принципе, оно может сразу и добавлять):

1.   if ( CheckSolution( solution ) ) solutions.AddSolution( solution );
2.   if ( Checsolution( solution.HFlip( ) ) solutions.AddSolution( solution );
3.   if ( Checsolution( solution.HFlip( ).VFlip( ) ) solutions.AddSolution( solution );
4.   if ( Checsolution( solution.VFlip( ).DlFlip( ) ) solutions.AddSolution( solution );
5.   if ( Checsolution( solution.DlFlip( ).DrFlip( ) ) solutions.AddSolution( solution );
6.   if ( Checsolution( solution.DrFlip( ).Rotate( ) ) solutions.AddSolution( solution );
7.   if ( Checsolution( solution.Rotate( ) ) solutions.AddSolution( solution );
8.   if ( Checsolution( solution.Rotate( ) ) solutions.AddSolution( solution );

Сергей-4030> Я не знал. Недавно решили? Последний раз, когда я смотрел, у них был, конечно, хороший задел, очень много дебютов просчитано, но вроде еще не все. Это, наверное, Полл и имел в виду, только не "восьмиклеточные шахматы", а "шашки".

Давно уже — точно больше 5 лет. Мне, собственно, мужик сказал, который был чемпионов в Молдавии по шашкам. Потом где-то ещё проскакивало. ЕМНИП, моща компов позволила просто просчитать всё.

Сергей-4030> Да нет, я понимаю. Поэтому и привел в пример шахматы. Лучшие (в данном применении) умы планеты задачу решают (своими "неалгоритмическими" методами), да решить (то бишь делать лучшие возможные ходы) не могут. И когда компьютеры эту задачу таки решат (как шашки почти решили) - все, конец. То есть, решение. Которое заведомо не по зубам человеку.
Так ты и не понял, о чем я спорил Я не о том, что есть задачи, на которых человек побьет компьютер (хотя и таких полно осталось даже после того как шахматы посчитали), а про то, что человек эти задачи считает не так как компьютер, поэтому оценивать сложность задачи для человека по тому, сколько машиновремени для этого понадобится нельзя.

GOGI> Так ты и не понял, о чем я спорил Я не о том, что есть задачи, на которых человек побьет компьютер (хотя и таких полно осталось даже после того как шахматы посчитали), а про то, что человек эти задачи считает не так как компьютер, поэтому оценивать сложность задачи для человека по тому, сколько машиновремени для этого понадобится нельзя.

Да понял он. Просто оценка сложности алгоритма — это чисто математическая, к компам имеет отношение пятое. В математике такие задачи и оценивают. Как показывает практика, случайно такие задачи решают, но вероятностно оно в полном сооветствии с теорией. Т.е. можно дать тебе уравниение и спосить, а какой корень у него. И скажешь ты: "25!" И даже может угадаешь, но чаще (в 99.999999999%) нет.