Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
Привед други! Шахматуны и базисты.

В продолжение задачи о 1000 ферзях http://www.sql.ru/forum/1270505/pyatnichnaya-zadachka-dlya-uma-za-1-million

Допустим найдена расстановка ферзей для доски 8x8

+
Картинка с другого сайта.

Расстановка сохраняется в БД в виде:

insert into queen8x8(id,position) values(1,'a1b5c8d6e3f7g2h4');

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

Мы можем по логике приложения или по триггеру добавить еще несколько
строк в queen8x8 которые учитывают "развороты" и "зеркала".

В задаче также подразумевается что мы можем делать поиск решений по
частичному совпадению. Тоесть найти все комбинации которые соответствуют
некой стартовой расстановке.

select * from queen8x8 where position like 'a1b5__d6e__7g2__';


Возник вопрос. Можем-ли мы создать Domain-Index который будет
учитывать этот момент? Ради экономии места. Для доски 1000х1000 клеток.

P.S. Не спрашивайте зачем это надо. Считайте что это - просто мозговой штурм
и вопрос "зачем" уже пройден и стоит вопрос "как".
30 сен 17, 18:51    [20833611]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
booby
Member

Откуда:
Сообщений: 1484
mayton,
like 'a1b5__d6e__7g2__'

я-то дома, сам с собой, русским языком всегда разговариваю...

кто такая
like 'a1b5__d6e__7g2__'

?
Следует ли понимать, что это такая b5, которая в субботу вечером стоит на второй позиции записи "решения"?

А кто такие d6e и 7g2? Для ослабленного субботой взгляда тут либо e и 7 лишние, если образец фиксирует расстановку, либо прилично было бы явить миру, как они связаны с определением "домена".

А доменный индекс можно построить по любой детерминированной функции, возвращающий скалярное значение само по себе пригодное для индексации.
До 12.2 можно изобретать форму записи, умеющую отображать факт того, что тебя интересует
ферзь установленный в 4й вертикали на 6й горизонтали (что-то вроде '001005006%' для начала твоей недоопознаваемой кодировки), или что-то другое, для чего сгодился бы вариант такого текстового индекса.
В 12.2 можно строить индексы на json-полях.
--------------
PS
Попробуй выразить свои мысли на Прологе.
Может быть это приведет к совсем другой форме вопросов про индексы.
30 сен 17, 19:49    [20833670]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
booby
Member

Откуда:
Сообщений: 1484
booby,
ой, для 1000 4 знакоместа потребуется...
30 сен 17, 19:55    [20833678]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
booby
Member

Откуда:
Сообщений: 1484
booby
booby,
ой, для 1000 4 знакоместа потребуется...

угу и '00010005____0006%'
30 сен 17, 20:12    [20833695]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
booby
?
Следует ли понимать, что это такая b5, которая в субботу вечером стоит на второй позиции записи "решения"?

А кто такие d6e и 7g2?

Да. Опечатка.
30 сен 17, 20:14    [20833702]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
booby
А доменный индекс можно построить по любой детерминированной функции, возвращающий скалярное значение само по себе пригодное для индексации.

Почти готов согласиться. Но в чем тогда разница между доменным индексом и индексом по функции?
30 сен 17, 20:17    [20833704]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
xtender
Member

Откуда: Мск
Сообщений: 4684
Прочитал только статью с мейлру специально, чтобы дать мозгу подумать без подсказок и не верится, что это такая уж тяжелая задача: каждый ферзь стоит на своей отдельной горизонтали/вертикали, так разве трудно для современных машин проверить такое... можно даже наверное взять 1024 для ровной битовой маски.
30 сен 17, 21:21    [20833819]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
booby
Member

Откуда:
Сообщений: 1484
mayton,
эти термины могут использоваться как синонимы.

Но, кроме того, под доменными индексами специфически понимаются специальные конструкции, живущие в собственных таблицах, снабженных вполне обычными индексами, поиск по которым идет специальными функциями.
В частности, текстовые индексы в рамках Oracle Text, поддерживаются таблицами и кодом, живущим в схеме ctx, и текстовые индексы CTX - именно доменные индексы во втором смысле.
А json-индексы - синтаксический сахар над текстовыми.
Т.е. для поддержки доменных индексов нужна а) доменная математика, раскрывающая "смысл домена", б) вспомогательные (обычные)таблицы/индексы/код обеспечивающие поиск, контекст которого специфичен для домена.
В этом смысле доменные индексы могут никак не соотносится с тем, что обычно понимается под индексами, и даже не иметь формы стандартного синтаксического объявления.
Хотя для доменов поддерживаемых из коробки самим oracle, что-то на уровне синтаксиса как правило дается.
30 сен 17, 21:34    [20833829]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
xtender
Прочитал только статью с мейлру специально, чтобы дать мозгу подумать без подсказок и не верится, что это такая уж тяжелая задача: каждый ферзь стоит на своей отдельной горизонтали/вертикали, так разве трудно для современных машин проверить такое... можно даже наверное взять 1024 для ровной битовой маски.

Проверить - можно. Это не сложно. Я-же говорю. Спрашивать "зачем" - не стоит.
30 сен 17, 21:40    [20833833]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
booby
Member

Откуда:
Сообщений: 1484
xtender
Прочитал только статью с мейлру специально, чтобы дать мозгу подумать без подсказок и не верится, что это такая уж тяжелая задача: каждый ферзь стоит на своей отдельной горизонтали/вертикали, так разве трудно для современных машин проверить такое... можно даже наверное взять 1024 для ровной битовой маски.

существо дело в вычислительной сложности задачи.
Логически задачу можно видеть как разделенную на две части:
1) сгенерировать все возможные комбинации расположения n ферзей на доске nxn
2) отобрать среди них "правильные" - применительно к ферзям - такие, где на каждой вертикали расположен ферзь и он не бьется никаким другим из расставленных.

В своей сути это арифметическая задача, описание которой есть у Гика в книжке "Шахматы и математика":
Дан набор числе от 1 до n
Частным решением считается последовательность числе от 1 до n такая что:
- все числа использованы
- ни одно не повторяется дважды
- если n - максимальный (последний) номер, i - номер позиции, а f(i) - число записанное в позиции i, то:
а) последовательность f(i) + i дает набор не повторяющихся чисел и
b) последовательность f(i) + n - i + 1 также дает набор не повторяющихся чисел.

Для таких наборов известно, что если i,j - позиции и i<j<=n, то abs(f(i)-f(j)) <> (j - i)

Первоначальный вопрос - как получить все возможные расстановки.
Обсуждаемый на миллион вопрос - о получении подмножества расстановок на доске 1000x1000 таких, что занятость части позиций есть входное условие задачи при условии, что решения могут быть получены за полиномиальное время.

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

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

Применительно к базам данных вопрос - как ускорить двухфазный процесс, состоящий из фазы записи набора данных в таблицу и фазу наложения фильтра, путем резкого сокращения объема данных на фазе добавления записей.
30 сен 17, 22:28    [20833862]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
Stax
Member

Откуда: Ukraine,Lviv
Сообщений: 615
mayton

P.S. Не спрашивайте зачем это надо. Считайте что это - просто мозговой штурм
и вопрос "зачем" уже пройден и стоит вопрос "как".



автор

Ученые из Сент-Эндрюсского университета (Великобритания) предложили миллион долларов за разгадку старинной шахматной задачи. Об этом сообщается на сайте университета.
...
Решение для стандартной доски в 64 клетки было найдено еще в 1850 году. С увеличением размеров поля и количества фигур задача усложняется. Исследователи обнаружили, что если размер доски увеличить до 1000 на 1000 клеток, компьютерные программы начинают зависать.
...


.....
stax
1 окт 17, 11:58    [20834269]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
Все прочитайте топик-родитель сначала.
1 окт 17, 13:03    [20834368]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 4901
mayton
в чем тогда разница между доменным индексом и индексом по функции?
В том, что для доменного индекса создаются вспомогательные структуры - поковыряй для примера Oracle Text.
Индекс по функции просто индексирует выражение.
Для твоей задачи пишешь функцию которая приводит выражение к "канонической форме" и ее индексируешь.
mayton
Все прочитайте топик-родитель сначала.
Для человека с computer science образованием тот топик не несет никакой дополнительной смысловой нагрузки.

В программировании часто очень проблематично доказать, что более простого алгоритма не существует,
поэтому некоторые универы могут стебаться над дилетантами формулируя подобные задачи.

Возвращаясь к реальному миру, в 99% случае надо найти не все решения, а оптимальное. А уже для него есть ряд устоявшихся подходов.
Я еще много лет назад экспериментировал с генетическим алгоритмом, который прекрасно находил решение для 1000+ ферзей на моем слабеньком писюке.

PS. Не совсем понятно почему ты решил влезть с этой "оригинальной" задачей именно в ветку Оракл.
1 окт 17, 14:11    [20834491]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
dbms_photoshop
PS. Не совсем понятно почему ты решил влезть с этой "оригинальной" задачей именно в ветку Оракл.

Ищу применение для DI. Ферзи - просто повод.
1 окт 17, 18:17    [20834733]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
_Nikotin
Member

Откуда: СПб
Сообщений: 2961
mayton,

Молекулы индексировали как-то.
1 окт 17, 20:31    [20834881]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
dbms_photoshop
Member

Откуда: sqlmdx.net
Сообщений: 4901
mayton
dbms_photoshop
PS. Не совсем понятно почему ты решил влезть с этой "оригинальной" задачей именно в ветку Оракл.

Ищу применение для DI. Ферзи - просто повод.

http://docs.oracle.com/database/121/ADDCI/ext_idx_frmwork.htm#ADDCI4390
When to Use Extensible Indexing
Oracle's built-in indexing facilities are appropriate to a large number of situations. However, as data becomes more complex and applications are tailored to specific domains, situations arise that require other approaches. For example, extensible indexing can help you solve problems like these:

Implementing new search operators using specialized index structures

You can define operators to perform specialized searches using your index structures.

Indexing unstructured data

The built-in facilities cannot index a column that contains LOB values.

Indexing attributes of column objects

The built-in facilities cannot index column objects or the elements of a collection type.

Indexing values derived from domain-specific operations

Oracle object types can be compared with map functions or order functions. If the object uses a map function, then you can define a function-based index for use in evaluating relational predicates. However, this only works for predicates with parameters of finite range; it must be possible to precompute function values for all rows. In addition, you cannot use order functions to construct an index.


И в том же Data Cartridge Developer's Guide конкретные примеры
Part III Scenarios and Examples
Click to expand 15 Power Demand Cartridge Example
Click to expand 16 PSBTREE: Extensible Indexing Example

Обрати внимание, что функция ODCIIndexCreate для user defined domain indexes создает и вставляет данные во вспомогательную таблицу(цы).
1 окт 17, 20:54    [20834897]     Ответить | Цитировать Сообщить модератору
 Re: Субботний шахматун 1000х1000  [new]
mayton
Member

Откуда: loopback
Сообщений: 35695
dbms_photoshop, OK спасибо.
1 окт 17, 21:07    [20834908]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить