Блог пользователя 12iq

Оптимизации перебора / Brute-force
Автор 12iq, история, 8 лет назад, По-русски

Доброго времени суток. Прошу накидать материала(лекции, задачи, все что угодно) по трюкам, которые помогают ускорить полный перебор всех вариантов. Так же хочется узнать решение конкретно этой задачи: 1824. Ифрит-бомбардировки на тимусе.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Здесь уже просили материал, но там так его никто и не скинул.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Ну конкретно в этой задаче у меня такое:
- отсечение по ответу
- не идти в ветку перебора, если скинув бомбы на все оставшиеся города мы все равно не взорвем все
- не кидать бомбу на город, если это не взрывает какой-то новый город

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо! В предыдущих попытках не пользовался этим "не идти в ветку перебора, если скинув бомбы на все оставшиеся города мы все равно не взорвем все".

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я не понял второй пункт.

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если скинуть бомбы на все оставшиеся города, мы всегда все взорвем

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Грубо говоря, наш перебор имеет вид 

      go(i) {
 берем(i) -> go(i + 1)
 не берем(i) -> go(i + 1)
}

      Тогда под оставшимися городами подразумеваются города с i + 1 по n

      → Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

клик

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Там честную динамику считают, перебор нечто иное.

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      там происходит сведение полного перебора всех путей за n! к полному перебору за 2^n. Оптимизация перебора с небольшой меморизацией. Но по сути, это тот же перебор.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

клик

→ Ответить