Задача построения оптимальной компьютерной сети предположительно является NP-полной, и для ее решения на данный момент требуются алгоритмы со сложностью, экспоненциально растущей с увеличением размерности задачи. В этом контексте жадный алгоритм с эвристическими методами, применяемый для построения дерева сети, может значительно сократить время вычислений без существенного ущерба для качества решения. К примеру, использование метода поиска наибольшего остовного дерева может уменьшить количество рассматриваемых вариантов и значительно ускорить работу алгоритма. Таким образом, применение эвристических методов может быть эффективным подходом к решению задачи построения оптимальной компьютерной сети.
Мартынов П.М. (науч. рук. Аксенов В.Е.) Исследование эвристических методов построения оптимальных компьютерных сетей // Сборник тезисов докладов конгресса молодых ученых. Электронное издание. – СПб: Университет ИТМО, [2023]. URL: https://kmu.itmo.ru/digests/article/11107