Построение оптимальных древовидных сетей
Автор: Злотов А.В.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 4 (48) т.12, 2020 года.
Бесплатный доступ
Рассматриваются точный и приближенный алгоритмы построения оптимальных сетей с разрывной функцией стоимости в зависимости от потока на ребрах. Установлены свойства оптимального решения задачи, описан алгоритм формирования всех деревьев и однокорневых поддеревьев графа, на базе которого построен алгоритм направленного перебора для поиска оптимального и приближенных решений задачи. Описаны алгоритмы получения приближенного решения и его корректировки.
Алгоритм генерации деревьев, построение оптимальных деревьев с разрывными функциями стоимости ребер
Короткий адрес: https://sciup.org/142229692
IDR: 142229692
Список литературы Построение оптимальных древовидных сетей
- Хачатуров В.Р., Соломатин А.Н., Злотов А.В. [и др.]. Планирование и проектирование освоения нефтегазодобывающих регионов и месторождений: Математические модели, методы, применение. Москва: УРСС, 2015.
- Берж К. Теория графов и ее применение. Москва: ИЛ, 1962.
- Ермольев Ю.М., Мельник Н.М. Экстремальные задачи на графах. Киев: Наукова думка, 1968.
- Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения Кибернетический сборник. Вып. 2. Москва: ИЛ, 1961. C. 95-107.
- Кельманс А.К. О построении кратчайшей связывающей сети // Кибернетика и управление. Москва: Наука, 1967. С. 115-130.
