Перебор

  1. Мир есть перебор.
    1. DP = перебор + запомниание (меморизация)
    2. Жадность и перебор. Любую жадность можно улучшить до перебора.
    3. Ленивость перебора. Перебираем только то, что уже необходимо знать.
  2. Отсечения в переборе
    1. Отсечение по времени
    2. Отсечение по ответу: CurrentValue + F(State) >= Answer
    3. Перебор ребер в "правильном" порядке
      1. Sort по F(State)
      2. Эвристика хода конем
    4. Iterative Deepening (dfs = bfs)
  3. Техника перебора
    1. Перебираем только k первых ходов в отсортированном порядке.
    2. Iterative Increasing of k. Вещественные k.
    3. Запускаем перебор несолько раз (см. картинку)
    4. (Iterative Deepening + перебор первых k лучших) меняем на bfs (см. картинку)
    5. Iterative Increasing по размеру очереди.

Практика

  1. Захэшируем, дубль #1 110304a1 : 1A
  2. Захэшируем, дубль #2 110304a1 : 1B
  3. Отсечение по ответу 110304a1 : 1C
  4. Зверский перебор, дубль #1 110304a1 : 1D
  5. Зверский перебор, дубль #2 110304a1 : 1E
  6. Перебор ленивый, обыкновенный 110304a1 : 1F