Максимизируйте количество очков за круговое расположение чисел

Я ищу эффективный алгоритм для решения проблемы организации кругового набора чисел от 1 до 12, чтобы получить наивысший балл.

Оценка расположения определяется суммой оценок всех соседних пар.

Чтобы получить оценку соседней пары (a,b), вычисляются следующие шаги:

1. Find x such that (a+x) mod 12 = b
2. Look up x in a score table
3. The value in the score table at index 'x' is the score of the pair (a,b).

Это повторяется для каждой соседней пары, и сумма является оценкой расположения.

Here is an example:

Suppose the score table is [5,4,6,7,2,7,-2,-6,-8,-2,6,12,13]

Consider these numbers: 5, 12, 8, 9

For each adjacent pairs,
the values for x are:   5 -> 12: 7
                        12 -> 8: 8
                        8 -> 9:  1
                        9 -> 5:  8

The values for score[x] are:
                        score[7] = -6
                        score[8] = -8
                        score[1] = 4
                        score[8] = -6

The sum of the score[x] values is: (-6) + (-8) + (4) + (-6) 
                                   = -18

Цель состоит в том, чтобы придумать алгоритм для эффективного расположения чисел, чтобы максимизировать счет, учитывая сами числа — до двадцати из них между 1 и 12 — и таблицу очков.

Большое спасибо,


search algorithm tree permutation maximize
person Dr C    schedule 30.10.2014    source источник
comment
Проблема в том, что... Это очень похоже на задачу коммивояжера (TSP). И решить их оптимально не всегда быстро. Однако у вас нет набора большого размера, и это может быть фактором искупления.   -  person Kaganar    schedule 30.10.2014
comment
Я полагаю, я должен спросить. Вы ищете алгоритм, который находит максимальный балл или довольно хороший балл?   -  person Kaganar    schedule 30.10.2014
comment
Я бы предпочел максимальный балл. огромное спасибо.   -  person Dr C    schedule 30.10.2014
comment
В этом случае ищите точные решатели TSP, которые допускают асимметричные и произвольные веса. Это будет непросто реализовать, поэтому, если вы можете использовать уже существующую библиотеку, тем лучше. Там есть несколько.   -  person Kaganar    schedule 30.10.2014
comment
Здесь обсуждается TSP: stackoverflow.com/questions/7159259/optimized-tsp- алгоритмы   -  person Kaganar    schedule 30.10.2014
comment
У меня возникли проблемы с пониманием того, как моя проблема связана с проблемой TSP, не могли бы вы помочь мне понять.   -  person Dr C    schedule 30.10.2014

Ответы (1)


arrow_upward
0
arrow_downward

Вы можете решить эту проблему с помощью точного решателя TSP.

Представьте, что есть набор городов, каждый из которых имеет «значение». Мы скажем, что стоимость города x равна V(x). А теперь представьте, что проезд из города x в y стоит S(V(y) - v(X) (mod 12)). Обратите внимание, что S — это ваша таблица результатов, а V(y) - V(x) (mod 12) — это значение, которое нужно искать в таблице результатов.

Цель TSP — определить, в каком порядке вы должны посетить все города ровно один раз, чтобы оптимизировать свои расходы — в этом случае вы хотите максимизировать свои расходы. (В качестве альтернативы вы можете просто сделать свою оценочную функцию отрицательной и минимизировать свои затраты.)

То есть TSP даст вам перестановку набора городов, которые оптимизируют ваш счет. Поскольку ваши города на самом деле являются значениями, которые вам интересно переставить, это даст вам перестановку ваших значений, которая даст оптимальный результат.

Итак.. Найдите программу или библиотеку, которая позволяет вам указать, сколько стоит перелет из города x в город y, а затем запустите ее, и она даст вам оптимальную перестановку ваших городов - тогда вы можете заменить город ID со значением (V(id)), чтобы получить оптимальное решение, которое вы искали.

Вы также можете написать свой собственный решатель TSP — методы ветвей и границ выглядят популярными.

person Kaganar    schedule 30.10.2014
comment
так как оценка также зависит от оценки между первым и последним посещенным городом, мне нужно изменить алгоритм? - person Dr C; 31.10.2014
comment
Не должен - каноническое определение - найти цикл. Это означает, что последний город должен соединиться с первым городом. - person Kaganar; 31.10.2014