Допустим у нас имеется "клавиатура" (без наклеек букв, но с конкретными позициями кнопок - 3 ряда, на которых расположено суммарно 33 кнопки). Ещё есть словарь - список корректных слов. Если задать раскладку, то у слова появляется характеристика, зависящая от раскладки. Самый простой пример - длина слова на клавиатуре (длина ломанной, которая получится в результате последовательного соединения букв слова)
Требуется придумать оптимальную раскладку (для которой средняя характеристика будет минимальной) для заданной характеристики и заданного словаря.

Самый простой и в то же время самый долгий способ - перебор.
Будут ещё какие-нибудь варианты?)

(0) от характеристики все зависит, например для "длина ломанной, которая получится в результате последовательного соединения букв слова" можно используя суффиксные деревья получить буквы которые должны быть рядом это уменьшит перебор

по каким критериям характеристику то считаем? чтобы были задействованы максимальное количество пальцев, либо 1 указательный палец максимально мало передвигать?

(1) Опять же.. Это перебор. Хотелось бы что-нибудь математическое)

(3) дык нету математического решения подобных задач т.к. есть несколько правильных ответов
возьми к примеру раскладку и отобрази ее зеркально по вертикали и(или) горизонтали что то изменится разве?

(2) "1 указательный палец максимально мало передвигать?"
Что-то вроде того.

Пример:
Характеристика - длина слова
Раскладка - стандартная русская клавиатура.

Характеристика(ЙК)=3=Характеристика(ЙЦУК)
Характеристика(ЙКУ)=4
Характеристика(ПРИВЕТ)~10
Всё указано в клавишах)

(4) Наверняка есть поиск одной из минимальных раскладок

задача из разряда шахмат, почитай про деревья комбинаций

(7) деревья комбинаций? Гугл выдаёт только то, что может пригодится слесарю)

(8) считаешь количество соседних букв, причем не зависимо от их порядка, сортируешь по убыванию, и из центральной точки 33 буквы заполнить будет не сложно

т.е. если взять за центральное поле букву "п", то тебе надо найти 8 комбинаций максимально встречающихся с одной буквой. после этого их нахождения удаляешь из выборки все комбинации с этой буквой.
пример:
а б в
г д е
ж з и
дб и дз должны быть комбинации на 7 и 8 местах по совмещению
далее у тебя будет на выбор по 1-3 из максимально встречающихся. т.е. у буквы а надо выбрать 2 варианта, у буквы г 3 варианта у буквы ж 2 варианта и их подставлять

естественно это получается грубая оценка и может быть провал в каком-нибудь слове. возможно вырожденные случаи необходимо рассмотреть отдельно.

а вообще напоминает поиск числа бога.. 10^50 степени