Задумался о том, какая связь между Генетическими Алгоритмами и методом PTA двух челов из Utah.
Общего много. Подход к отбору. Берем случайные хромосомы. Далее. Мутации и кроссовера нет.
Но зато есть забавный обмен местами признаков в одной удачной хромосоме. Если не быть педантами
и представить что ГА это вовсе не алгоритм а скорее философский принцип отбора и селекции решений.

Еще мысль. PTA(Polynominal Time Algorithm) в силу особенностей ГА будет выдавать нам решения
с хорошей скоростью только на старте. (Ее можно оценить). Со временем эта скорость будет падать.
Мы будем попадать в "distinct solutions". Количество решений будет стремиться к финальному но не
скоро достигнет его. В конце (когда потухнет солнце и космос будет состоять из редких black-holes),
мы все таки найдем последнее решение (ведь их количество - счетное) однако комбинаторный алгоритм
нас может к тому времени обогнать. (Это тоже надо оценить).

Если мы откажемся от "случайности" в выборе вектора ферзей в PTA и заменим его на псевдо-случайность
то тогда есть надежда что генерация решений будет более осмысленная. Без distinct. Правда локальные
минимумы подкинут свинью. Надо решить как быть с ними. Или тоже подвергнуть их псевдо-случайным
перестановкам.

Aleksandr SharahovНемного погонял алгоритм. Впечатление нереальности происходящего не покидает.
В то время как при N=100 можем запросто 50 раз подряд попасть в яму, при N=50000 решение всегда (насколько хватило терпения жмакать кнопку) находится с первой попытки.
Не-ре-аль-но... может у тебя снова бага. Как с зеркалом.

Попытался изобразить свою мысль. Я ввожу функцию X(n)
(это не "Икс" а это я пытался нарисовать греческую букву "Хи")
которая будет возвращать общее количество решений ферзевой
задачи для размера доски n, включая зеркала и развороты.

Вобщем синий график - это наш рекурсивный факториальный
брутфорс. А красный это полиномиальный искатель случайных
решений.

tip78Aleksandr Sharahovпропущено...


Это точно, у меня зеркальная (лево-право) бьет по скорости даже двойную зеркальную (лево-право, верх-низ).
да у вас прогресс!
Aleksandr Sharahovmayton,

зачем вообще возиться с зеркалированием?

Ведь в нашем случае:
1. при поиске всех перестановок зеркалирование не дает выигрыша по времени,
2. никто не спрашивает, сколько уникальных решений было найдено.
неужели таки осилили мою идею зеркалирования?
осталось только понять, зачем вы считаете все 4 квадрата ))
Я-бы здесь дополнил сам себя. Считаю что расчет зеркал и разворотов
не приближает нас к финалу (к полному перерасчету всех ферзевых решений).
Имея 1 решение мы всегда (за константное время) расчитаем всех его братьев.
Но есть технические приёмы, работы с матрицами на аппаратной архитектуре x86.
В учебных примерах на wiki мы обходим клетки сверху вниз. Профанация! Нужно
сменить направление.

tip78, а зачем вам простые числа?

kealon(Ruslan)mayton,

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

По сабжу. Я чем дольше думаю о BackTracking и Polynomial то тем больше понимаю что это настолько разные
алгоритмы что их пора разделить на два топика а модератора просить выкосить все рефералы и сравнения.

Они - разные и решают разные задачи.

Кажется что уже где-то проговорили что не будем хранить найденные значения но... нет
кто-то снова спрашивает а куда дескыть мы их положим? Какая нахер разница для BackTracking! Он итерирует весь
континуум! Вобщем... жутко бесит.

Хочется спросить. Товарищь! Ты сейчас о каком АЛГОРИТМЕ говорил?

Бесит тема зеркалирования и разворотов. Какое это имеет значение?! Родные! Мы импрувим асимптоматику!
Мы решаем вопросы теории пределов. Какое имеет значение добавите вы коефициентик или нет! Вообще ни разу не играет роли!
Не влияет. Не оказывает. Не помогает.

Сорян друзья. Пойду накапаю себе капель...

Понаблюдал за ферзями на примере доски 8х8. Они не одинаковые. Тоесть
они как фигуры - одинаковые но в зависимости от позиции - кроют разное
число клеток. К примеру ферзь в углу кроет только 1+7+7+7 = 22 клетки.
Ферзь в центре - до 28 клеток.

Можно сказать что "центровой" ферзь - рангом повыше.

Если алгоритм BackTracking будет делать проверки не в декартовом
порядке а в порядке старшинства рангов - то весть мысль что мы
быстрее будем проскакивать рекурсивные ямы.

Какой смысл в блог толкать исходники? КМК уместно опубликовать формулу или идею.

Просто ИМХО.