Алгоритм преобразования одного графа в другой с минимальной ценой

Рассматриваются ориентированные графы, состоящие из любого числа дизъюнктных цепей и циклов, ребрам графов приписаны без повторений их имена — натуральные числа. Фиксирован список операций, каждая из которых по-своему преобразует один граф в другой, ей приписано число — цена данной операции. Нужно найти минимальную по суммарной цене последовательность операций, которая для двух данных графов преобразует один в другой. Эта задача самым широким образом применяется в прикладных вопросах. По-видимому, она является NP-трудной и поэтому может быть эффективно решена только при том или ином условии на цены или при некотором ограничении на графы. Ее решение при достаточно широких условиях получено в виде линейных по времени и памяти алгоритмов, для которых доказана точность (неэвристичность), т. е. доказано, что они всегда находят минимальную по цене последовательность операций. Задача давно решается многими эвристическими алгоритмами, которые тестировались на разных данных, но предлагаемые авторами решения — первые среди точных.