Здравствуйте, dilmah, Вы писали:

D>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

Ужас! Неужели ожидаемое решение — полный перебор?

Если бы я был царь, то я бы сделал поиск с приоритетами.

Состояние = карта + пробег (количество итераций от исходной карты).
Карте соответствует дальность — нижняя оценка расстояния до финальной карты, равная сумме кратчайших путей всех шариков до своих лунок, без учёта коллизий.
Состоянию соответсвует вес = пробег + дальность.

Заведём реестр карта->пробег встреченных карт и приоритетную очередь вес->состояние.

Дальше всё просто.
Извлекаем очередное состояние и порождаем следующие за ним (их пробег, соответственно, инкрементирован).
Если карты этих состояний уже есть в реестре, и тамошние пробеги меньше-или-равны нынешним — игнорируем их.
Если карта уже встречалась, но мы улучшили её пробег, то
— передвигаем её вперёд по очереди
— обновляем реестр
Если карта новая — то просто добавляем в очередь и обновляем реестр.

Здравствуйте, Кодт, Вы писали:

К>Ужас! Неужели ожидаемое решение — полный перебор?

Оно не такое уж и плохое. Для такой карты количество вариантов совсем маленькое.

К>Состояние = карта + пробег (количество итераций от исходной карты).
К>Карте соответствует дальность — нижняя оценка расстояния до финальной карты, равная сумме кратчайших путей всех шариков до своих лунок, без учёта коллизий.

Без учета коллизий — это значит мы не учитываем другие шарики?

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

А,B — шарики
1,2 — лунки для A,B

C учетом других шариков - наклон влево, затем вниз
. B A .
. . . .
. 1 . .
2 . . .

Без учета других шариков - пути нет.
. . A .
. . . .
. 1 . .
. . . .

Или под коллизиями понималось что-то другое?

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, dilmah, Вы писали:

D>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.

К>Ужас! Неужели ожидаемое решение — полный перебор?

Нет, полный перебор — это brute force. А здесь bfs.

К>Если бы я был царь, то я бы сделал поиск с приоритетами.

А я бы сделал так, как описал выше, и работать будет быстро.

К>Ужас! Неужели ожидаемое решение — полный перебор?

К>Если бы я был царь, то я бы сделал поиск с приоритетами.

К>Состояние = карта + пробег (количество итераций от исходной карты).
К>Карте соответствует дальность — нижняя оценка расстояния до финальной карты, равная сумме кратчайших путей всех шариков до своих лунок, без учёта коллизий.

не ясны детали.
Нужно найти минимальное расстояние, а не "приблизительно" минимальное расстояние.
То есть надо быть уверенным что более короткого нет.
Я не совсем понял деталей как ты будешь давать минимальную оценку расстояния.
Во первых, за один ход шарики катятся "до упора".
Поэтому тривиальная нижняя оценка обычна равна 2, 3 или 4.
По моему учет этой оценки будет давать околонулевой выигрыш при значительно усложняющемся коде.

Здравствуйте, dilmah, Вы писали:

D>не ясны детали.
D>Нужно найти минимальное расстояние, а не "приблизительно" минимальное расстояние.

Приблизительно минимальное (оценка снизу) нужно для упорядочивания очереди.
Ибо, фронт разрастается экспоненциально, и надо сперва проверять наиболее симпатичные состояния.

D>Во первых, за один ход шарики катятся "до упора".

Упс! Этот момент я как-то упустил. Почему-то решил, что шарики ходят, как в игре lines.
Тогда буду думать по-новой

К>Ибо, фронт разрастается экспоненциально

можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

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

P.S.
Еще полезно использовать свойство идемпотентности хода -- сделать ход 2 раза в одну сторону это все равно что сделать ход 1 раз. Из этого следует простой но полезный факт что если состояние принадлежит цепочке решения, то найдется такой ход для которого это состояние явлется неподвижной точкой.

Здравствуйте, dilmah, Вы писали:

К>>Ибо, фронт разрастается экспоненциально

D>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

D>Первая проблема -- обратный ход дает не одно состояние а несколько, а иногда и очень много.. Но обычно их не очень много и их можно быстро найти, если аккуратно реализовать это. Но еще проблема в том что эффективно реализовать "обратный ход" очень трудоемко.

D>P.S.
D>Еще полезно использовать свойство идемпотентности хода -- сделать ход 2 раза в одну сторону это все равно что сделать ход 1 раз. Из этого следует простой но полезный факт что если состояние принадлежит цепочке решения, то найдется такой ход для которого это состояние явлется неподвижной точкой.

Тоже думал об этом, но обратный ход дает очень много вариантов, которые сложно просчитывать. Хотя, может оказаться, существенно меньше, чем быстро разрастающие варианты прямых ходов. Хотя бы тот пример с тремя лунками. На последнем ходу мог закатиться один шар, тогда он мог закатиться из 7 положений (без стенок, со стенками может быть меньше). Можно ограничиться, правда, не 7-ю а меньшим числом вариантов, т.к. шар должен касаться стенки или другого шара на каждом шаге (будет, правда, усложнение алгоритма просчета). На последнем ходу могло закатиться 2 шара (3 варианта выбора какие именно два). Из скольки положений -- они катились с одной стороны, например, сверху, каждый из ui вариантов. Т.е. будет что-то u1*u2+r1*r2+d1*d2+l1*l2 вариантов. Но тут надо еще учесть, что лунки могут стоять рядом. Для трех шаров еще куча вариантов. Для каждого варианта еще один ход назад даст еще тучу вариантов. Короче, если и просчитывать так, то надо следующим образом: просчитать один ход назад, посмотреть, сколько вариантов получилось, и считать сначала, пока не наберется такое же число вариантов. Далее просчитать еще на один ход назад, снова считать вперед, пока не компенсирует, и т.д.

Здравствуйте, dilmah, Вы писали:

D>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

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

А как проверить, что задача не решаема?

D>>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

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

AJD>А как проверить, что задача не решаема?

дождаться пока фронт выдохнется

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

Здравствуйте, dilmah, Вы писали:

К>>Ибо, фронт разрастается экспоненциально

D>можно попробовать вести 2 фронта -- из начала и из конца. Фактически половинится путь который нужно пройти -- половинится показатель экспоненты.

А можно вопрос.. Какую именно экспоненту мы пробуем половинить?

D>Первая проблема -- обратный ход дает не одно состояние а несколько, а иногда и очень много.. Но обычно их не очень много и их можно быстро найти, если аккуратно реализовать это. Но еще проблема в том что эффективно реализовать "обратный ход" очень трудоемко.

D>P.S.
D>Еще полезно использовать свойство идемпотентности хода -- сделать ход 2 раза в одну сторону это все равно что сделать ход 1 раз. Из этого следует простой но полезный факт что если состояние принадлежит цепочке решения, то найдется такой ход для которого это состояние явлется неподвижной точкой.

_DA>А можно вопрос.. Какую именно экспоненту мы пробуем половинить?

хороший вопрос. Ту экспоненту которая растет с каждым ходом из-за 3 вариантов ходов.
Конечно она гасится тем что состояния повторяются и все ограничено общим кол-вом состояний. Поэтому если общее кол-во состояний не велико, то как бы экспонента уже погашена.

Но в формулировке задачи которую я получал от CQG в свое время размер поля был ограничен 40x40, с неограниченным кол-вом стенок и дырок.

Может подскажите, как запоминать положение шариков на доске, чтобы хранить их(положения) для всех состояний пройденного пути у дерева? Каждый узел нижнего уровня хранить все состояния доски пройденного пути от корня. Нужно для того, чтобы избежать зацикливания. Запоминать координаты всех шариков на доске и хранить их в векторе накладно, т.к. путь до решения может быть довольно долгим. Замечу, что именно координаты шариков не нужны, нужен некий "слепок", чтобы в каждом состоянии можно было посмотреть, а не было ли такого же состояния ранее при спуске. Первое, что пришло на ум, это hash функция. Но как её подобрать, какая вероятность колизий при спуске через 1600 вершин? Пока на доске 1600 клеток, в худшем случае шарик пройдет все 1600 клеток до цели. Но шариков может быть и больше.

C>Может подскажите, как запоминать положение шариков на доске, чтобы хранить их(положения) для всех состояний пройденного пути у дерева? Каждый узел нижнего уровня хранить все состояния доски пройденного пути от корня. Нужно для того, чтобы избежать зацикливания. Запоминать координаты всех шариков на доске и хранить их в векторе накладно, т.к. путь до решения может быть довольно долгим. Замечу, что именно координаты шариков не нужны, нужен некий "слепок", чтобы в каждом состоянии можно было посмотреть, а не было ли такого же состояния ранее при спуске. Первое, что пришло на ум, это hash функция. Но как её подобрать, какая вероятность колизий при спуске через 1600 вершин? Пока на доске 1600 клеток, в худшем случае шарик пройдет все 1600 клеток до цели. Но шариков может быть и больше.

Не понимаю зачем хранить все состояния пройденного пути до корня.
В каждом узле нужно хранить указатель на предыдущее состояние (чтобы когда/если прийдешь в конечное состояние можно было отследить путь которым пришел).
Кроме того нужно вести один глобальный std::set содержащий все посещенные состояния (чтобы не зациклиться).

(С учетом того что нужно параллелить алгоритм, то нужно сделать lock striping этого множества).

Здравствуйте, dilmah, Вы писали:
D>Не понимаю зачем хранить все состояния пройденного пути до корня.

Мне нужны только положения шариков на доске, для того чтобы исключить движение шарика по одному пути. Например циключно по краю доски, можно придумать целый лабиринт, когда шарик будет двигаться по замкнутому контуру бесконечно.
И количество шагов сразу вряд ли будет предсказуемым.

D>В каждом узле нужно хранить указатель на предыдущее состояние (чтобы когда/если прийдешь в конечное состояние можно было отследить путь которым пришел).
В самом состоянии можно хранить пройденный путь, как пример: NWEW... . При обходе в ширину нет необходимости хранить уже пройденные состояния, их можно просто уничтожать. Т.е. нет необходимости хранить дерево целиком в памяти. Используется принцип FIFO. Помещаем вершину в очередь, забераем её оттуда, считаем следующие состояния, помещаем их в эту очередь, а саму вершину уничтожаем, в каждом состоянии запоминаем, что мы прошли через вершину, и т.д.

D>Кроме того нужно вести один глобальный std::set содержащий все посещенные состояния (чтобы не зациклиться).
Я хотел немного другого: в каждом состоянии хранит в vector<что-то> по чему я мог узнать были ли у меня шарики в такой расстановке уже или нет.
Но с глобальным set тоже интересно: Проходя, допустим по правой ветке 10 уровня в глубину и встретив состояние уже находящееся в set можно остановить дальнейший обход этой ветки и считать этот путь не верным, даже если это состояние сформировалось вообще в другой части дерева.

D>(С учетом того что нужно параллелить алгоритм, то нужно сделать lock striping этого множества).

С синхронизацией проблем нет. Есть проблемы с обходом дерева и немного с организацией классов для этой задачи.

От безисходности готов для доски 40*40 просто представить все положения шариков единичными битами, а пустые клетки 0. Собрать все это в int-ы и поместить в структуру, но размер структуры получится 200 б. Теряюсь, не знаю как лудше сделать

C>Мне нужны только положения шариков на доске, для того чтобы исключить движение шарика по одному пути. Например циключно по краю доски, можно придумать целый лабиринт, когда шарик будет двигаться по замкнутому контуру бесконечно.
C>И количество шагов сразу вряд ли будет предсказуемым.

я не отслеживаю положение одного шарика, я отслеживаю положение всех шариков. Если один шарик прошел круг, но при этом положение других изменилось, то это нормальная ситуация, это может быть частью решения.

Есть тип marbles_coord_t -- это пара char -- хранит координату.

Есть тип marbles_state_t -- это сути дела std::vector< marbles_coord_t >, в котором положения всех шариков.

И наконец волна -- состоит из:

std::map< marbles_state_t, const marbles_state_t * > some_map;
std::vector< const marbles_state_t * > some_vec[2];

Допустим начальное состояние это marbles_state_t S;
В some_map изначально кладем пару S->NULL. Второй компонент пары -- это указатель на предшествующее состояние, для начального состояния это 0.

some_vec[0] сперва содержит указатель на S (который лежит в some_map, а как известно добавления в some_map не инвалидируют ни итераторы, ни указатели на элементы some_map)
some_vec[1] сперва пусто.
В цикле проходятся все элементы some_vec[0].
Допустим там есть элемент X -- пытаемся сделать 4 возможных хода, получается 4 новых состояния. Проверяем есть ли такие состояния в some_map, если уже есть то игнорируем их. Если нет, то кладем в some_map пару новое состояние -> указатель на предыдущее состояние X. Кроме того кладем указатель на это новое состояние в some_vec[1]. Если новое состояние совпадает с целевым состоянием, то мы нашли решение.
Так продолжаем пока не пройдем все элементы some_vec[0], после этого очищаем some_vec[0] и делаем some_vec[0].swap(some_vec[1]).
И продолжаем пока либо не найдем решение, либо some_vec[0] не окажется пустым.

Конечно, на большой доске и сложных лабиринтах, это будет intractable, но такова жизнь..

Здравствуйте, dilmah, Вы писали:
D>И наконец волна -- состоит из:
Не встречал раньше такого термина, это что? Если не сложно в 2х словах или ссылку.


D> std::map< marbles_state_t, const marbles_state_t * > some_map;
D> std::vector< const marbles_state_t * > some_vec[2];
Здесь все понятно,но:

D>Допустим начальное состояние это marbles_state_t S;
D>В some_map изначально кладем пару S->NULL. Второй компонент пары -- это указатель на предшествующее состояние, для начального состояния это 0.

Т.е. some_map[S] = NULL, по записи выглядит именно так. Далее:

D>some_vec[0] сперва содержит указатель на S (который лежит в some_map,

Каким образом мы получим этот указатель? Вот при такой записи some_map[S] = NULL для S будет использован конструктор копирования, чтобы поместить его как ключ в map.

>а как известно добавления в some_map не инвалидируют ни итераторы, ни указатели на элементы some_map)

Яндекс говорит что так, я сейчас точно не помню, в каком случае итераторы становятся не действительными, буду благодарен если напомните.

D>>И наконец волна -- состоит из:
C>Не встречал раньше такого термина, это что? Если не сложно в 2х словах или ссылку.

выше писали, что это breadth-first search http://ru.wikipedia.org/wiki/Поиск_в_ширину
some_vec[0] и some_vec[1] можно рассматривать как 2 поколения такой движущейся волны.

C>Т.е. some_map[S] = NULL, по записи выглядит именно так. Далее:
D>>some_vec[0] сперва содержит указатель на S (который лежит в some_map,
C>Каким образом мы получим этот указатель? Вот при такой записи some_map[S] = NULL для S будет использован конструктор копирования, чтобы поместить его как ключ в map.

вставить пару в map можно не только some_map[S] = NULL, но и так:
std::map< marbles_state_t, const marbles_state_t * >::iterator it = some_map.insert(std::make_pair(S, NULL)).first;

после этого искомый указатель можно взять как &(it->first)

>>а как известно добавления в some_map не инвалидируют ни итераторы, ни указатели на элементы some_map)
C>Яндекс говорит что так, я сейчас точно не помню, в каком случае итераторы становятся не действительными, буду благодарен если напомните.

у контейнеров типа map или list итераторы на элемент становятся недействительными только когда непосредственно этот элемент удаляется. Добавлять и удалять другие элементы можно безопасно. Это контрастирует с vector, где можно добавить новый элемент и внезапно инвалидировать итераторы на все остальные элементы.

Здравствуйте, SullenMan, Вы писали:

SM>Кто-нибудь пробовал решить такую задачку
SM>Интересует не программный код ессесно, а сам метод (алгоритм) решения.

SM>Ну первое что приходит на ум — взять любой шарик, составить для него список всех возможных путей и последовательно их проверить. Как только шар попал в дырку, брать любой из оставшихся, опять составить список всех путей до его дырки исходя из текущего (а не первоначального) положения и проверять эти пути.

SM>Затем из первоначального состояния брать другой шарик и делать то же самое.
SM>Но как мне кажется это не совсем рацианальный метод решения.
SM>Господа, математики, может что подскажете.

Что-то из условия я не совсем понял, а дырку с отличным номером шарик может пересечь или её надо обходить?

А>Что-то из условия я не совсем понял, а дырку с отличным номером шарик может пересечь или её надо обходить?

да, нужно обходить. Если шарик попал не в свою лунку, то это проигрышное состояние.

Здравствуйте, SullenMan, Вы писали:

SM>Кто-нибудь пробовал решить такую задачку
SM>Интересует не программный код ессесно, а сам метод (алгоритм) решения.

SM>Ну первое что приходит на ум — взять любой шарик, составить для него список всех возможных путей и последовательно их проверить. Как только шар попал в дырку, брать любой из оставшихся, опять составить список всех путей до его дырки исходя из текущего (а не первоначального) положения и проверять эти пути.

SM>Затем из первоначального состояния брать другой шарик и делать то же самое.
SM>Но как мне кажется это не совсем рацианальный метод решения.
SM>Господа, математики, может что подскажете.



Знатоки математики/алгоритмов, я так понимаю эту задачу можно решить путём полного перебора возможных путей для всех шаров. Ибо кратчайший путь от шара к дырке не всегда ведёт к решению задачи. Или я не прав?