nshindarev / mas-carpooling

Проект "Carpooling" для платформы JADE. Пассажиры и водители пытаются преодолеть определённые маршруты с минимальными денежными затратами
MIT License
2 stars 0 forks source link

Автоматическая генерация районов #19

Closed nshindarev closed 7 years ago

nshindarev commented 7 years ago

Нелинейная функция зависимости районов и количества вершин в городе.

nbirillo commented 7 years ago

Алгоритм генерации (первая версия): Вычисляем по формуле (вики) количество районов в городе. Вычисляем примерное количество вершин в каждом районе (N) (общее количество вершин делим на количество районов). Алгоритм: Идем по множеству вершин. Для каждой вершины: Записываем в очередь все смежные с ней (и в множество этого района тоже добавляем и саму вершину тоже). Помечаем дуги, как включенные в район. Помечаем ее как пройденную. Смотрим, в искомом множестве вершин >= N? Если нет. То берем следующую вершину из очереди и проделываем с ней то же самое. Если да, то останавливаемся. Район готов (TODO: если получится замкнуть, будет круто)

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

Когда вершины закончатся - разделение по районам готово.