Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа

• Опубліковано в: : Кибернетика и системный анализ
• Дата: 2012
• Автори: Шило, В.П., Шило, О.В., Рощин, В.А.
• Формат: Стаття
• Мова: Російська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
• Теми: Системный анализ
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/84128
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Метод глобального равновесного поиска решения задачи о максимальном взвешенном разрезе графа / В.П. Шило, О.В. Шило, В.А. Рощин // Кибернетика и системный анализ. — 2012. — Т. 48, № 4. — С. 101-105. — Бібліогр.: 14 назв. — рос.

Розроблено новий, оснований на використанні методу глобального рівноважного пошуку (ГРП) алгоритм розв’язання задачі про максимальний зважений розріз графу. Проведено його порівняльне дослідження з найкращими на даний час алгоритмами розв’язання цієї задачі. Показано переваги алгоритму ГРП як за швидкодією, так і за можливістю отримання кращих розв’язків. A new algorithm based on the global equilibrium search (GES) is developed to solve the weighted MAXCUT problem. A comparison study of the algorithm and currently the best algorithm for solving this problem was conducted. The advantages of the GES algorithm both in the performance and the possibility of finding the best solutions are shown.