Помогите придумать кошерный алгоритм поиска пути?
Сначала уточнение, потом на примере, потом четкая форумлировка.
Уточнение.
Надо в первую очередь решить задачу, т.е. если есть уже готовые либы или языки программирования, которые искаропки решают задачу, и которые можно заюзать без особых накладных расходов из JavaVM или накрайняк C++ - было бы очень кстати. Литература по теме тоже бы пригодилась.
На примере.
Я пишу небольшой пакетный менеджер, который накатывает патчи. В данный момент система находится в состоянии A. Нужно узнать, возможно ли с помощью накатывания патчей (из готового набора) перевести ее в состояние B, и если да - то по какому именно пути.
Так как исходная задача сомнительная, то можно сказать так: какие ограничения следует наложить на устройство патчей, чтобы задача стала решимой, и решимой за как можно меньшее количество ресурсов.
Четкая формулировка.
Есть структура из следующих переменных START(x1...xn)
Есть набор патчей вида: Patch1(x1+10, x2-20), Patch2(x1*2, x2/2), Patch3(x1/x2, x3*x4). Т.е. каждый патч указывает, на сколько изменились исходные переменные, используя операции +,-,*,/.
Есть набор условий на конечное состояние: FINISH(x1=10, x2>=25), т.е. с помощью простых операций сравнения (=,!=,>,>=,<,<=) описывающих финальное состояние объекта.
Нужно определить, возможно ли из START получить состояние, удовлетоворяющее набору сравнений FINISH применением набора патчей. И какой будет этот набор - т.е. какие патчи, в какой последовательности. Один и тот же патч можно применять безграничное количество раз. В качестве ответа приоритет имеет самая короткая цепочка.
Так как исходная задача сомнительная, то можно сказать так: какие ограничения следует наложить на устройство патчей, чтобы задача стала решимой, и решимой за как можно меньшее количество ресурсов.
Например, здорово помогло бы поле-ограничение типа Patch1(ADD_ONLY,x1+1,x2+1) указывающее что данный патч может только увеличивать значения исходного сосотяния. Если весь набор доступных патчей состоит из ADD_ONLY, то для него юзается гораздо более простой алгоритм.
===
Как-то так. Есть идеи?
