Comments 14
Всеобщее молчание и в закладках уже у 20 человек — и добавить нечего, и полезно, и красиво. Спасибо!
+9
Отличная статья, спасибо.
+1
Кстати, может кому-то понадобится, я тоже недавно накидал имплементацию алгоритма x на C# с использованием пляшущих ссылок и эвристикой, которую предлагает Кнут в своей работе.
+1
Посмотрел на Ваш код, вы без эвристики столбцы выбираете. Кнут советует выбирать столбец с минимальным количеством единиц, чтобы минимизировать ветвления.
+1
При всём уважении, мне кажется, вы не очень внимательно его смотрели.
/* select column with mininimal number of elements */
Col *select_col(){
int min = cptr->length;
Col *col = cptr->right, *mc = cptr;
while(col != cptr){
if(col->length < min){
mc = col;
min = col->length;
}
col = col->right;
}
return mc;
}
+4
Танцующие ссылки — интересно. Алгоритм — банальный перебор с возвратом.
+4
Хороший алгоритм. Я попробовал реализовать его на битовых масках, а не на списках. Итог — 180 строк, 12 секунд (на i7, 2.9 GHz).
Код здесь.
Интересно, что будет, если фигуры разные. Это должна получиться матрица примерно 150*24000? (дополнительные 25 столбцов — на идентификаторы фигур). Боюсь, что работать будет уже не так быстро…
Код здесь.
Интересно, что будет, если фигуры разные. Это должна получиться матрица примерно 150*24000? (дополнительные 25 столбцов — на идентификаторы фигур). Боюсь, что работать будет уже не так быстро…
+1
Важно не только количество строк, но и как быстро они уходят (мы здесь считаем, что удалять строки проще, чем перебирать варианты). Если всего фигур n, то каждая итерация будет удалять ~1/n часть строк. В частности с двумерными пентаминошками задачи по заполнению фигуры разными доминошками считаются быстрее, чем одинаковыми. Матрица в первом случае больше, зато дерево решений не так ветвится.
0
Написал сборку параллелепипеда 4*5*7 из 28 пентакубиков (всех, кроме отрезка 5*1*1). Первые решения программа нашла мгновенно, но всё дерево перебирает не быстро (уже есть 20000 решений и счёт продолжается...) Так что дерево очень даже ветвится.
Интересный эффект — алгоритм сам выбирает, что делать на очередном шаге — попытаться заполнить какую-нибудь клетку возможными способами, или выбрать какую-нибудь фигуру и перебрать все возможные её расположения. Я его этому не учил…
Интересный эффект — алгоритм сам выбирает, что делать на очередном шаге — попытаться заполнить какую-нибудь клетку возможными способами, или выбрать какую-нибудь фигуру и перебрать все возможные её расположения. Я его этому не учил…
+1
Торт!
0
Чертовски интересно, особенно если фигуры будут неправильной формы и трёхмерные. Дух захватывает от перспектив быстрого решения подобных задач. Если есть ссылки на подобные решения был бы очень благодарен.
+1
Например, вот. Но там несколько менее совершенный алгоритм.
+2
Sign up to leave a comment.
Алгоритм Х или что общего между деревянной головоломкой и танцующим Линком?