Всем привет! Заинтересовался одной задачей, решения в интернете НЕТ. Поэтому, если вы знаете, как её решить - решите, только, пожалуйста, объясните, как вы это сделали. Если вы не знаете, как её решать - не решайте. Хочу увидеть чёткий, адекватный ответ. Спасибо! Вот сама задача (кстати, не уверен, что её вообще можно решить, поэтому не обольщайтесь). Тема: комбинаторика.
Задача достаточно короткая: Для вычислительной машины, способной просчитать миллион игровых комбинаций в секунду с отсевом заведомо неоптимальных ветвей, на просчёт 6 ходов вперёд потребуется 1 секунда, на 12 ходов — 11 дней, а на 18 ходов — около 32000 лет. Вопрос: сколько лет потребуется этой самой вычислительной машине на то, чтобы просчитать 70 ходов? (Задача очень даже правдоподобна, под "игровыми комбинациями" подразумеваются шахматные комбинации. Спасибо!
Аноним:
задача нереальная
Ответы
Ответ дал:
1
Это задача относится к так называемым классом
сложности или просто задача не решаемая за полинамиальное время , тем самым относится к категорий
классу , это значит что нет такого алгоритма так что он решал бы данную задачу при помощи скажем так рекурсивного метода , ИМЕННО метода ,потому что перебор идет " с отсевом заведомо неоптимальных ветвей" , это видно из-за времени , на просчитание ходов
Сама суть задачи , на примере шахматной игры , или вообще какой-та антагонистической игры , когда вы играете с компьютером , он использует так называемый принцип Альфа-бета отсечение , то есть к примеру вы сделали шаг , и Компьютеру нужно некое время к примеру как в данной задачи (это не имеет значение)
- секунда , вы делайте шаг , и теперь Компьютер оценивает ваш ход перебирая остальные , и сужая тем самым последующие ходы в зависимости как вы пойдете в следующий раз , то есть можно это изобразить в виде ГРАФА , на который поставлены приоритеты в зависимости как вы ходили , компьютер описывает все действия при помощи некой функций (но сам принцип , есть оценивание этих самым ветвей графа), которое интерпретируется в сам процессоров в виде битов , вопрос есть ли или существует алгоритм при помощи которой компьютер без проигрышна вас обыграет , то какой он
Явно выше сказанный алгоритм не без безпроигрышный , потому что он только использует оценивание , после ваших ходов то есть в любом случае оценивание , было бы хуже чем в начале игры итд
Так в чем суть , полинамиальных классов задач , это в том что , вы в зависимости от задачи , скажем так решаемой , описываете при помощи каких-то операций (алгоритма) и он должен вывести , что задача не решается , то есть зависимость
, то есть подставив ваши исходные данные в псевдоокоде , есть ли он такой алгоритм который бы решал , данную задачу за некоторое время , ответ
Сама суть задачи , на примере шахматной игры , или вообще какой-та антагонистической игры , когда вы играете с компьютером , он использует так называемый принцип Альфа-бета отсечение , то есть к примеру вы сделали шаг , и Компьютеру нужно некое время к примеру как в данной задачи (это не имеет значение)
Явно выше сказанный алгоритм не без безпроигрышный , потому что он только использует оценивание , после ваших ходов то есть в любом случае оценивание , было бы хуже чем в начале игры итд
Так в чем суть , полинамиальных классов задач , это в том что , вы в зависимости от задачи , скажем так решаемой , описываете при помощи каких-то операций (алгоритма) и он должен вывести , что задача не решается , то есть зависимость
Вас заинтересует
11 месяцев назад
11 месяцев назад
1 год назад
6 лет назад
6 лет назад
7 лет назад
7 лет назад