Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 46 47 48 49 50 51 [52] 53 54 55   вперед  Ctrl
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Просматривая старые записи на топике, нашел следующую.
Aleksandr Sharahov
1. Сколько бы вы ни расширяли свой алгоритм включением в него новых алгоритмов, для заданного N в момент испытаний он выдаст фиксированное количество решений.

2. Можно сказать проще. Ваш алгоритм не находит решения, не входящие в его список решений. Т.е. не находит подавляющее большинство решений, причем даже в простейшем случае, когда поставлены все ферзи, кроме одного.
И задумался.

Если сравнивать решения на доске 8х8, 9х9, то можно заметить, что комбинации из 2-х или 3-х чисел участвуют в различных решениях.
Следовательно, на доске NxN установленные М ферзей тоже могут участвовать в построении нескольких решений. И есть вероятность, что одно из этих решений будет описано в существующих алгоритмах.

Тогда с помощью множества МЭА можно будет найти быстро одно из решений. Особенно это важно на очень больших досках.
12 дек 18, 16:38    [21761819]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Дайте определение насыщения.
Задачу насыщения можно сформулировать по-другому.
mayton
Геннадий предположил что насыщение доски n это такая величина ферзей m при которой количество остаточных расстановок резко (очень резко) сокращается.

Надеюсь я близок к определению.
Попробую развить этот тезис.

Пусть имеется доска NxN и на ней существует S решений задачи N ферзей.
Всего будет S x N ферзей.

Предположим, что они равномерно распределены по клеткам доски. На самом деле, есть отдельные области по углам доски и недалеко от центра, где это не так.

Разместим на доске все S решений. Если имеем допущение о равномерности распределения всех ферзей всех решений по клеткам доски, то в одной клетке будет находиться:
S1 = S/N ферзей.
Тогда можно говорить, что с этой клеткой связано S/N решений.

Установим на доске ферзя F1(x1, y1). Тогда в расширении будут участвовать только те ферзи из вертикали х1, которые находятся в клетке y1. И всего этих решений будет S/N.
Можно рассматривать ещё горизонталь y1. Однако, в ней могут находиться ферзи, которые участвует в уже отвергнутых решениях. Поэтому, чтобы не дублировать процесс сокращения решений, варианты с горизонталями пока не рассматриваются. Оценим эту ситуацию в конце этого текста.

Формулу S/N можно объяснить по-другому следующим образом:
через одну из N клеток в вертикали х1 «проходит» S/N решений.

Установив ферзя F1, на доске «убираются» вертикаль х1 и горизонталь y1. Остаётся (N-1) вертикалей и (N-1) горизонталей. Во всех клетках этих вертикалей и горизонталей осталось:
S2 = S/N решений.
Теперь устанавливаем на доске NxN следующего ферзя F2(x2, y2), и применяем предыдущие действия по удалению решений. И на доске NxN останется S/N/(N-1) решений.
Данный процесс можно продолжить: после установки ферзя Fi(xi, yi) на доске NxN останется:
Si = S/N/(N-1)/(N-2)/(N-3)/……/(N-i+1) решений.
Ферзи ставятся до тех пор, пока количество решений будет сравнимо с размером доски (установка следующего ферзя приведет либо к отсутствию решений, либо останется одно решение).
Назовем это пределом насыщения.

Тогда определение:
Пределом насыщения называется предел по количеству устанавливаемых ферзей, после которых на доске NxN могут либо отсутствовать решения, либо останется только одно решение.

Расчеты, проведенные с небольшими досками, показали, что пределы насыщения в процентах количества устанавливаемых ферзей к размеру доски постепенно увеличиваются и на доске 27х27 доходит до 52% от размера доски.
Вместе с тем, поскольку не удалялись решения, которые имеют в своём составе ферзи из клеток в горизонталях (было сказано ранее), то этот процент будет ещё меньше.

Далее, таблица,
размер доски – предел насыщения в процентах
10-30, 11-36, 12-42, 13-38, 14-43, 15-40, 16-44, 17-47, 18-44, 19-47, 20-45, 21-48, 22-45, 23-48, 24-50, 25-48, 26-50, 27-52
14 дек 18, 07:48    [21763616]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1487
Сразу к обоим последним постам.
Красиво на бумаге. На практике мы знаем, что у модельных вычисленных средних всегда будет дисперсия.
Но и этого мало.
(171547, 1)= .09.07.04.08.11.13.06.10.12.01.03.05.02
(470899, 2)= .06.11.09.02.04.13.08.10.12.01.03.05.07
(471385, 3)= .06.11.09.12.04.02.08.10.13.01.03.05.07
(485809, 4)= .08.02.09.12.10.04.06.11.13.01.03.05.07
Паттерн "1 3 5 2", находясь в конце перестановки - единственный (что видно по сортировке). В то же время он много раз встречается в начале и особенно внутри.

Сейчас неохота искать, встречались патерны длиной ~9-10, у к-рых отличались только оставщиеся 4 числа. Отличались перестановкой этих 4-х чисел.

А я бы предпочёл определение в терминах деревьев, как если бы рисовали дерево поиска в глубину.
А то здесь сочетание "предел насыщения" далеко не (а иногда близко не) предел и не насыщения. И для размерностей от ~17 величина предположительная.
14 дек 18, 18:07    [21764323]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
exp98
...А то здесь сочетание "предел насыщения" далеко не (а иногда близко не) предел и не насыщения.


Добавлю, что и мне природный такт не позволяет сказать, что "предел насыщения" - просто бред )
14 дек 18, 18:40    [21764350]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
exp98
Member

Откуда:
Сообщений: 1487
Ну да, это желаемая быть узнанной величина ад хок. Приведённое определение можно считать таковым в начальном приближении, но практической пользы не даёт. Лишь, я думаю, в среднем можно ориентироваться на 50%.
И оказалось, что моя соседняя тема перекликается с задачей завершения и с этим пределом.
14 дек 18, 18:52    [21764362]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
автор
Предположим, что они равномерно распределены по клеткам доски. На самом деле, есть отдельные области по углам доски и недалеко от центра, где это не так.
Aleksandr Sharahov
exp98
...А то здесь сочетание "предел насыщения" далеко не (а иногда близко не) предел и не насыщения.
Добавлю, что и мне природный такт не позволяет сказать, что "предел насыщения" - просто бред )
exp98
Ну да, это желаемая быть узнанной величина ад хок. Приведённое определение можно считать таковым в начальном приближении, но практической пользы не даёт. Лишь, я думаю, в среднем можно ориентироваться на 50%.
И оказалось, что моя соседняя тема перекликается с задачей завершения и с этим пределом.
Определение было получено на основе предположения, что ферзи решений располагаются равномерно по всем клеткам.
На самом деле, как было замечено в сообщении, клетки доски заполняются неравномерно.

Поэтому в реальности, в зависимости от заполнения клеток с установленными ферзями, картина может быть разнородной, плюс минус несколько процентов или более. Например, на доске 9х9 21668862 такой разброс показан для разных клеток.

Насчет практической пользы... Просто при установке ферзей необходимо помнить, что в какой-то момент установка очередного ферзя может быть лишней.
14 дек 18, 19:48    [21764396]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
exp98
На практике мы знаем, что у модельных вычисленных средних всегда будет дисперсия.
Но и этого мало.
(171547, 1)= .09.07.04.08.11.13.06.10.12.01.03.05.02
(470899, 2)= .06.11.09.02.04.13.08.10.12.01.03.05.07
(471385, 3)= .06.11.09.12.04.02.08.10.13.01.03.05.07
(485809, 4)= .08.02.09.12.10.04.06.11.13.01.03.05.07
Паттерн "1 3 5 2", находясь в конце перестановки - единственный (что видно по сортировке). В то же время он много раз встречается в начале и особенно внутри.

Сейчас неохота искать, встречались патерны длиной ~9-10, у к-рых отличались только оставщиеся 4 числа. Отличались перестановкой этих 4-х чисел.
Данная информация - больше познавательная.
На самом деле, намного важнее должна быть другая информация: развитие именно этих дисперсий (перестановок и ещё чего-нибудь) на другие доски, например с шагом 6, 12 и т.д.
Причем, эти
.01.03.05.02
(или
.01.03.05.07
)
должны быть на всех досках либо одинаковыми, либо определяться по одной формуле.

Тогда возможен эвристический алгоритм.
19 дек 18, 19:44    [21768817]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov, ты можешь все исходники собрать в некий единый документ?

Aleksandr Sharahov
Gennadiy Usov
Топик называется "Расстановка ферзей".
Так что с этим всё нормально. Просто - очередной алгоритм расстановки ферзей на произвольной доске.

Чтобы это назвать алгоритмом должна быть сформулирована некая общая задача, которую он решает.
Опишите ее и попросите модератора добавить описание в начало топика.
Пока все эти мелкие специализированные процедуры выглядят как случайно разбросанные куски сломанной игрушки.
Gennadiy Usov
Пока это наброски программ.
Хотя отдельные процедуры можно уже использовать.
Как я ранее сообщал, в МЭА должно войти большое количество алгоритмов. И создание такого множества - довольно длительная работа.

Чтобы их использовать, должен существовать верхний уровень алгоритма, разлагающий N на множители и планирующий генерацию решений. И он должен работать хотя бы для одного N (например, 1000), хотя бы один раз вызывая процедуры из вашего множества алгоритмов (например, состоящего из единственного алгоритма), а также обычные процедуры поиска с возвратом.

Aleksandr Sharahov и mayton,

По всей видимости, вы правы, пока рано МЭА использовать для задачи прикладного варианта задачи N ферзей (задача n-Queens Completion).
С другой стороны, весь материал по МЭА будет удобнее расположить в другом топике – МЭА для математического варианта задачи N ферзей (задача n-Queens).
И здесь каждый желающий попробует написать свой алгоритм для сформулированной задачи.

Пока нет вопросов?
25 дек 18, 19:32    [21773291]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Решил ещё раз рассмотреть матрицу с ограничениями (кажется так это звучит?) на доске NxN, на которой установлены М ферзей.
Если ферзь из М установленных ферзей бьет клетку доски, то в соответствующей клетке матрицы NxN будет 1, иначе будет 0.

На данном топике уже рассматривались такие матрицы.
Если не трудно, то было бы хорошо узнать результаты исследований этих матриц в процессе решения задачи расширения, или ссылки на сообщения об исследовании.
26 дек 18, 16:35    [21774006]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Предел насыщения жив!

Решил попробовать использовать матрицу с ограничениями 21774006 при определении расширения на доске 25х25.

Имеются установленные ферзи: 13 штук:
4 7 0 3 0 18 1 0 2 0 0 0 19 0 0 0 17 0 20 0 5 0 6 9 11

Оказалось, что расширения, т.е. решения, нет!
27 дек 18, 13:26    [21774709]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 38322
Gennadiy Usov
Aleksandr Sharahov и mayton,

По всей видимости, вы правы, пока рано МЭА использовать для задачи прикладного варианта задачи N ферзей (задача n-Queens Completion).
С другой стороны, весь материал по МЭА будет удобнее расположить в другом топике – МЭА для математического варианта задачи N ферзей (задача n-Queens).
И здесь каждый желающий попробует написать свой алгоритм для сформулированной задачи.

Пока нет вопросов?


Ну отлично.

Чем планируешь занятся в отсутствие шахмат?
27 дек 18, 14:07    [21774756]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Мне представляется совсем простая штука -
Предела нет (тут нету трюка):
Поставь, как надо, все фигурки из бамбука,
И удали одну, без звуков и без стука.
27 дек 18, 14:13    [21774763]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Мне представляется совсем простая штука -
Предела нет (тут нету трюка):
Поставь, как надо, все фигурки из бамбука,
И удали одну, без звуков и без стука.
Подстроиться под ситуацию? Так, конечно, проще
27 дек 18, 14:53    [21774841]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
mayton
Gennadiy Usov
Aleksandr Sharahov и mayton,
По всей видимости, вы правы, пока рано МЭА использовать для задачи прикладного варианта задачи N ферзей (задача n-Queens Completion).
С другой стороны, весь материал по МЭА будет удобнее расположить в другом топике – МЭА для математического варианта задачи N ферзей (задача n-Queens).
И здесь каждый желающий попробует написать свой алгоритм для сформулированной задачи.
Пока нет вопросов?
Ну отлично.

Чем планируешь занятся в отсутствие шахмат?
А нет у меня шахмат
27 дек 18, 14:55    [21774845]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
Мне представляется совсем простая штука -
Предела нет (тут нету трюка):
Поставь, как надо, все фигурки из бамбука,
И удали одну, без звуков и без стука.
Подстроиться под ситуацию? Так, конечно, проще


Вам виднее, что делать: хотите - подстраивайтесь, хотите - нет.
Но этот контрпример доказывает, что предела насыщения не существует.
27 дек 18, 15:11    [21774867]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
Подстроиться под ситуацию? Так, конечно, проще
Вам виднее, что делать: хотите - подстраивайтесь, хотите - нет.
Но этот контрпример доказывает, что предела насыщения не существует.
На доске установлено 52 % ферзей, и нет расширения для этих ферзей.

Следовательно, нет смысла ставить 14-го ферзя. Ведь система ( 13 ферзей на доске 25х25) насытилась.
Значит, есть предел насыщения для этой системы.
27 дек 18, 15:17    [21774874]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...
Вам виднее, что делать: хотите - подстраивайтесь, хотите - нет.
Но этот контрпример доказывает, что предела насыщения не существует.
На доске установлено 52 % ферзей, и нет расширения для этих ферзей.

Следовательно, нет смысла ставить 14-го ферзя. Ведь система ( 13 ферзей на доске 25х25) насытилась.
Значит, есть предел насыщения для этой системы.


1. Какое определение предела насыщения вы используете в данный момент?
2. В чем его практический смысл?
3. Как его вычислить?
27 дек 18, 15:26    [21774888]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
На доске установлено 52 % ферзей, и нет расширения для этих ферзей.
Следовательно, нет смысла ставить 14-го ферзя. Ведь система ( 13 ферзей на доске 25х25) насытилась.
Значит, есть предел насыщения для этой системы.
1. Какое определение предела насыщения вы используете в данный момент?
2. В чем его практический смысл?
3. Как его вычислить?
1. Раз есть предел насыщения для отдельной системы ферзей, значит и когда-то будет определение.

2. Практический смысл в том, что не надо много ставить ферзей на доску. А то некоторые программисты говорят, что можно поставить на доску до 90 % (от размера доски) ферзей.

3. Вычислить для данной системы можно, если будем убирать по одному ферзю (любому) до тех пор, пока не будет решение.
27 дек 18, 15:53    [21774916]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...
1. Какое определение предела насыщения вы используете в данный момент?
2. В чем его практический смысл?
3. Как его вычислить?
1. Раз есть предел насыщения для отдельной системы ферзей, значит и когда-то будет определение.

2. Практический смысл в том, что не надо много ставить ферзей на доску. А то некоторые программисты говорят, что можно поставить на доску до 90 % (от размера доски) ферзей.

3. Вычислить для данной системы можно, если будем убирать по одному ферзю (любому) до тех пор, пока не будет решение.


1. В этой ветке было предпринято несколько попыток дать определение предела насыщения . Ни разу не удалось. Более того, всякий раз в зависимости от ситуации появляется новая трактовка. Пока нет непротиворечивого определения и ответов на поставленные вопросы, и говорить не о чем.

2. Много-мало... Вы о чем вообще? Сколько конкретно ферзей ставить? Было показано, что можно поставить хоть N-1 и получить решение. Еще раз: каков практический смысл? Как собираетесь использовать вычисленное значение?

3. Т.е. сначала ставим? Все N как угодно? Потом убираем, пока не решается. А если уже сразу было решение? А если убираем в другом порядке? Это чушь, а не алгоритм вычисления.
27 дек 18, 17:05    [21775013]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
1. Раз есть предел насыщения для отдельной системы ферзей, значит и когда-то будет определение.
2. Практический смысл в том, что не надо много ставить ферзей на доску. А то некоторые программисты говорят, что можно поставить на доску до 90 % (от размера доски) ферзей.
3. Вычислить для данной системы можно, если будем убирать по одному ферзю (любому) до тех пор, пока не будет решение.
1. В этой ветке было предпринято несколько попыток дать определение предела насыщения . Ни разу не удалось. Более того, всякий раз в зависимости от ситуации появляется новая трактовка. Пока нет непротиворечивого определения и ответов на поставленные вопросы, и говорить не о чем.
2. Много-мало... Вы о чем вообще? Сколько конкретно ферзей ставить? Было показано, что можно поставить хоть N-1 и получить решение. Еще раз: каков практический смысл? Как собираетесь использовать вычисленное значение?
3. Т.е. сначала ставим? Все N как угодно? Потом убираем, пока не решается. А если уже сразу было решение? А если убираем в другом порядке? Это чушь, а не алгоритм вычисления.
Самое простое действие при обсуждении алгоритма, который тебе не нравится, это называть алгоритм чушью.

Тогда как объясните казус: есть 13 ферзей на доске 25х25 и нет расширения (решения). Или будете ставить дальше ферзи 14, 15, ..., и до N-1?
27 дек 18, 19:02    [21775146]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...
1. В этой ветке было предпринято несколько попыток дать определение предела насыщения . Ни разу не удалось. Более того, всякий раз в зависимости от ситуации появляется новая трактовка. Пока нет непротиворечивого определения и ответов на поставленные вопросы, и говорить не о чем.
2. Много-мало... Вы о чем вообще? Сколько конкретно ферзей ставить? Было показано, что можно поставить хоть N-1 и получить решение. Еще раз: каков практический смысл? Как собираетесь использовать вычисленное значение?
3. Т.е. сначала ставим? Все N как угодно? Потом убираем, пока не решается. А если уже сразу было решение? А если убираем в другом порядке? Это чушь, а не алгоритм вычисления.
Самое простое действие при обсуждении алгоритма, который тебе не нравится, это называть алгоритм чушью.

Тогда как объясните казус: есть 13 ферзей на доске 25х25 и нет расширения (решения). Или будете ставить дальше ферзи 14, 15, ..., и до N-1?


Я не назвал чушью, а объяснил, почему считаю чушью то, что вы называете алгоритмом.
Что мы имеем на данный момент - предел насыщения это:
1. то, чему нет определения,
2. то, что неясно как можно было бы использовать,
3. то, что непонятно как можно было бы вычислить.

А ваш казус - он казус только для вас, а для алгоритма поиска с возвратом - это нормальное состояние.
27 дек 18, 19:43    [21775196]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
Самое простое действие при обсуждении алгоритма, который тебе не нравится, это называть алгоритм чушью.

Тогда как объясните казус: есть 13 ферзей на доске 25х25 и нет расширения (решения). Или будете ставить дальше ферзи 14, 15, ..., и до N-1?

А ваш казус - он казус только для вас, а для алгоритма поиска с возвратом - это нормальное состояние.
Считаете нормальным, что для 13 ферзей из 25-ти уже нет расширения?
27 дек 18, 19:55    [21775209]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...

А ваш казус - он казус только для вас, а для алгоритма поиска с возвратом - это нормальное состояние.
Считаете нормальным, что для 13 ферзей из 25-ти уже нет расширения?


мне все равно, пусть алгоритм считает
27 дек 18, 19:59    [21775213]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 945
Aleksandr Sharahov
Gennadiy Usov
Считаете нормальным, что для 13 ферзей из 25-ти уже нет расширения?
мне все равно, пусть алгоритм считает
Если Вы это допускаете, то, следовательно, допускаете, что на доске NxN существуют такие построения М ферзей (М <= N/100x52), что расширения для таких построений не существует.
27 дек 18, 20:10    [21775225]     Ответить | Цитировать Сообщить модератору
 Re: Расстановка ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1697
Gennadiy Usov
Aleksandr Sharahov
пропущено...
мне все равно, пусть алгоритм считает
Если Вы это допускаете, то, следовательно, допускаете, что на доске NxN существуют такие построения М ферзей (М <= N/100x52), что расширения для таких построений не существует.


а если мне все равно?
27 дек 18, 20:17    [21775232]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 46 47 48 49 50 51 [52] 53 54 55   вперед  Ctrl
Все форумы / Программирование Ответить