Порекомендуйте, в каком направлении двигаться для решения следующей задачи:
Имеется множество целых чисел от 0 до 63. Имеется N<1000 пар, состоящих из двух чисел из исходного множества. Пара AB равна паре BA, пары могут повторяться, пара может состоять из двух одинаковых чисел. Необходимо распределить те числа из исходного множества, которые присутствуют в парах, на 4 группы не более 16 чисел в группе таким образом, что бы числа из каждой конкретной пары оказались в одной группе. Это не всегда возможно, поэтому приоритет у тех пар, которых чаще повторяются. Для пар AB, CD, EF, GH, AG,... числа из пар AB, GH и AG должны в идеале оказаться в одной группе. Если общее количество чисел, из которых состоят пары, меньше 64, то в группы можно добавлять числа, доводя количество чисел в группе до 16. Т.е. если пару AB не получается разместить в группу, в которой уже есть число A, то если в группе, содержащей число B, есть свободное место, то в нее можно добавить число A. Или можно поместить числа A и B вообще в третью группу. Задача алгоритма сделать так, что бы у максимального количество пар числа из пары входили в одну группу.
Здравствуйте, Aniskin, Вы писали:
A>Порекомендуйте, в каком направлении двигаться для решения следующей задачи:
A>Имеется множество целых чисел от 0 до 63. Имеется N<1000 пар, состоящих из двух чисел из исходного множества. Пара AB равна паре BA, пары могут повторяться, пара может состоять из двух одинаковых чисел. Необходимо распределить те числа из исходного множества, которые присутствуют в парах, на 4 группы не более 16 чисел в группе таким образом, что бы числа из каждой конкретной пары оказались в одной группе. Это не всегда возможно, поэтому приоритет у тех пар, которых чаще повторяются. Для пар AB, CD, EF, GH, AG,... числа из пар AB, GH и AG должны в идеале оказаться в одной группе. Если общее количество чисел, из которых состоят пары, меньше 64, то в группы можно добавлять числа, доводя количество чисел в группе до 16. Т.е. если пару AB не получается разместить в группу, в которой уже есть число A, то если в группе, содержащей число B, есть свободное место, то в нее можно добавить число A. Или можно поместить числа A и B вообще в третью группу. Задача алгоритма сделать так, что бы у максимального количество пар числа из пары входили в одну группу.
Ну, выглядит как задача кластеризации. Метрикой расстояния между числами возьмём сопротивление электроцепи между ними, считая, что каждая пара — это соединение проводником с единичным сопротивлением.
Рассчитать сопротивления можно примерно так:
0. Сопротивление между парами чисел X и Y равно 1/(количество пар (X,Y) + количество пар (Y, X)) в исходном множестве.
1. Если между X и Y нет соединения, то сопротивление между ними равно 1/(сумма (1/сопротивление маршрута I)), где "маршрут I" — это путь из X в Y через I, предполагая, что маршруты из X в I и из I в Y уже построены. Для него сопротивление — это просто сумма сопротивлений XI и IY.
То есть, вроде бы, можно просто возвести матрицу смежности в степень 6, и получить попарную метрику расстояния.
А потом натравливаем на это какой-нибудь алгоритм кластеризации.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>1. Если между X и Y нет соединения, то сопротивление между ними равно 1/(сумма (1/сопротивление маршрута I)), где "маршрут I" — это путь из X в Y через I, предполагая, что маршруты из X в I и из I в Y уже построены. Для него сопротивление — это просто сумма сопротивлений XI и IY.
Может быть ситуация, когда между X и Y нет пути в принципе. Т.е. сопротивление бесконечно. Мне кажется, что проще использовать прямые значения, а не 1/N, это позволит использовать ноль для бесконечного сопротивления.
S>То есть, вроде бы, можно просто возвести матрицу смежности в степень 6, и получить попарную метрику расстояния.
А какой физический смысл именно в шестой степени? Почему не пять или семь?
Здравствуйте, Aniskin, Вы писали: A>Может быть ситуация, когда между X и Y нет пути в принципе. Т.е. сопротивление бесконечно. Мне кажется, что проще использовать прямые значения, а не 1/N, это позволит использовать ноль для бесконечного сопротивления.
Да, можно так. Важно скорректировать алгоритм кластеризации так, чтобы он правильно сравнивал расстояния.
Например, когда в алгоритме написано "взять все точки, ближе чем некоторый R", то мы должны фильтровать те точки, у которых "близость" больше, чем R. Чтобы точки с нулевым расстоянием не попали.
S>>То есть, вроде бы, можно просто возвести матрицу смежности в степень 6, и получить попарную метрику расстояния. A>А какой физический смысл именно в шестой степени? Почему не пять или семь?
Это я накосячил. Надо не в шестую степень, а шесть раз возвести в квадрат, т.е. получить степень 64 = 2^6.
Предположим, у нас есть маршрут 1->2->3->4->5.....->63->64, заданный матрицей смежности M.
Возведя M в квадрат, мы получим матрицу с маршрутами 1->2, 1->3 (из 1->2->3), 2->3, 2->4 (из 2->3->4), и т.п. То есть она покрывает маршруты с длинами 1 и 2.
Возведя M^2 в квадрат, мы получим матрицу с маршрутами 1->2, 1->3 , 1->4 (из 1->2->4 и 1->3->4), 1->5 (из 1->3->5) и т.п. То есть теперь мы покрыли маршруты с длинами 1, 2, 3, и 4.
Видно, как максимальная длина найденного маршрута удваивается при каждом возведении в квадрат. Итого после шести умножений, мы построим матрицу, в которой будут ненулевыми все ячейки, включая ячейку (1, 64).
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Важно скорректировать алгоритм кластеризации так, чтобы он правильно сравнивал расстояния. S>Например, когда в алгоритме написано "взять все точки, ближе чем некоторый R", то мы должны фильтровать те точки, у которых "близость" больше, чем R.
Единственный алгоритм кластеризации, с которым я хорошо знаком, это метод k-средних. Этот метод требует вычисления центра кластера. А что мне взять в качестве центра кластера в моем случае?
Здравствуйте, Aniskin, Вы писали: A>Единственный алгоритм кластеризации, с которым я хорошо знаком, это метод k-средних. Этот метод требует вычисления центра кластера. А что мне взять в качестве центра кластера в моем случае?
Похоже, надо было с самого начала погуглить по "алгоритмы кластеризации на графах".
Вот, например: https://habr.com/ru/company/dca/blog/265077/
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
