Все мы хоть раз писали СМС на мобильном телефоне и, наверное, заметили, что некоторые слова пишутся гораздо дольше других (той же длины, автоподстановка отключена). Например, чтобы написать слово "стриж", нужно нажать 6 (3 раза), подождать пару секунд, опять нажать 6 (2 раз), еще подожать, опять 6 (1 раз) и потом без задержек 4 и 3. А если бы С, Т, Р находились на разных цифрах, это слово мы написали бы не за десять секунд, а за две. На написание слова "баба" у нас уйдет порядка 8 секунд!
Сама задача
Представим теперь, что мы проектируем новый телефон и вольны раскидать 33 русских буквы по 8 клавишам так, как захотим. Наша задача - минимизировать время набора сообщения, приняв следующие расценки:
- Последовательное нажатие разных клавиш 0 секунд
- Нажатие одной и той же клавиши несколько раз для выбора нужного символа - 0.1 секунда за нажатие (таким образом, порядок "АБВГ" и "ГВБА" дают разные результаты)
- Ожидание клавиши, чтобы на ней можно было набрать следующий символ - 2 секунды
От нас требуется описать алгоритм, который бы за разумное время определил бы близкий к оптимальному порядок расположения букв. В качестве тестовой базы можно взять пару десятков современных газет и журналов - можно ожидать, что используемые слова часто встречаются и в СМС. В нашем распоряжении - вычислительные возможности персоналки - не так и мало, но полный перебор вариантов раскладки не осилит.
Итак, как будем решать? Ясное дело, пробежимся по тексту, составим список встречающихся слов (и число повторений), но что делать дальше?
Предисловие
Все мы хоть раз писали СМС на мобильном телефоне и, наверное, заметили, что некоторые слова пишутся гораздо дольше других (той же длины, автоподстановка отключена). Например, чтобы написать слово "стриж", нужно нажать 6 (3 раза), подождать пару секунд, опять нажать 6 (2 раз), еще подожать, опять 6 (1 раз) и потом без задержек 4 и 3. А если бы С, Т, Р находились на разных цифрах, это слово мы написали бы не за десять секунд, а за две. На написание слова "баба" у нас уйдет порядка 8 секунд!
Сама задача
Представим теперь, что мы проектируем новый телефон и вольны раскидать 33 русских буквы по 8 клавишам так, как захотим. Наша задача - минимизировать время набора сообщения, приняв следующие расценки:
- Последовательное нажатие разных клавиш 0 секунд
- Нажатие одной и той же клавиши несколько раз для выбора нужного символа - 0.1 секунда за нажатие (таким образом, порядок "АБВГ" и "ГВБА" дают разные результаты)
- Ожидание клавиши, чтобы на ней можно было набрать следующий символ - 2 секунды
От нас требуется описать алгоритм, который бы за разумное время определил бы близкий к оптимальному порядок расположения букв. В качестве тестовой базы можно взять пару десятков современных газет и журналов - можно ожидать, что используемые слова часто встречаются и в СМС. В нашем распоряжении - вычислительные возможности персоналки - не так и мало, но полный перебор вариантов раскладки не осилит.
Итак, как будем решать? Ясное дело, пробежимся по тексту, составим список встречающихся слов (и число повторений), но что делать дальше?