Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Dobrý den.
Chtěl bych poprosit, zda by někdo nevěděl jakým postupem vyřešit toto:
Mám například 4 cíle a 6 družstev, dále mám určeno kolik družstev má dojí do každého cíle.
Např. do cíle 1 - 1 družstvo, do 2. - 2 družstva, do 3. - 1 družstvo, do 4. - 1 družstvo.
To je celkem 5 družstev, 1 zbyde - nikam nepůjde (to nevadí).
Každé družstvo jde určitou dobu do každého cíle. Potřebuji najít způsob jak vyhledat družstvo-cil, aby mezi 1.příchozím družstvem a posledním příchozím družstvem byl co nejkratší časový rozdíl.
Přikládám příklad viz obrázek. Je to příklad s malím počtem skupin a cílů, jde to určit pohledem.
Pro svoji potřebu bych do budoucna potřeboval o hodně více skupin a cílů.
Nevím, zda vůbec existuje nějaké matematické řešení, kromě kombinace všech veličin (které u většího počtu je skoro nekonečné) .
Předem děkuji za jakoukoliv radu.
obrázek pro lepší představu
Offline
Jedna z možností je určitě ta, že když nemůžeš vyzkoušet všechny kombinace, tak zkoušet nějaké náhodně vybrané. Sice nemáš jistotu, že najdeš nejlepší řešen ... ale nějaké najdeš...otázka je jak moc vadí, žes nenašel to nejlepší.
Já samozřejmě nevím, kolik těch skupin chceš mít, pokud jich bude kolem 30, tak to ještě půjde vyzkoušet všechny varianty. Když jich bude 60, tak už asi (na běžných počítačích) né, když jich bude 128, tak na žádných dnešních myslitelných počítačích, kdyby jich bylo 1000 tak je to mimo jakoukoliv rozumnou představu.
Na druhou stranu - čím více bude skupin a cílů, tím si budou asi jednotlivé hodnoty podobnější - těžko bude mít jeden 5 hodin a druhý 200. Takže to náhodně odhalené řešení se možná nebude moc lišit od toho optimálního.
Jsou podle mě i jednodušší problémy, které nelze nějak efektivně řešit - obecně všechny tzv. úplné NP problémy:
Odkaz
Offline
No já nevím, přijde mi, že počet kombinací je v řádu , v tomhle případě . To jse samozřejmě prd, ale kdyby jich mělo být třeba tak je asi nikdo všechny nevyzkouší. A 128 družstev není zas tak moc...
Offline
Zdravím, dle mě je jen 19 možností
Offline
↑ mák:
Ahoj, jak konstruuješ to řešení?
Ale řekl bych že tvá složitost závisí na hodnotě vstupu a nikoli jen na počtu vstupů.
Offline
jj, máš pravdu, když najdu sloupec s nejnižšími časy a sloupec s nejvyššími časy a ostatní budou mezi těmito dvěma hodnotami, tak stačí najít nejmenší rozdíl mezi těmito dvěma sloupci, ale pak ještě vymyslet aby se neopakovaly skupiny.
Offline