Как отсортировать элементы на основании критерия совместимости?

Question

[antares4045]

Есть словарь (на самом деле js объект), в котором могут быть тысячи элементов. У каждого элемента есть набор не нормализованных "пожеланий" быть поближе к определённым узлам. что то вроде "я, id0, оцениваю желание быть поближе к элементу id1 в 10 баллов, к id9 в 123832 балла а к id5 в 8". Необходимо реорганизовать структуру в кольцо максимально учитывая пожелания близости (причём отмечу, что необходимо не просто подобрать соседей а именно учесть пожелание быть поближе: тоесть в данном примере id5 от id0 на противоположном конце кольца оказаться не должен).
Причём дополнительной сложностью является то, что задача (в идеале) должна решаться в браузере в рантайме, хотя при большой необходимости можно унести и на бэкенд.

Скорее всего, есть алгоритм, решающий задачи такого типа, но все мои попытки что-то нагуглить упираются в настойчивое желание гугла впарить мне qsort.

другими словами

{
    id0 : {
        weights: {
            id1: 10,
            id9: 123832,
            id5: 8
        }
    },
    id1: {
        weights: {
            id0 : 10
        }
    },
    id5: {
        weights: {
            id0 : 8
        }
    },
    id9 : {
        weights: {
            id0 : 123832
        }
    }
}

должно перобразовываться в любой из массивов

['id0', 'id9', 'id5', 'id1']
['id9', 'id5', 'id1', 'id0']
['id5', 'id1', 'id0', 'id9']
['id1', 'id0', 'id9', 'id5']

['id0', 'id1', 'id5', 'id9']
['id1', 'id5', 'id9', 'id0']
['id5', 'id9', 'id0', 'id1']
['id9', 'id0', 'id1', 'id5']

Comments

[Wataru]

Оценки всегда симметричные, как у вас в примере (weight(idX,idY) = weight(idY,idX))?

Как набор весов преобразуется в оценку конкретного расположения элементов? Как понять, что одно расположение лучше другого? Т.е. например, можно разместить id0 с id1 на расстоянии 4, а с id10 на расстоянии 10, а можно id1 на расстоянии 5, а id10 на расстоянии 8. Как понять, что лучше?

Например, можно умножать расстояние между интересующимеся друг другом id-шниками на веса, суммировать это все и минимиировать. Можно домножать на квадраты расстояний, можно веса возводить в степень расстояния, можно давать штраф, если расстояние больше заданного порога... Куча вариантов и все дадут разные решения.

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

У задачи есть какой-то физический смысл? Может ее возможно свести к чему-то более простому - дайте изначальную задачу.

[antares4045]

Wataru, это маленькая подзадача в пока сугубо теоретическом механизме планаризации графа.
Критерий оценки пока что пойдёт любой, в крайнем случае буду играться с механизмом наборов весов, но если получится вынести его в гиперпараметр -- вообще шикарно.

[antares4045]

Wataru, и да, оценки всегда симметричные

Answer 1

[Константин]

Можно использовать метод отжига или генетический алгоритм (про них можно почитать в википедии или поискать статью на Хабр). По сути оба алгоритма решают задачу максимизации/минимизации какой-либо функции.
Например можно ввести метрику того, насколько какое-то решение "хорошее". Пусть f(p) - сумма по всем парам id (обозначим их как i и j) значения weiht(i, j) / |i - j|, где weiht(i, j) - то, насколько i "хочет быть ближе" к j, а |i - j| - минимальное расстояние между i и j в кольце. Здесь p - перестановка id. Тогда решение задачи - p, при которой f(p) - максимально.
К сожалению, есть одна проблема: отжиг и/или генетический алгоритм могут не сработать, но есть вероятность что в этой задаче они помогут. Не попробуешь - не узнаешь)

Comments

[antares4045]

Ну ГА просто тучу вычислительных мощностей сожрёт, что для моей задачи не приемлимо. А вот насчёт отжига интересно: я действительно упустил что есть алгоритмы подбора и всё пытался родить алгоритм вычисления. Пока времени нет, но как появится -- посмотрю что там можно придумать.

[Константин]

Удачи