Matematické Fórum

↑↑ dogy:

Kdybychom věděli, že řešení existuje jen jedno, pak by se úloha nalezení jednoho konkrétního řešení o trochu zjednodušila – nutně by z toho totiž plynulo, že některé řádky a některé sloupce jsou stejné. To není nějaká moje úchylka na to zjistit kolik má úloha řešení :-).

Podle toho, co píšeš, nic takového předpokládat nemůžeme a úloha tedy může mít víc řešení.

Žádný postup mě ale zatím nenapadá, je to příliš rozsáhlá matice i na řešení hrubou silou.

Ahoj,
úlohu by bylo možné řešit přes toky v sítích:
Zdroj napojíme na všechny řádky, tyto hrany ohodnotíme součtem příslušných řádků a spotřebič napojíme na všechny sloupce a tyto hrany ohodnotíme součtem příslušných sloupců. Následně každý řádek napojíme na každý sloupec a ohodnotíme 2. Potom zřejmě řešení původního problému existuje právě když maximální tok nasytí všechny hrany vycházející ze zdroje. Plyne to z toho, že v případě celočíselného ohodnocení je maximální tok celočíselný.
Ale je to spíš práce pro stroj než pro člověka.

Edit: Ještě odkaz:
http://en.wikipedia.org/wiki/Maximum_flow_problem
http://en.wikipedia.org/wiki/Ford%E2%80 … _algorithm

↑ dogy:
Ahoj,
musíš dávat zadání jasně a přesně. Když nejdřív napíšeš, že zadání existuje a je jediné a potom napíšeš, že nemusí být jediné, tak se, ač se to jedná, tím velmi mění i úvahy, jak dané(daná) řešení najít. To, že řekneš, že je řešení jediné je velmi cenná informace, na základě které lze učinit nějaké závěry při postupu hledání řešení. Např. máme-li soustavu Ax=o, kde A je matice, x neznámý vektor a o nulový vektor a řekneš, že je řešení jediné, pak aniž bych znal tvar A, tak vím, že x=o. (A také pak mj. vím, že A je regulární.)

Teď k tématu: Asi by bylo dobré si něco přečít obecně o teorii grafů (stačí základy kdekoli na internetu) a o tocích v sítích (opět stačí zaklady). Pak můžeme přisoupit k dalším krokům.

PS: Doufám, že ta má úvaha z předchozího příspěvku je správná.

↑ check_drummer:
ahoj tak jsem se pstil do studia
zatim jsem pochopil, že
počet vrcholů je 400
počet hran je 760
ale pokavad přidám zdroj a spotřebič tak máme
počet hran 800

↑ dogy:
V tocích v sítích nemáš ohodnocené vrcholy, ale hrany.

↑ dogy:
Tak pardon, algoritmy jsou cca složtosti V.E.E, tj. zhruba K.50.500.500 operaci, cca 1mil, takže řádově zlomek vteřiny nebo několik málo vteřin...

↑ dogy:
Ahoj. A o jaký konkrétně algoritmus jde? Můžeš sem prosím napsat odkaz?