Как определить последовательность действий?

Question

[Conder]

Допустим, есть некий сложный класс С, содержащий несколько полей (А1, А2, А3, и т.д), при чём эти поля не числовые, а нечто более комплексное (строки там, или енумы), то есть классическая алгебра к этим данным неприменима.
Есть конечный список действий, который мы можем выполнить над этим классом, например:

• Добавить строку "учи алгоритмы!" к полю А1
  
• Записать в поле А1 пустую строку и изменить значение поля А2 на "зеленый"
  
• Если поле А2 равно "синий" то поменять его на "красный", если нет - очистить поле А3
  
• И так далее
  

Далее, допустим у нас есть два объекта класса С (С1 и С2), и мы хотим построить такую последовательность действий, которая превратит С2 в С1

Вопрос: В какую сторону вообще копать? Каким образом решаются подобные задачи? В какой нотации записываются правила? Что хотя бы искать в гугле, есть у подобных задач общее название? Какую книгу почитать по теме?
Чувствую, что я что-то упустил в своём образовании.
Спасибо

Comments

[Сергей Соколов]

Конечный автомат, машина Тьюринга?

[hint000]

https://ru.wikipedia.org/wiki/Конечный_автомат

Answer 1

[Wataru]

Это называется поиск в пространстве состояний. Если бы вы могли построить граф - взять все возможные состояния поля A1 x все возможные состояния поля A2... и провести из каждого ребра, соответствующие всем возможным действиям, то это была бы тупо задача на поиск пути в графе.

Проблема в том, что состояний очень много. Поэтому граф не генерируется, а строится на лету. А дальше все-равно в этом графе запускается какой-то алгоритм поиска пути. Например A*. Или dfs со всякими эвристическими оптимизациями. Главное это накрутить достаточно оптимизаций, чтобы алгоритм не касался слишком большого количества состояний - потому что все просмотренные состояния надо хранить как-то в памяти.

Comments

[longclaps]

A* в разнородном пространстве, где тёплое и зелёное - это новость.

[Wataru]

longclaps, Какая разница, что за пространство. Главное, что в нем метрика есть - количество шагов. Осталось только эвристику подобрать. Это может быть не тривиально, но, например, если все действия меняют ровно одно поле в зависимости от каких-то условий, то может быть эвристика - сколько полей не совпало с конечным состоянием. Эта эвристика допустима - она не переоценивает никакой путь. Она еще и консистентна. Отлично подходит для A*.

[longclaps]

Wataru, это ретроспективно там есть количество шагов, а оценить, какая позиция ближе к цели -

• Добавить строку "учи алгоритмы!" к полю А1
• Записать в поле А1 пустую строку и изменить значение поля А2 на "зеленый"
  
• Если поле А2 равно "синий" то поменять его на "красный"
  

или исходная - не видится возможным. Так что сразу dfs.
Пример: целевая точка содержит компоненту - А2="синий", а реально кратчайший путь при условии А2= то зеленый, то красный попеременно.