Самый короткий путь для ввода текста ввода с клавиатуры

Question

Я получаю пользовательскую строку от пользователя. Теперь мне нужно разработать кратчайший маршрут для нажатия этой строки на клавиатуре, которая включает в себя 9 кнопок.

Примечание:

• Буквы решения должны быть расположены в алфавитном порядке т.е., B, C, D, E, ...
• Каждое число должно по крайней мере включать в себя одну клавиатуру символов

Решение, если входной текст = 'Привет'

1. A, B, C, D
2. е, е, ж
3. H, I, J, K
4. л, м, н
5. O, P, Q
6. R, S, T
7. U, V, W
8. х, у
9. г

Или

1. а, б, в, г
2. е, е, ж
3. H, I, J, K
4. л, м, н
5. о
6. р
7. д
8. г
9. s, T, U, V, W, X, у, г

с этой клавиатуры мне нужно нажать 3,2,4,4,5 для т ype 'hello'

Итак, если вы хотите набрать «привет» с помощью этой клавиатуры, вам нужно всего лишь нажимать кнопки 5 кнопок, так как это наименьшее количество клавиш.

Я думаю, что этот вопрос решается с помощью жадных алгоритмов или алгоритмов обратного отслеживания.

Answer 1

Каждая действительная клавиатура соответствует 26-битовому номеру с ровно девятью битами, установленными в 1. С учетом только 2042975 допустимых комбинаций, грубая сила должна быть первой попыткой, перед другими подходами, требующими большего мышления. Алгоритм будет похож на этот псевдокод:

int best_score = int.max 
list<int> keypads 
for int mask between 1 and 1<<26 
    if bit_count(mask) != 9 or mask ends in 1 continue 
    int lookup[26] 
    int p = 1 
    for int i between 0 and 26 
     lookup[i] = p 
     if mask's bit i is set to 1, p = 1 ; otherwise, p = p + 1 
    int total = 0 
    for each char ch in word 
     total = total + lookup[ch] 
    if total < best 
     keypads = new list {mask} 
     best = total 
    else if total == best 
     keypads.add(mask) 
print best, keypads 

Answer 2

Давайте обобщим алфавит на {1, ..., n}. Пусть k - количество ключей. Для 1 ≤ i < j ≤ k стоимость (= количество прессов) возможного ключа {i, ..., j} равна 1fi + 2f _{i + 1} + ... + (j - i + 1) f _j, где f _i - частота буквы i. Мы ищем недорогую точную крышку, состоящую из точно k ключей.

Эта проблема имеет следующую оптимальную подструктуру: исправить произвольное оптимальное решение и удалить ключ с {m + 1, ..., n} на нем. В результате получается оптимальное решение задачи с k - 1 клавишами и алфавитом {1, ..., m}; В противном случае мы могли бы улучшить первое оптимальное решение, переставив первые ключи k - 1.

Соответственно, мы можем применять динамическое программирование. Для каждого 0 ≤ i ≤ n и любого 0 ≤ j ≤ k вычислите оптимальное расположение для {1, ..., i} с помощью j-ключей. Стоимость такого расположения C _{I, J} удовлетворяет рекуррентные

С _{0, J} = 0 для всех J ≥ 0
C _{I, 0} = ∞ для всех г> 0
C _{I, J =} мин _{0 ≤ я '< я} (С _{я', J-1} + с _{я», J}),

где с _{a, b} - стоимость ключа {a, ..., b}. Можно восстановить саму компоновку из последовательности оптимальных аргументов i '.