How to become an author
Search
Write a publication
Pull to refresh

Comments 14

Всеобщее молчание и в закладках уже у 20 человек — и добавить нечего, и полезно, и красиво. Спасибо!
Total votes 9: ↑9 and ↓0+9
Посмотрел на Ваш код, вы без эвристики столбцы выбираете. Кнут советует выбирать столбец с минимальным количеством единиц, чтобы минимизировать ветвления.
Total votes 1: ↑1 and ↓0+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;
}
Total votes 4: ↑4 and ↓0+4
Да, прошу прощения, не внимательно посмотрел routineX(), выего оттуда вынесли в select_col(), потому бегло посмотрев не увидел.
Total votes 1: ↑1 and ↓0+1
Танцующие ссылки — интересно. Алгоритм — банальный перебор с возвратом.
Total votes 4: ↑4 and ↓0+4
Хороший алгоритм. Я попробовал реализовать его на битовых масках, а не на списках. Итог — 180 строк, 12 секунд (на i7, 2.9 GHz).
Код здесь.
Интересно, что будет, если фигуры разные. Это должна получиться матрица примерно 150*24000? (дополнительные 25 столбцов — на идентификаторы фигур). Боюсь, что работать будет уже не так быстро…
Total votes 1: ↑1 and ↓0+1
Важно не только количество строк, но и как быстро они уходят (мы здесь считаем, что удалять строки проще, чем перебирать варианты). Если всего фигур n, то каждая итерация будет удалять ~1/n часть строк. В частности с двумерными пентаминошками задачи по заполнению фигуры разными доминошками считаются быстрее, чем одинаковыми. Матрица в первом случае больше, зато дерево решений не так ветвится.
This comment wasn’t rated yet0
Написал сборку параллелепипеда 4*5*7 из 28 пентакубиков (всех, кроме отрезка 5*1*1). Первые решения программа нашла мгновенно, но всё дерево перебирает не быстро (уже есть 20000 решений и счёт продолжается...) Так что дерево очень даже ветвится.
Интересный эффект — алгоритм сам выбирает, что делать на очередном шаге — попытаться заполнить какую-нибудь клетку возможными способами, или выбрать какую-нибудь фигуру и перебрать все возможные её расположения. Я его этому не учил…
Total votes 1: ↑1 and ↓0+1
Чертовски интересно, особенно если фигуры будут неправильной формы и трёхмерные. Дух захватывает от перспектив быстрого решения подобных задач. Если есть ссылки на подобные решения был бы очень благодарен.
Total votes 1: ↑1 and ↓0+1
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr