Совет при решении задачи

@SVD102 · Регистрация: 12.10.2015

Студворк — интернет-сервис помощи студентам

Имеется следующая картинка. В каждом узле сетки дано некое значение(высота). В реальном мире это поверхность Земли c ямами и холмами(горками), и задача заключается в том что ее надо выровнять. Выровнять значит где-то засыпать ямы, а где то сровнять горы. Ни каких построек и водоемов нет. Земля с возвышенностей перераспределяется в ямы. Критерий оптимальности: как можно меньше земли пересыпать, ограничения: все можно ровнять и крайние точки тоже.
То есть на входе у меня будет некий массив со значениями в узлах, например такой как Z

@SVD102 · 12.05.2016, 13:34 **[ТС]**

Добавил картинки

@helter · 12.05.2016, 14:05

Это называется «транспортная задача». Для неё есть стандартные алгоритмы. К сожалению, литературы, кроме гугла, подсказать не могу.

echs · 12.05.2016, 16:10

Первое, что приходит в голову, вычислить среднюю
арифметическую высоту. И начать с того, чтобы
вычислить максимум (гору). Вот ее и надо ровнять...

@SVD102 1 / 1 / 1 Регистрация: 12.10.2015 Сообщений: 207
		1
	Совет при решении задачи 12.05.2016, 13:33. Показов 488. Ответов 3 Метки нет (Все метки) Имеется следующая картинка. В каждом узле сетки дано некое значение(высота). В реальном мире это поверхность Земли c ямами и холмами(горками), и задача заключается в том что ее надо выровнять. Выровнять значит где-то засыпать ямы, а где то сровнять горы. Ни каких построек и водоемов нет. Земля с возвышенностей перераспределяется в ямы. Критерий оптимальности: как можно меньше земли пересыпать, ограничения: все можно ровнять и крайние точки тоже. То есть на входе у меня будет некий массив со значениями в узлах, например такой как Z 0

@SVD102 1 / 1 / 1 Регистрация: 12.10.2015 Сообщений: 207
	12.05.2016, 13:34 [ТС]	2
	Добавил картинки Миниатюры 0

@helter 4520 / 3514 / 358 Регистрация: 12.03.2013 Сообщений: 6,037
	12.05.2016, 14:05	3
	Это называется «транспортная задача». Для неё есть стандартные алгоритмы. К сожалению, литературы, кроме гугла, подсказать не могу. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	12.05.2016, 16:10	4
	Первое, что приходит в голову, вычислить среднюю арифметическую высоту. И начать с того, чтобы вычислить максимум (гору). Вот ее и надо ровнять... 0

Опции темы