|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kovalev 2:5020/400 03 Apr 2002 17:07:18
To : Vladimir Veretnov
Subject : Re: Оптимизация алгоритма игры "Быки и коровы"
--------------------------------------------------------------------------------
[]
> Именно так все и сделано.
> Вопрос глубже: как нужно отсортировать массив всех возможных вариантов (в
> идеале делать это на каждом шагу), чтобы при известном первом ходе
> обеспечить максимальную вероятность угадывания любого числа менее, чем за
7
> ходов. Повторюсь, что сейчас 358 чисел из 5040 отгадываются за 7 ходов,
как
> сделать меньше ?
Hу, тут есть очевидный путь усиления алгоритма.
Резерв, как мне думается, заключается в том, что мы нахождение
экстремума на многих шагах ейчас заменяем нахождением
оптимальных ходов на каждом
отдельном шаге. Такие "пошагово оптимальные" решения совсем не обязательно
приводят к глобально оптимальной стратегии.
Другими словами, можно попробовать "заглядывать"
не на один ход вперед и анализировать наихудший вариант,
а сразу на два (или больше, если хватит электричества в твоем компутере ;)
и смотреть сразу пару (или больше ответов).
Как я помню, у меня были большие проблемы
с производительностью компутера (20 лет назад) и я делал смешанную
стратегию,
т.е. пока оставалось много претендентов, я делал пошаговую оптимизацию,
а когда допустимых чисел оставалось немного, делал многошаговую оптимизацию.
В пределе, если сразу делать оптимизацию на много шагов вперед, получишь
_оптимальную_ стратегию (по критерию минимизации максимального числа
попыток).
Правда, есть опасность, что _среднее_ число попыток может быть
при этом и не оптимально.
SK
--- ifmail v.2.15dev5
* Origin: HOME (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
