Головоломка

 
1 2 3 4
US Сергей-4030 #07.02.2008 18:46  @GOGI#07.02.2008 17:58
+
-
edit
 

Сергей-4030

исключающий третье
★☆
админ. бан
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 с лишком миллиардов раз быстрее человека.
 
RU GOGI #07.02.2008 22:19  @Сергей-4030#07.02.2008 18:22
+
-
edit
 

GOGI

координатор
★★★
Сергей-4030> NP-полная значит - нет никаких методов, хоть алгоритимизируемых, хоть неалгоритмизируемых. ;)
Судя по википедии, это все же немного не так. Имеются ввиду именно алгоритмизируемые задачи. Тем более, что наука пока даже близко не знает, как находят решения существа разумные.
Это конечно не значит, что я сходу найду решение для доски 16*16, но исключать того, что есть люди для которых эта задача элементарна - нельзя.
В те же шахматы компьютер научился играть лучше сильнейших игроков всего несколько лет назад. При этом нет никакой гарантии, что среди остальных 6 млрд. людей не нашлось бы тех, кто бы выиграли эту программу, вероятно, они вообще в шахматы ни разу не играли.
Но в любом случае считать, что человек будет решать эту задачу тупым перебором - как-то очень механистично.
1  
US Сергей-4030 #07.02.2008 23:02  @GOGI#07.02.2008 22:19
+
-
edit
 

Сергей-4030

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

И тем не менее, есть класс задач, которые никак иначе решить нельзя.
 
RU GOGI #07.02.2008 23:08  @Сергей-4030#07.02.2008 23:02
+
-
edit
 

GOGI

координатор
★★★
Сергей-4030> И тем не менее, есть класс задач, которые никак иначе решить нельзя.
Пример?
1  
US Сергей-4030 #08.02.2008 00:26  @GOGI#07.02.2008 23:08
+
-
edit
 

Сергей-4030

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

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

GOGI

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

Murkt

Pythoneer

Задача о н-цати ферзях решается перебором с отходом назад.
[team Їжачки - сумні падлюки]  
US Сергей-4030 #08.02.2008 01:17  @GOGI#08.02.2008 00:39
+
-
edit
 

Сергей-4030

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

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

Mishka

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

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

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

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

GOGI

координатор
★★★
Mishka> Серёг, вы говорите немного о разном. GOGI хочет найти хоть какое-то решение.
Что значит "хоть какое-то"? Звучит как "может не самое удачное, неизящное, тупое и банальное". Нормальное решение, единственное, которые нужное в реальной жизни. А постановки типа "найти все решения и доказать, что больше их нет", это сами математики придумали, чтобы довод был, почему мы их всех до сих пор не расстреляли :-)
1  
US Сергей-4030 #08.02.2008 03:42
+
-
edit
 

Сергей-4030

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

ЗЫ Кстати, шашки уже почти решены, Андрей, знаешь? :) Ходишь первый раз, машина тебе тут же: ошибся, батенька, не позже, чем через пятьсот ходов тебе придет кирдык. ;) Вот когда шахматные программы так же будут отвечать на e2-e4 - тут-то ты меня попомнишь. ;)

ЗЗЫ При этом шахматам, как виду спорта, видимо, придет кирдык. Не, конечно, останутся верные болельщики какие-то, но в основном никому это будет неинтересно. Жаль. :(
 
US Сергей-4030 #08.02.2008 03:43  @GOGI#08.02.2008 02:06
+
-
edit
 

Сергей-4030

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

А зачем тебе в реальной жизни вообще решать задачу о восьми ферзях? :)
 
US Сергей-4030 #08.02.2008 18:43  @Mishka#08.02.2008 01:41
+
-
edit
 

Сергей-4030

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

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

code text
  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.   ----------


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

code text
  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 "транзиции" максимум. Но на самом деле их меньше, потому что отдельные суперпозиции равны.
 
+
-
edit
 

Полл

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

Murkt

Pythoneer

Murkt>> Задача о н-цати ферзях решается перебором с отходом назад.
Mishka> Что и обеспечивается рекурсией — точнее возвратом. :)
Но полным перебором не является ;)
[team Їжачки - сумні падлюки]  
US Сергей-4030 #08.02.2008 19:35  @Полл#08.02.2008 19:04
+
-
edit
 

Сергей-4030

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

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

Mishka

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

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


Ну и с шахматами — если задача найти хоть какое-то решение, то и в этом случае машина тебя побъёт с вероятностью 99.9999% :)
 
US Mishka #08.02.2008 19:56  @Сергей-4030#08.02.2008 03:42
+
-
edit
 

Mishka

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

Mishka

модератор
★★☆
Murkt> Но полным перебором не является ;)

Здрасьте, батенька. У тебя понятие полного перебора вовсе не математическое. Полный перебор в математике — это перебор всех возможных значений, а не всех, какие Бог на душу положит. Поэтому как только постановка ферзя становится невозможной, так дальше и не идём. Но, чтобы дойти до этой ситуации — мы берём все возможные значения. Это и есть полный перебор. Не полный перебор — это, к примеру, жадный алгоритм. Он может давать сколь угодно далёкое решение от оптимального (за исключением матроидов), но даёт чёткое направление как из нескольких возможных альтернатив взять одну. т.е. не перебирая их все.
 
US Сергей-4030 #08.02.2008 20:19  @Mishka#08.02.2008 19:56
+
-
edit
 

Сергей-4030

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

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

Murkt

Pythoneer

Murkt>> Но полным перебором не является ;)
Mishka> Здрасьте, батенька. У тебя понятие полного перебора вовсе не математическое.
Ой, эта ж тема не в "Программировании" :D
[team Їжачки - сумні падлюки]  
US Mishka #09.02.2008 00:04  @Сергей-4030#08.02.2008 18:43
+
-
edit
 

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 900

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, если решение надо добавить; в принципе, оно может сразу и добавлять):
code text
  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 );
 
US Mishka #09.02.2008 00:11  @Сергей-4030#08.02.2008 20:19
+
-
edit
 

Mishka

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

Давно уже — точно больше 5 лет. Мне, собственно, мужик сказал, который был чемпионов в Молдавии по шашкам. Потом где-то ещё проскакивало. ЕМНИП, моща компов позволила просто просчитать всё.
 
RU GOGI #09.02.2008 00:22  @Сергей-4030#08.02.2008 03:42
+
-
edit
 

GOGI

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

Mishka

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

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

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru