Сегментация карты - Википедия - Map segmentation

В математика, то сегментация карты проблема - это своего рода проблема оптимизации. Он включает в себя определенный географический регион, который необходимо разделить на более мелкие субрегионы для достижения определенной цели. Типичные цели оптимизации включают:[1]

  • Минимизация загруженности автопарка, закрепленного за субрегионами;
  • Балансировка потребления ресурса, как в ярмарка разрезания торта.
  • Определение оптимального расположения складов снабжения;
  • Максимальное покрытие наблюдения.

Справедливое разделение земли было важной проблемой с древних времен, например в древняя Греция.[2]

Обозначение

Есть географический регион, обозначенный буквой C («торт»).

Разбиение C, обозначаемое X, представляет собой список непересекающихся подобластей, объединение которых равно C:

Существует определенный набор дополнительных параметров (например, препятствия, неподвижные точки или функции плотности вероятности), обозначаемых P.

На множестве всех разбиений существует вещественная функция, обозначенная G («цель»).

Задача сегментации карты состоит в том, чтобы найти:

где минимизация выполняется на множестве всех разбиений C.

Часто существуют ограничения геометрической формы перегородок, например, может потребоваться, чтобы каждая часть была выпуклый набор или подключенный набор или по крайней мере измеримый набор.

Примеры

1. Красно-синее разделение: есть набор синих точек и набор красных точек. Разделите самолет на такие регионы, что каждый регион содержит примерно долю синих точек и красных точек. Здесь:

  • Торт C это весь самолет ;
  • Параметры п два набора точек;
  • Целевая функция грамм является
Он равен 0, если в каждом регионе есть ровно дробь. точек каждого цвета.

Связанные проблемы

Рекомендации

  1. ^ Рагхувир Девулапалли (советник: Джон Гуннар Карлссон) (2014). Алгоритмы геометрического разделения для справедливого разделения географических ресурсов. Доктор философии Диссертация подана на факультет Миннесотского университета. ProQuest  1614472017.
  2. ^ Бойд, Томас Д .; Джеймсон, Майкл Х. (1981). «Разделение городских и сельских земель в Древней Греции». Hesperia. 50 (4): 327. Дои:10.2307/147876. JSTOR  147876.