задачка

[109]

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

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

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

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

Comments

простое неправильное решенÐ

[109.livejournal.com]

а вот как я в своё время неправильно её решил.

я решил, что
1. любую N-арную перестановку можно разложить на совокупность бинарных.
2. если N-арная перестановка является "улучшающей", то хотя бы одна из составляющих её бинарных перестановок также должна является "улучшающей".
3. если ни одной "улучшающей" бинарной перестановки не осталось, то мы достигли абсолютного максимума.

таким образом, мой алгоритм перебирал все возможные бинарные перестановки, а если находил "улучшающую", то производил её, и начинал перебор сначала. такой алгоритм лучше простого перебора, поскольку простой перебор пропорционален N!, а данный алгоритм - N³.

но как оказалось, цепочка рассуждений 1-3, несмотря на кажущуюся очевидность, неверна. в чём тут кидалово, говорить пока не буду, надеясь на гениальность читателей :-)

Re: простое неправильное решеÐ

[manco.livejournal.com]

Цепочка рассуждений неверна в п3 - это еще называется ловушка локального минимума.
А еще есть подозрение, что задача эквивалентна знаменитой задаче о рюкзаке, которая NP-полна, поэтому есть шанс, что если вы ее решите, то докажете, что P=NP :)

Re: простое неправильное решеÐ

[109.livejournal.com]

а можно поподробнее? почему 3 неверно, если оно непосредственно следует из 1 + 2?

и каков же правильный алгоритм?

Re: простое неправильное решеÐ

[manco.livejournal.com]

Не следует потому что в 2) говорится что хотя бы 1 бинарная улучшающая есть, а Вы пытаетесь построить перестановку из одних только улучшающих бинарных.

Ловушка локального минимума это такая штука:
Допустим у вас есть некоторая неровная поверхность, и нужно найти на ней самую низкую точку - вы берете стальной шарик, кладете его в произвольную точку на поверхности, он начинает катится под действием силы тяжести - когда остановится это и будет искомый минимум. Но это не всегда верно - представьте, что вам повезло первым шагом положить его в неглубокую ямку на вершине высокой горы. И все это несмотря на то, что шарик всегда катился только вниз.

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

А как насчет суммы элементов

[network-angel.livejournal.com]

Она равна 1 или нет?

Re: А как насчет суммы элементо

[109.livejournal.com]

нет, эта сумма не равна 1 (см. происхождение задачи)

ОК.

[network-angel.livejournal.com]

Как насчет такого варианта -

Подсчитывается сумма каждого столбца.
Начиная со столбца с максимальной суммой - сравниваем все элементы этого столбца с элементом на главное диагонали - если больше, меняем строки местами. При столбцах с равными суммами придерживаемся какого-либо порядка - слева направо или наоборот.

Re: ОК.

[109.livejournal.com]

ну так, поставим мы максимальный элемент одного столбцп на диагональ. а дальше?

А дальше

[network-angel.livejournal.com]

делаем то же самое со следующим.

Re: А дальше

[109.livejournal.com]

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

Хранить не только максималь�

[network-angel.livejournal.com]

И если надо трогать уже поставленную на место строку - смотреть насколько улучшится общее решение?

Re: Хранить не только максимал�

[109.livejournal.com]

получаем бинарный алгоритм, описанный в самом первом моём комментарии. к сожалению, он не гарантирует нахождение абсолютного максимума.

[dma.livejournal.com]

Задача о назначениях, только чуть в другой постановке. К классическому виду приводится путем отнимания от 1 всех элементов матрицы, чтобы получилось "нежелание играть за расу Х", тогда goal - "Минимизация несчастья" :)

Решается венгерским методом, смотреть тут (новое окно) (http://rain.ifmo.ru/~kalugin/StartApplet_koi8.html)
(ОСТОРОЖНО, КОИ-8!). Там даже и апплет есть, показывающий на примерах работу алгоритма.

Трудоемкость не помню, но полиномиальная, мамой клянус :)

[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.