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

ab-отсечения
Автор sdryapko, 13 лет назад, По-русски

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

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

13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
ИМХО Это даже не алгоритм, а просто здравый смысл, когда мы считаем что-то, делаем перебор. И если мы пришли в некоторое состояние, посчитав которое, даже в наилучшем случае мы не сможем улучшить свой текущий результат, то такое состояние просчитывать не нужно. Как-то так.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Это вы описали более общий вариант - метод ветвей и границ. AB-prune - это уже специализириванная версия для минимакса, т.е. обычно для алгоритмов игры с двумя игроками.
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Врядли здравый смысл описывается таким закрученными предложением :)
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Потому что русский язык не всегда хорошо подходит для описания здравого смысла. ;)
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
wikipedia

Только это скорее не полноценный алгоритм а методика ввода оптимизаций в перебор
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Википедия, однако!

Вообще т.к. алгоритм простой, он очень много где описывается, даже в старых книжках по программированию для детей я его встречал.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
лет 12 назад, в доинтернетовскую эпоху, мне пришлось ознакомиться с альфа-бетта отсечениями в книге
"Братко Иван. Алгоритмы искусственного интеллекта на языке PROLOG". Была такая толстенькая книжка, сейчас наверное есть в инете.
Про пролог не пугайся, там теория хорошо описана без пролога :)
Потом написал игру в Шашки, которая использовала альфа-бетта отсечения при переборе вариантов.
→ Ответить