Описание проблемы: Назначьте несколько складов для определенных мест в сетке и найдите решение, которое минимизирует общую стоимость транспортировки. Известно: Стоимость перевозки за километр между двумя складами, карта в виде сетки, где каждый край имеет удельный вес (1 километр)
Пример : Найти места дляпять складов {A, B, C, D, E}, стоимость транспортировки за километр между двумя складами показана в следующей таблице, сетчатая карта показана на следующем рисунке, каждый край этого неориентированного графика имеет длину1 километр. Найдите решение, которое минимизирует общую стоимость транспортировки.
Неоптимальное решение, например: например: A->0, B->1, C->2, D->3, E->7, затемобщая стоимость = cost(A,B)+cost(A,D)+cost(A,E)+cost(B,C)+cost(B,E)+cost(C,D)+cost(C,E)+cost(D,E) = 10*1+30*3+35*4+40*1+60*3+80*1+90*2+70*1
Вопрос : Как спроектировать алгоритм полиномиального времени, чтобы найти оптимальное или приближенно оптимальное решение.
Большое спасибо!