Задано N(<=500) параметров, каждый из которых может принимать значение от 1 до 26. Есть M(<=500) кнопок, нажатие на каждую из которых меняет значения исходных параметров (необязательно всех). Также задано некоторое начальное состояние параметров S0.
Требуется для некоторо набора состояний S[1..K](K<=100) определить, можно ли получить состояние Si из состояния S0 путем нажатия некоторой последовательности кнопок (кнопки могут нажиматься произвольно, каждая кнопка может быть использована неограниченное число раз).
Здравствуйте, Serge, Вы писали:
S>Всем привет. Такой этюд..
S>Задано N(<=500) параметров, каждый из которых может принимать значение от 1 до 26. Есть M(<=500) кнопок, нажатие на каждую из которых меняет значения исходных параметров (необязательно всех). Также задано некоторое начальное состояние параметров S0.
S>Требуется для некоторо набора состояний S[1..K](K<=100) определить, можно ли получить состояние Si из состояния S0 путем нажатия некоторой последовательности кнопок (кнопки могут нажиматься произвольно, каждая кнопка может быть использована неограниченное число раз).
S>Есть идеи?
Составь систему уравнений по модулю 26
Здравствуйте, kov_serg, Вы писали:
_>Составь систему уравнений по модулю 26
_>S0 + m[i]*K[i] = S1 %26
_>m[i] — собственно кол-во нажатий на кнопку K[i]
Возможно, система уравнений подойдет для случая, когда каждая кнопка инкрементирует значение параметра. В исходной задаче, каждая кнопка устанавливает значения параметров. Например, для 2 параметров: Кнопка 1: ('a', 'b'), Кнопка 2: ('x', '-'), где '-' означает, что значение параметра остается неизменным, после нажатия данной кнопки.
Здравствуйте, Serge, Вы писали:
S>Здравствуйте, kov_serg, Вы писали:
_>>Составь систему уравнений по модулю 26
_>>S0 + m[i]*K[i] = S1 %26
_>>m[i] — собственно кол-во нажатий на кнопку K[i]
S>Возможно, система уравнений подойдет для случая, когда каждая кнопка инкрементирует значение параметра. В исходной задаче, каждая кнопка устанавливает значения параметров. Например, для 2 параметров: Кнопка 1: ('a', 'b'), Кнопка 2: ('x', '-'), где '-' означает, что значение параметра остается неизменным, после нажатия данной кнопки.
Тогда всё хуже
S[0]=S0
...
S[i+1]=S[i]*M[i]+K[i]
...
S[n]=S_fin
Например
M[i]=(0,1,1,...) -- маска
K[i]=('-',0,0,...) -- результат нажатия
Здравствуйте, Serge, Вы писали:
S>Всем привет. Такой этюд..
S>Задано N(<=500) параметров, каждый из которых может принимать значение от 1 до 26. Есть M(<=500) кнопок, нажатие на каждую из которых меняет значения исходных параметров (необязательно всех). Также задано некоторое начальное состояние параметров S0.
S>Требуется для некоторо набора состояний S[1..K](K<=100) определить, можно ли получить состояние Si из состояния S0 путем нажатия некоторой последовательности кнопок (кнопки могут нажиматься произвольно, каждая кнопка может быть использована неограниченное число раз).
S>Есть идеи?
S>Спасибо.
А начальные состояние могут быть не достижимыми(неправильными)? Если нет, то все сводится к доказательству возможности состояния Si. Сопоставим каждому параметру набор кнопок, которыми он управляется. Если значение всех параметров с одинаковым набором кнопок равно значению какой либо кнопки из этого набора, то состояние является достижимым. Вроде так.
Здравствуйте, Qulac, Вы писали:
Q>А начальные состояние могут быть не достижимыми(неправильными)? Если нет, то все сводится к доказательству возможности состояния Si. Сопоставим каждому параметру набор кнопок, которыми он управляется. Если значение всех параметров с одинаковым набором кнопок равно значению какой либо кнопки из этого набора, то состояние является достижимым. Вроде так.
Начальное состояние может быть любым. Вот пример:
S0 = 'cc' — начальное состояние
Кнопки:
'a-'
'-b'
где '-' -- кнопка не меняет данный параметр.
Тогда для следующих состояние ответом будет
'ab' -- можно
'ac' -- можно
'cb' -- можно
'ba' -- нельзя
Здравствуйте, Serge, Вы писали:
S>Здравствуйте, Qulac, Вы писали:
Q>>А начальные состояние могут быть не достижимыми(неправильными)? Если нет, то все сводится к доказательству возможности состояния Si. Сопоставим каждому параметру набор кнопок, которыми он управляется. Если значение всех параметров с одинаковым набором кнопок равно значению какой либо кнопки из этого набора, то состояние является достижимым. Вроде так.
S>Начальное состояние может быть любым. Вот пример: S>S0 = 'cc' — начальное состояние S>Кнопки: S>'a-' S>'-b' S>где '-' -- кнопка не меняет данный параметр.
S>Тогда для следующих состояние ответом будет S>'ab' -- можно S>'ac' -- можно S>'cb' -- можно S>'ba' -- нельзя
Тогда так: Если значение всех параметров состояния si с одинаковым набором кнопок равно значению какой либо кнопки из этого набора или значению аналогичного параметра из состояния s0, то состояние si является достижимым.
Зафиксируем состояние Si, для которого требуется найти ответ. Тогда задача может быть сведена к следующей. Есть N лампочек и M кнопок. Известно начальное состояние лампочек (включена — 1, выключена — 0). Каждая из кнопок включает/выключает некоторое подмножество лампочек. Требуется определить, можно ли выключить все лампочки.
Данная задача отличается от классической тем, что нажатие кнопки не меняет состояние лампочки (т.е. 1->0, 0->1), а устанавливает состояние лампочки (например, в 0 [0->0, 1->0] или в 1 [0->1, 1->1]).
Возможно, кто-то знает, является ли данная задача NP или нет.
Казалось бы.
Имеем.
Состояния достижимые из исходного за один ход, за два. за три и т. д.
Естественную оценку расстояния до целевого состояния -- число отличающихся параметров.
Получаем целенаправленный эвристический поиск пути в графе, например А*
S>Спасибо.
Для "спасибо" тут есть кнопки
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Состояния достижимые из исходного за один ход, за два. за три и т. д.
Ага, всего 2^500 состояний.
E>Естественную оценку расстояния до целевого состояния -- число отличающихся параметров.
Шагов не много, вершин много.
E>Получаем целенаправленный эвристический поиск пути в графе, например А*
Ну да, и на выходе ответ: "не шмогла". А почему — непонятно, то ли пути нет, то ли не получилось найти.
Как-то не очень похожа задача на полную, должно быть что-то динамическое, вроде бы подпуть оптимального пути тоже оптимален.
