zadacha

nqkoi moje li da reshi slednata zadacha

matrica 100x100 ot byte (0-255)

da se namerat takiva 100 chisal che da nqma 2 chisla v 1 red i 1 stulb
taka che sumata im da e minimalna

Linear Assignment problem

стандартна задача от Linear Programming

има и доста код из интернет, ама ме мързи да ти го търся

Общият случай на тази задача миналата седмица я обяснявахме на студентите и се решава по много начини:

1. унгарски алгоритъм (hungarian algorithm)
2. максимален поток с минимална цена (minimal cost max-flow algorithm)
3. линейно оптимиране - не препоръчвам да се занимава човек с това, освен ако не е запален математик, любител на анализа и числените методи

Проблемът е известен още като "задача за назначенията" (assignment problem) или максимално двойкосъчетание в претеглен двуделен граф (optimal weighted matching in bipartial graph).

За съжаление всички от посочените 3 начин за решаване на задачата са доста сложни. Най-късата реализация на унгарския алгоритъм, която съм виждал беше около 300 реда. максималн поток с минимална цена може да се реализира сравнително лесно с модификация на алгоритъма на Форд-Фулкерсон за максималн поток, ама ще работи доста бавно. Има ефективни алгоритми за макс. поток с минимална цена, ама са доста сложни.

Ако искаш, пиши ми един e-mail и мога да ти изпратя реализация на унгарския алгоритъм на Pascal (sorry, преди 8 години пишех на Паскал).

Светлин Наков
[линк]

Що? Ти тогава си го измислил унгарския алгоритъм или си го превеждал от фортран?

ami togava go pisah kato gledah po edni stari bumagi na ruski ezik.
po princip algoritymyt e dosta slozen i ne sym siguren che niakoj moze da go napishe bez da gleda ot nikyde.

Светлин Наков
[линк]

една подобна задача ми попадна наскоро:

дилър иска да направи кръгова продажба на валута и да спечели, т..е. да смени долари->левове->йени->Х->У->долари и да е на печалба.

Дадена е матрица с обменните курсове на различните валути една спрямо друга, да се намери най-късата възможна кръгова продажба чиято печалба да е поне х%. Може и да не съществува такава продажба.

Каква е сложността на този алгоритъм?