Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 14

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

Публикации

Показать лучшие за всё время

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr