| |
|
|
| | Расчет численности избирателей на избирательных участках.
Имеется таблица со следующими полями:
Дом, Численность, СоседнийДом_1, СоседнийДом_2 и т.д. до СоседнийДом_8
Таблица содержит 100 тыс. записей (100 тысяч домов) с численностью от 1 (частный дом) до 1000 (многоквартирный дом) человек. Каждый дом имеет соседний (к примеру, берется дом в прямой видимости), соседних домов может быть от одного до восьми. Все соседние дома перечисляются в поле Дом, имеют количество жильцов и перечисление своих соседей.
Задача стоит следующая: Для формирования избирательных участков необходимо отобрать группу домов с общей численностью в 2500 человек. Количество в группе должно быть максимально приближенно к 2500 человек, но не менее 1000 и не более 2800. Группа домов не должна разрываться (избирательный участок не должен иметь разрывов).
Методика расчета следующая: Берётся дом №1 с количеством, к примеру, 500 человек, добавляется в группу, берётся следующий дом и из поля СоседнийДом_1, также добавляется в группу, затем из поля СоседнийДом_2 и т.д. Далее берутся в группу дома по необходимости, уже соседи соседей. В случае перебора или недобора по количеству, происходит возврат назад и исключение какого либо из соседних домов, но при условии, что исключённый дом может быть включён в другою группу (избирательный участок) т.е. он не останется изолированным внутри группы. Дома, которые попали в группу из категории СоседнийДом, в расчётах поля Дом в дальнейшем не учувствуют.
Как можно программно выполнить эту задачу? | |
| |
| |
| |
|
|
| | а зачем - результат все равно известен | |
| |
| |
| |
|
|
| |
Как можно программно выполнить эту задачу?
|
у этой задачи нет програмного решения (точнее есть но оно неверное)
предположим что на участке построено 8 домов из каждого из которых виден любой соседний дом.
вопрос - сколько "соседних" домов будет на участке
-----------
Алекс - почитай что-то по комбинатрике и по статистическим методам.
тебе это нужно... | |
| |
| |
|
|
| |
 17 Кб. |
|
| | >>> а вообще эту задачу видимостью и выборами решили давно
сколько "соседних" домов на этом графе (в постановке ТС) | |
| |
| |
| |
44 Кб. |
|
| | тьху, картинку перепутал...
вот ==>>> | |
| |
| |
| |
|
|
| | первый вариант явно лучше  | |
| |
| |
| |
|
|
| | если внесена табла соседей - то как вариант -
берем дом (первый) -
выбираем дом - Сосед № 1
- проверка всех соседей для Сосед № 1, если у них существую соседи (кроме выбранных) то данный сосед заносится в таблу и + колв-ов челов.
- выбираем сосед № 2 - и т.д. пока кол-во не дойдетдо макс.
для максимального приближения к желаемому значению 2500 - просто нужно пробежаться по всем соседям Соседей № 1 - N
но при каждом выборе - нужна куча проверок и препроверок | |
| |
| |
| |
|
|
| | пытался я решить подобную задачу - мозгов не хватило
а задачка детская - на шахматной доске передвигая коня побывать во всех клеточках по одному разу
на бумаге подобная задача решается влет (причем именно тем способом который вы сейчас пытаетесь применить), а вот заставить машину думать - не получилось
более того есть подводный камень - если машина пойдет считать дома не в пределах одного нужного района, а допустим по окраине города | |
| |
| |
| |
|
|
| | Видел подобную разработку на Делфи. Считала правильно, но все участки были или змейкой через весь город или почти строго по прямой. Вот думал сделать что-то подобное, но то которое с районированием дружила. Добавить типа что-то приоритета на прирост. | |
| |
| |
|
|
| |
114 Кб. |
|
| | >>> в таком случае нужно дабоваить деление на районы, кварталы
это называется эвристические методы анализа графа
http://www.codingrus.ru/print.php?type=A&item_id=2069
==>> | |
| |
| |
| |
|
|
| |
это называется эвристические методы анализа графа
|
ну графиню эвристически - пожалуй лучше анал (в)и зировать | |
| |
| |
| |
|
|
| | >>> пожалуй лучше анал (в)и зировать
не лучше а быстрее.
эвристические алгоритмы дают только приблизительное решение,
зато быстрее чем полный перебор | |
| |
| |
