Метод Хичкока

Алгоритм определения оптимальности: во всех загруженных клетках получаем нулевой потенциал, для этого по строчкам и столбцам таблицы, ко всем расстояниям, поставленным в верхних правых углах загруженных клеток, прибавляем такие числа, которые в сумме с расстояниями дают 0. Т.е. расстояние каждой загруженной клетки должно быть равно обратному значению суммы потенциалов строки и столбца, в которой находится данная клетка.

) Определяя потенциалы для всех свободных клеток, находят для каждой свободной клетки сумму указанного в ней расстояния с ранее полученными по загруженным клеткам потенциалами строки и столбца

При решении задач на минимум оптимальный вариант получится в том случае, когда во всех загруженных клетках находится нулевой потенциал, а потенциалы не загруженных клеток являются положительными числами. Наиболее потенциальной клеткой является такая клетка, потенциал которой имеет наибольшее отрицательное значение.

Наибольшая потенциальная клетка получает загрузку, чтобы это сделать, необходимо перераспределить груз в таблице. Это выполняется следующим образом: количество загруженных клеток в предыдущем шаге должно равняться m+n-1, если количество загруженных клеток менее m+n-1, то недостающее число клеток получают путем загрузки соответствующего количества клеток нулями. Клетка, в которой поставлена загрузка равная 0, считается загруженной. Для наиболее потенциальной клетки строится контур. Строится контур так, чтобы все углы кроме одного располагались в загруженных клетках, а один единственный находился в свободной наиболее потенциальной клетке. При соблюдении этого правила для каждой свободной клетки можно построить только один единственный контур. Определяются положительные и отрицательные углы контура, считается, что первый положительный угол лежит в свободной клетке, для которой построен контур, отрицательные и положительные углы чередуются, и их количество должно быть равно.

Выявляется наименее загруженная клетка, занятая отрицательным углом в нашем контуре. Количество груза указанное в этой клетке отнимается из всех клеток с отрицательными углами и прибавляется во все клетки с положительными углами. В результате одна или несколько ранее загруженных клеток становятся свободными, а наиболее потенциальная клетка становится загруженной.

Таблица № 4