LINUX.ORG.RU

Помогите с поиском пути?

 


0

3

Помогите придумать кошерный алгоритм поиска пути?

Сначала уточнение, потом на примере, потом четкая форумлировка.

Уточнение.

Надо в первую очередь решить задачу, т.е. если есть уже готовые либы или языки программирования, которые искаропки решают задачу, и которые можно заюзать без особых накладных расходов из 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, то для него юзается гораздо более простой алгоритм.

===

Как-то так. Есть идеи?

★★★★☆

boost::graph?

upd. После прочтения «чёткой формулировки» оказалось, что не всё так просто.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)

Идей навалом, но ты ж вроде погроммист, должон как «Отче наш» докладывать про пути и двоичные деревья.

Deleted ()
Ответ на: комментарий от Deleted

Я могу в перебор, но на тупой перебор никаких ресурсов не хватит. Хотелось бы нечто более аналитическое, на основе ограничений и свойств операций.

На нечто большее я пока не способен, т.к. в моей быдлокодерской жизни подобная задача встретилась вообще в первый раз, предыдущий раз был еще в школе и неправда :)

Поэтому и прошу идей, готовых решений и литературы (конкретно по этой задаче).

stevejobs ★★★★☆ ()
Последнее исправление: stevejobs (всего исправлений: 1)

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

Deleted ()

Чем-то напоминает типовые задачки, которые мы решали в универе на Прологе, да :). Почитай первые главы Братко, может увидишь.

yoghurt ★★★★★ ()
Ответ на: комментарий от stevejobs

Вечером дам, когда будет доступ к тому компу.

vurdalak ★★★★★ ()
Ответ на: комментарий от tailgunner

Понимаешь, типовой SAT-солвер не имеет внутрях последовательности действий

Почти всегда примененем одного-единственного патча задача не решается

У меня по условию один и тот же патч можно применять бесконечное число раз

Поэтому я даже перебор не могу устроить - неизвестно же, есть вообще решение или нет.

А если тупо установить лимит в глубину (или какое-то другое количество переходов), то может оказаться решение, лежащее на поверхности с первого взгляда человеком, но до которого эвристика добирается за слишком большое количетсво переходов и поэтому не добирается вообще (останавливается на лимите)

stevejobs ★★★★☆ ()
Ответ на: комментарий от stevejobs

У меня по условию один и тот же патч можно применять бесконечное число раз

от в том и проблема. Можно канешн добавить к каждой вершине замкнутое на нее же ребро, и посмотреть, чо при этом выйдет из обычных алгоритмов...

arkhnchul ★★ ()
Ответ на: комментарий от Deleted

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

непонятно как целевой функционал задать.

dikiy ★★☆☆☆ ()

попробуй для начала со строгими ограничениями на патчи. А потом их ослабляй.

dikiy ★★☆☆☆ ()

ну а еще в качестве идеи - какой-нить эвристический алгоритм с функцией оценки текущего состояния.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

сейчас такая идея.

Тупо A*, который «поиск кратчашего пути на карте», ищем самый дешевый маршрут из соображения что стоимость пути до точки - это стоимость пути до предыдущей точки+стоимость текущего шага, определяющегося эвристикой.

Фиксируем какой-то набор «особо важных» переменных, 1-3 штуки, и считаем что чем быстрее операция приближает к ним, тем «короче путь» до нее. Т,е если цель - x>100, то путь x+500 намного дешевле, чем x+10. «Пространство поиска» уменьшится. Потом снова фиксируем 1-3 переменных, и так далее.

Идти можно и A->B, и B->A одновременно. В надежде что встретятся. Учитывать в эвристике, что чем ближе между собой противоположные пути, тем «дешевле» считать этот путь.

Плюс крутое анти-ограничение «автоподстраивающиеся значения». В конце дерева поиска (либо в «конце пути», либо при встрече двух сходящихся одновременно из А и Б путей) скорее всего получится так, что решений не существует. Тогда движок будет волен поменять (в некоторых пределах допуска) саму задачу, н-р если исходно требуется чтобы x>20, а у нас x=19, и это правило помечено как «неважное» (или не помечено как «важное») - то движок корректирует условие: x>20 => x>19.

Всё вместо это может оказаться намного дешевле тупого перебора в ширину

Но тут надо хорошую эвристику на «расстояние», которой я еще не знаю, если есть идеи - вэлкам

Например, вот x*2 будет «дешевле» x+500 только при достаточно больших X. Но как мы решим, что Х действительно достаточно большое - проведем реальные вычисления? Тогда на сам подсчет стоимости шага будут тратиться капец какие ресурсы

stevejobs ★★★★☆ ()
Последнее исправление: stevejobs (всего исправлений: 2)
Ответ на: комментарий от dikiy

Какие ограничения могут быть? У меня фантазия махонькая :)

(Ту же add_only даже задавать не надо - она выводится простым анализом запроса, не занимающим нисколько ресурсов, а сама задача может решиться из коробки (тем же A*) так что дешевле только рюкзак с кодами грея, так что эту оптимизацию при наличии хорошего основного алгоритма можно вообще не делать руками)

stevejobs ★★★★☆ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.