Блафиране?
0 отговора
0 прегледа
Блафиране?
Струва ми се, че krassiholmz чисто и просто блафира с очевидната цел
да изплаши потенциалната конкуренция. Ето някои съображения, защо
аз смятам така.
1) За да бъде алгоритм, какъвто и да е той, по-ефективен, пермутациите
генериращи групата трябва да се реализират като масиви
(а не като функции). За 8-ми huge тест това значи най-малко
4*658*0.5М = 1.3G. Т.е. за бръкма с 256М RAM (или дори с 512М като у жури),
практически всички изчисления ще протичат в swap файла, и за 30 секунди
(а дори и 1 минута) може само да се мечтае
2) Но, да предположим, че програмата е вървяла на машина с 2 или повече
G RAM. Или пък генераторите на групата бяха реализирани като функции.
Да предположим, че krassiholmz е намерил наистина решение от
1.628.135 хода. Колко време ще е нужно на журито да провери,
дали това е решение? Очевидно на него ще му потрябват
броя на квадрати X броя на ходове елементарни проверки.
Това значи 0.5М по 1.5М = 750 000000000 проверки! Което ще отнеме
време от порядъка на едно денонощие, ако не и повече!
А време за намиране на решение очевидно не може да бъде по-малко
от време за неговата проверка.
Стига вече с този krassiholmz, ще напиша някои съображения за самите
алгоритми и предели на техните възможности.
Класически алгоритм за изследване на някоя подгрупа на групата на
пермутации, породена от дадено семейство на генераторите,
е алгоритм на Шрайер-Симс. По-точно, това е едно семейство от
алгоритми. Най-бързите от това семейство (т.н. Монте-Карло или Лас Вегас)
са недетерминистични. Има една freeware система -- GAP, в която тези
алгоритми бяха реализирани, само че не на С, а на някакъв си интерпретатор.
Границите на тази реализация: за дъска 19х21 алгоритм, изчисляващ т.н.
силно генериращо семейство от генератори върви 75 сек
(процессор: AMD64 3200+, 1G RAM). Моята реализация на С++ на една
саморъчно направена (не можах да намеря в интернет никакво описание на
оригиналните Лас Вегас алгоритми) евристична версия на Лас-Вегас съкращава това време почти 30 пъти -- до 2.7 секунди.
А за дъска 25х25 времето е вече 10 сек
(колко време върви GAP -- не знам, нямах търпение да дочакам до края).
Е, това са горе-долу границите на възможности на Шрайер-Симс за дадена
задача. А и това е само част от задачата. Шрайер-Симс дава представяне
на произволен елемент на групата не като произведение на първоначалните
генератори, а като произведение на генератори от силно генериращо семейство. Тези генератори образуват една йерархия, в която генератори
от по-високо стъпало се изразяват като произведение от най-малко 3 генератора от предходно стъпало. Броя на стъпалата за нашия случай
е N*M-1, ако N или M е четно или N*M-2 в противния случай. С други думи,
групата породена от "шифтинги" съвпада с групата на всички пермутации
на N*M елемента или с нейната подгрупа от всички четни пермутации
(в зависимост от четностите на N и M). Не мога да го докажа като теорема,
но то се подтвърждава експериментално за всички 1<N,M<=25 -- това го проверих с моята програма. И ето откъде идва трудност: Шрайер-Симс ще
ни даде израз на елемент g, преместващ началната дъска в крайната, като
произведение на N*M-1 или N*M-2 елемента, като първи елемент е произведение на някои шифтинги (най-ниското стъпало на иерархията),
а всеки следващ елемент в това разложение ще принадлежи към с единица
по-високо стъпало отколкото предишния. Последен елемент е от най-високото
стъпало. От всичко това се вижда, че последния елемент в разложението
ще е произведение от най-малко 3^(N*M) шифтинга, което няма да се побере нито в RAM, нито в 100-терабайтов масив от дискове. Дори при N=M=10!
Разбира се, при рекуррентното изразяване на елементите от по-високо ниво
чрез тези от по-ниските нива използването на съотношения от типа на
Li^N=1, Li*Lj=Lj*Li и т.д. може да намали дължината на израза много пъти,
но и това няма да е достатъчно за да се получи израз с приемлива дължина.
По-нататък може да се търсят повтарящи се поддуми Х^n, да се търси периода
m на Х, и ако n%m<n, да се замени поддума Х^n на Х^(n%m). И т.д.
Но за такива игри аз вече нямам време...
Това е. Прилагането на Шрайер-Симс към тази задача води до задънена улица.
Дори ако е възможен ефективен алгоритм на "компресиране" на дължините
на търсимия израз, приложимостта му е ограничена до дъски с не
повече от 1000 квадрати (при ограничение от 30 секунди).
Какви други начини може да се ползват? Аз лично се отказах от самото начало
от всякакви вариации на тема greedy алгоритми (увеличаваме числото на
съвпадащи по цвят точки (или пък намаляваме Манхаттънско разстояние)
докогато е възможно, след което правим няколко случайни шифтинга и
продължаваме докато квадратчета се наредят някак си сами по себе си).
От друга страна, както се вижда, тестовете на журито предоставени
за тренинг, не са много
сложни от гледна точка на теория на групите: дори и един милион
случаини завъртания се намират на много голямо разстояние от наистина
дълги възможни думи. Може би има алгоритм, отчитащ това обстоятелство,
само че аз не го виждам?
Ако все пак има такъв, аз подозирам, что той ще се
провали на следващ простичек тест:
10 10 100
1 2 3 4 5 6 7 8 9
10 11 12...100 99
С други думи в този тест трябва да се намери представяне на
една елементарна транспозиция (99 100) чрез шифтинги.
Тя, както аз писах горе, със СИГУРНОСТ може да се представи
като произведение на шифтинги. Само че не е възможно
да бъде сгенерирана по случаен начин.
да изплаши потенциалната конкуренция. Ето някои съображения, защо
аз смятам така.
1) За да бъде алгоритм, какъвто и да е той, по-ефективен, пермутациите
генериращи групата трябва да се реализират като масиви
(а не като функции). За 8-ми huge тест това значи най-малко
4*658*0.5М = 1.3G. Т.е. за бръкма с 256М RAM (или дори с 512М като у жури),
практически всички изчисления ще протичат в swap файла, и за 30 секунди
(а дори и 1 минута) може само да се мечтае
2) Но, да предположим, че програмата е вървяла на машина с 2 или повече
G RAM. Или пък генераторите на групата бяха реализирани като функции.
Да предположим, че krassiholmz е намерил наистина решение от
1.628.135 хода. Колко време ще е нужно на журито да провери,
дали това е решение? Очевидно на него ще му потрябват
броя на квадрати X броя на ходове елементарни проверки.
Това значи 0.5М по 1.5М = 750 000000000 проверки! Което ще отнеме
време от порядъка на едно денонощие, ако не и повече!
А време за намиране на решение очевидно не може да бъде по-малко
от време за неговата проверка.
Стига вече с този krassiholmz, ще напиша някои съображения за самите
алгоритми и предели на техните възможности.
Класически алгоритм за изследване на някоя подгрупа на групата на
пермутации, породена от дадено семейство на генераторите,
е алгоритм на Шрайер-Симс. По-точно, това е едно семейство от
алгоритми. Най-бързите от това семейство (т.н. Монте-Карло или Лас Вегас)
са недетерминистични. Има една freeware система -- GAP, в която тези
алгоритми бяха реализирани, само че не на С, а на някакъв си интерпретатор.
Границите на тази реализация: за дъска 19х21 алгоритм, изчисляващ т.н.
силно генериращо семейство от генератори върви 75 сек
(процессор: AMD64 3200+, 1G RAM). Моята реализация на С++ на една
саморъчно направена (не можах да намеря в интернет никакво описание на
оригиналните Лас Вегас алгоритми) евристична версия на Лас-Вегас съкращава това време почти 30 пъти -- до 2.7 секунди.
А за дъска 25х25 времето е вече 10 сек
(колко време върви GAP -- не знам, нямах търпение да дочакам до края).
Е, това са горе-долу границите на възможности на Шрайер-Симс за дадена
задача. А и това е само част от задачата. Шрайер-Симс дава представяне
на произволен елемент на групата не като произведение на първоначалните
генератори, а като произведение на генератори от силно генериращо семейство. Тези генератори образуват една йерархия, в която генератори
от по-високо стъпало се изразяват като произведение от най-малко 3 генератора от предходно стъпало. Броя на стъпалата за нашия случай
е N*M-1, ако N или M е четно или N*M-2 в противния случай. С други думи,
групата породена от "шифтинги" съвпада с групата на всички пермутации
на N*M елемента или с нейната подгрупа от всички четни пермутации
(в зависимост от четностите на N и M). Не мога да го докажа като теорема,
но то се подтвърждава експериментално за всички 1<N,M<=25 -- това го проверих с моята програма. И ето откъде идва трудност: Шрайер-Симс ще
ни даде израз на елемент g, преместващ началната дъска в крайната, като
произведение на N*M-1 или N*M-2 елемента, като първи елемент е произведение на някои шифтинги (най-ниското стъпало на иерархията),
а всеки следващ елемент в това разложение ще принадлежи към с единица
по-високо стъпало отколкото предишния. Последен елемент е от най-високото
стъпало. От всичко това се вижда, че последния елемент в разложението
ще е произведение от най-малко 3^(N*M) шифтинга, което няма да се побере нито в RAM, нито в 100-терабайтов масив от дискове. Дори при N=M=10!
Разбира се, при рекуррентното изразяване на елементите от по-високо ниво
чрез тези от по-ниските нива използването на съотношения от типа на
Li^N=1, Li*Lj=Lj*Li и т.д. може да намали дължината на израза много пъти,
но и това няма да е достатъчно за да се получи израз с приемлива дължина.
По-нататък може да се търсят повтарящи се поддуми Х^n, да се търси периода
m на Х, и ако n%m<n, да се замени поддума Х^n на Х^(n%m). И т.д.
Но за такива игри аз вече нямам време...
Това е. Прилагането на Шрайер-Симс към тази задача води до задънена улица.
Дори ако е възможен ефективен алгоритм на "компресиране" на дължините
на търсимия израз, приложимостта му е ограничена до дъски с не
повече от 1000 квадрати (при ограничение от 30 секунди).
Какви други начини може да се ползват? Аз лично се отказах от самото начало
от всякакви вариации на тема greedy алгоритми (увеличаваме числото на
съвпадащи по цвят точки (или пък намаляваме Манхаттънско разстояние)
докогато е възможно, след което правим няколко случайни шифтинга и
продължаваме докато квадратчета се наредят някак си сами по себе си).
От друга страна, както се вижда, тестовете на журито предоставени
за тренинг, не са много
сложни от гледна точка на теория на групите: дори и един милион
случаини завъртания се намират на много голямо разстояние от наистина
дълги възможни думи. Може би има алгоритм, отчитащ това обстоятелство,
само че аз не го виждам?
Ако все пак има такъв, аз подозирам, что той ще се
провали на следващ простичек тест:
10 10 100
1 2 3 4 5 6 7 8 9
10 11 12...100 99
С други думи в този тест трябва да се намери представяне на
една елементарна транспозиция (99 100) чрез шифтинги.
Тя, както аз писах горе, със СИГУРНОСТ може да се представи
като произведение на шифтинги. Само че не е възможно
да бъде сгенерирана по случаен начин.