![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109вот, кстати, задачка, с которой я в своё время столкнулся по поводу игрушки vga planets.
итак, имеем 11 разных рас и 11 игроков, желающих играть той или иной расой в той или иной степени (выраженной, скажем, в процентах). задача - найти такое распределение игроков по расам, чтобы суммарное "щастье" было максимально. точнее говоря, найти алгоритм, который будет это делать быстрее, чем простым перебором.
иными словами, имеется квадратная матрица NxN, удовлетворяющая условиям:
- все элементы матрицы принадлежат отрезку [0,1]
- сумма элементов каждой строки равна 1
- строки можно переставлять местами
требуется: найти алгоритм, вычисляющий максимальное значение суммы элементов главной диагонали и порядка строк, соответствующего этой сумме, имеющий наименьший порядок зависимости от N. N2 вполне пойдёт.
итак, имеем 11 разных рас и 11 игроков, желающих играть той или иной расой в той или иной степени (выраженной, скажем, в процентах). задача - найти такое распределение игроков по расам, чтобы суммарное "щастье" было максимально. точнее говоря, найти алгоритм, который будет это делать быстрее, чем простым перебором.
иными словами, имеется квадратная матрица NxN, удовлетворяющая условиям:
- все элементы матрицы принадлежат отрезку [0,1]
- сумма элементов каждой строки равна 1
- строки можно переставлять местами
требуется: найти алгоритм, вычисляющий максимальное значение суммы элементов главной диагонали и порядка строк, соответствующего этой сумме, имеющий наименьший порядок зависимости от N. N2 вполне пойдёт.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
пÑоÑÑое непÑавилÑное ÑеÑенÐ
Date: 2002-11-29 12:26 pm (UTC)Ñ ÑеÑил, ÑÑо
1. лÑбÑÑ N-аÑнÑÑ Ð¿ÐµÑеÑÑÐ°Ð½Ð¾Ð²ÐºÑ Ð¼Ð¾Ð¶Ð½Ð¾ ÑазложиÑÑ Ð½Ð° ÑовокÑпноÑÑÑ Ð±Ð¸Ð½Ð°ÑнÑÑ .
2. еÑли N-аÑÐ½Ð°Ñ Ð¿ÐµÑеÑÑановка ÑвлÑеÑÑÑ "ÑлÑÑÑаÑÑей", Ñо Ñ Ð¾ÑÑ Ð±Ñ Ð¾Ð´Ð½Ð° из ÑоÑÑавлÑÑÑÐ¸Ñ ÐµÑ Ð±Ð¸Ð½Ð°ÑнÑÑ Ð¿ÐµÑеÑÑановок Ñакже должна ÑвлÑеÑÑÑ "ÑлÑÑÑаÑÑей".
3. еÑли ни одной "ÑлÑÑÑаÑÑей" бинаÑной пеÑеÑÑановки не оÑÑалоÑÑ, Ñо Ð¼Ñ Ð´Ð¾ÑÑигли абÑолÑÑного макÑимÑма.
Ñаким обÑазом, мой алгоÑиÑм пеÑебиÑал вÑе возможнÑе бинаÑнÑе пеÑеÑÑановки, а еÑли Ð½Ð°Ñ Ð¾Ð´Ð¸Ð» "ÑлÑÑÑаÑÑÑÑ", Ñо пÑоизводил еÑ, и наÑинал пеÑÐµÐ±Ð¾Ñ ÑнаÑала. Ñакой алгоÑиÑм лÑÑÑе пÑоÑÑого пеÑебоÑа, поÑколÑÐºÑ Ð¿ÑоÑÑой пеÑÐµÐ±Ð¾Ñ Ð¿ÑопоÑÑионален N!, а даннÑй алгоÑиÑм - N3.
но как оказалоÑÑ, ÑепоÑка ÑаÑÑÑждений 1-3, неÑмоÑÑÑ Ð½Ð° кажÑÑÑÑÑÑ Ð¾ÑевидноÑÑÑ, невеÑна. в ÑÑм ÑÑÑ ÐºÐ¸Ð´Ð°Ð»Ð¾Ð²Ð¾, говоÑиÑÑ Ð¿Ð¾ÐºÐ° не бÑдÑ, надеÑÑÑ Ð½Ð° гениалÑноÑÑÑ ÑиÑаÑелей :-)
Ркак наÑÑÐµÑ ÑÑÐ¼Ð¼Ñ ÑлеменÑов
Date: 2002-11-29 07:08 pm (UTC)Re: Ркак наÑÑÐµÑ ÑÑÐ¼Ð¼Ñ ÑлеменÑо
Date: 2002-11-30 07:20 am (UTC)ÐÐ.
Date: 2002-11-30 08:13 am (UTC)ÐодÑÑиÑÑваеÑÑÑ ÑÑмма каждого ÑÑолбÑа.
ÐаÑÐ¸Ð½Ð°Ñ Ñо ÑÑолбÑа Ñ Ð¼Ð°ÐºÑималÑной ÑÑммой - ÑÑавниваем вÑе ÑлеменÑÑ ÑÑого ÑÑолбÑа Ñ ÑлеменÑом на главное диагонали - еÑли болÑÑе, менÑем ÑÑÑоки меÑÑами. ÐÑи ÑÑолбÑÐ°Ñ Ñ ÑавнÑми ÑÑммами пÑидеÑживаемÑÑ ÐºÐ°ÐºÐ¾Ð³Ð¾-либо поÑÑдка - Ñлева напÑаво или наобоÑоÑ.
Re: ÐÐ.
Date: 2002-12-01 10:11 pm (UTC)РдалÑÑе
Date: 2002-12-02 06:52 am (UTC)Re: РдалÑÑе
Date: 2002-12-02 06:58 am (UTC)Ð¥ÑаниÑÑ Ð½Ðµ ÑолÑко макÑималÑ
Date: 2002-12-02 02:10 pm (UTC)Re: Ð¥ÑаниÑÑ Ð½Ðµ ÑолÑко макÑимал
Date: 2002-12-03 06:00 am (UTC)Re: пÑоÑÑое непÑавилÑное ÑеÑеÐ
Date: 2002-12-03 07:25 am (UTC)РеÑе еÑÑÑ Ð¿Ð¾Ð´Ð¾Ð·Ñение, ÑÑо задаÑа ÑквиваленÑна знамениÑой задаÑе о ÑÑкзаке, коÑоÑÐ°Ñ NP-полна, поÑÑÐ¾Ð¼Ñ ÐµÑÑÑ ÑанÑ, ÑÑо еÑли Ð²Ñ ÐµÐµ ÑеÑиÑе, Ñо докажеÑе, ÑÑо P=NP :)
Re: пÑоÑÑое непÑавилÑное ÑеÑеÐ
Date: 2002-12-03 07:30 am (UTC)и каков же пÑавилÑнÑй алгоÑиÑм?
Re: пÑоÑÑое непÑавилÑное ÑеÑеÐ
Date: 2002-12-03 07:56 am (UTC)ÐовÑÑка локалÑного минимÑма ÑÑо ÑÐ°ÐºÐ°Ñ ÑÑÑка:
ÐопÑÑÑим Ñ Ð²Ð°Ñ ÐµÑÑÑ Ð½ÐµÐºÐ¾ÑоÑÐ°Ñ Ð½ÐµÑÐ¾Ð²Ð½Ð°Ñ Ð¿Ð¾Ð²ÐµÑÑ Ð½Ð¾ÑÑÑ, и нÑжно найÑи на ней ÑамÑÑ Ð½Ð¸Ð·ÐºÑÑ ÑоÑÐºÑ - Ð²Ñ Ð±ÐµÑеÑе ÑÑалÑной ÑаÑик, кладеÑе его в пÑоизволÑнÑÑ ÑоÑÐºÑ Ð½Ð° повеÑÑ Ð½Ð¾ÑÑи, он наÑÐ¸Ð½Ð°ÐµÑ ÐºÐ°ÑиÑÑÑ Ð¿Ð¾Ð´ дейÑÑвием ÑÐ¸Ð»Ñ ÑÑжеÑÑи - когда оÑÑановиÑÑÑ ÑÑо и бÑÐ´ÐµÑ Ð¸ÑкомÑй минимÑм. Ðо ÑÑо не вÑегда веÑно - пÑедÑÑавÑÑе, ÑÑо вам повезло пеÑвÑм Ñагом положиÑÑ ÐµÐ³Ð¾ в неглÑбокÑÑ ÑÐ¼ÐºÑ Ð½Ð° веÑÑине вÑÑокой гоÑÑ. РвÑе ÑÑо неÑмоÑÑÑ Ð½Ð° Ñо, ÑÑо ÑаÑик вÑегда каÑилÑÑ ÑолÑко вниз.
ЧÑо каÑаеÑÑÑ Ð·Ð°Ð´Ð°Ñи о ÑÑкзаке, Ñо она ÑеÑаеÑÑÑ ÐºÐ°ÐºÐ¸Ð¼-Ñо ÑмнÑм пеÑебоÑом, деÑево пеÑебоÑа ÑÑÑоиÑÑÑ ÐºÐ°Ðº-Ñо Ñ Ð¸ÑÑо Ñак, ÑÑо можно на каждом ÑÐ°Ð³Ñ Ð¾ÑкидÑваÑÑ ÐºÑÑпнÑе веÑки - алгоÑиÑм вÑе-Ñавно ÑкÑпоненÑиалÑнÑй, но гоÑаздо ÑÑÑекÑивней. Я ÑейÑаÑ, к ÑожалениÑ, не воÑпÑÐ¾Ð¸Ð·Ð²ÐµÐ´Ñ Ð²Ñе ÑÑо, но можно поиÑкаÑÑ Ð² инÑеÑнеÑе.
(no subject)
Date: 2002-12-03 07:55 pm (UTC)РеÑаеÑÑÑ Ð²ÐµÐ½Ð³ÐµÑÑким меÑодом, ÑмоÑÑеÑÑ ÑÑÑ (новое окно) (http://rain.ifmo.ru/~kalugin/StartApplet_koi8.html)
(ÐСТÐÐ ÐÐÐÐ, ÐÐÐ-8!). Там даже и Ð°Ð¿Ð¿Ð»ÐµÑ ÐµÑÑÑ, показÑваÑÑий на пÑимеÑÐ°Ñ ÑабоÑÑ Ð°Ð»Ð³Ð¾ÑиÑма.
ТÑÑдоемкоÑÑÑ Ð½Ðµ помнÑ, но полиномиалÑнаÑ, мамой клÑнÑÑ :)
(no subject)
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(2N).
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.