задачка

[109]

вот, кстати, задачка, с которой я в своё время столкнулся по поводу игрушки vga planets.

итак, имеем 11 разных рас и 11 игроков, желающих играть той или иной расой в той или иной степени (выраженной, скажем, в процентах). задача - найти такое распределение игроков по расам, чтобы суммарное "щастье" было максимально. точнее говоря, найти алгоритм, который будет это делать быстрее, чем простым перебором.

иными словами, имеется квадратная матрица NxN, удовлетворяющая условиям:
- все элементы матрицы принадлежат отрезку [0,1]
- сумма элементов каждой строки равна 1
- строки можно переставлять местами

требуется: найти алгоритм, вычисляющий максимальное значение суммы элементов главной диагонали и порядка строк, соответствующего этой сумме, имеющий наименьший порядок зависимости от N. N² вполне пойдёт.

Comments

[averros.livejournal.com]

Sorry for writing in English --

this problem is the same as finding maximal cost Hamiltonian cycle in an fully meshed oriented graph. (This is easy to see because ordering of rows in the matrix is the same as order of visiting the graph nodes, and element a[i,j] of the original matrix is the "cost" of going from node j to node i).

Because max and min cost problems are easily converted to each other, this is equivalent to Traveling Salesman Problem (TSP), which is NP-complete. I.e. an algorithm guaranteeing the optimal solution is not going to be better than O(2^N).

Because the graph is fully connected, the standard sparse-graph heuristic algorithms (http://web.cs.ualberta.ca/~joe/Theses/vandegriend.html) won't work very well. I would suggest using simulated annealing or genetic algorithms.