Махов А.М. (С.- Петербург)
О НЕКОТОРЫХ АЛГОРИТМАХ ТЕОРИИ ГРАФОВ
Среди алгоритмов теории графов с точки зрения наибольшей универсальности в первую очередь заслуживают внимания задача о кратчайшей цепи, задача о минимальном гамильтоновом цикле (задача коммивояжера) и метод сетевого планирования и управления комплексом работ. Задача о кратчайшей цепи, кроме очевидных применений, связанных с поиском в ограниченном наборе вариантов либо самого дешевого, либо самого быстрого способа передачи чего-либо между пунктами в пространстве, имеет так же приложения к планированию и управлению во времени, среди которых широко известны два: так называемая задача о замене оборудования и метод сетевого планирования и управления комплексом работ. Различные алгоритмы решения этих задач разрабатывались с конца 50-ых годов, среди алгоритмов решения задачи о кратчайшем пути можно выделить две группы: 1) использующие условие неотрицательности элементов матрицы обобщенной стоимости задачи и 2) работающие для любой матрицы стоимости в случае выполнения для неё условия существования решения. Необходимо отметить, что при разработке этих алгоритмов случай наличия в графе дуг отрицательной стоимости особо не разбирался, хотя он и может встречаться на практике, например в задаче о замене оборудования в случае гиперинфляции или дефляции. Так как подобных процессов в экономике США (где и проведено большинство посвященных этому вопросу работ) во время разработки вышеупомянутых алгоритмов не наблюдалось, то и практическое применение их в этих ситуациях не анализировалось. Однако недавнее прошлое России и других постсоциалистических государств продемонстрировало возможность существования ситуаций гиперинфляции или дефляции в экономике на протяжении длительного временного промежутка. С другой стороны, в последних исследованиях в структурном анализе управляемости систем используются графы с отрицательными стоимостями дуг.
Наиболее эффективный из алгоритмов решения - алгоритм расстановки пометок в варианте- не применим к случаю графа с дугами отрицательной стоимости. Все допускающие отрицательные дуги варианты алгоритма просто принудительно расширяют базу вершин, используемую при вычислении пометки очередной итерации, до всех вершин графа, что, вообще говоря, максимизирует (а не минимизирует!) объем вычислений. Однако при модификации матрицы стоимости, при которой все цепи из начальной вершины в конечную увеличиваются на одинаковую величину, можно добиться сопоставления исходному графу новой матрицы с неотрицательными элементами, к которой применим вышеупомянутый эффективный алгоритм Дейкстры.