Staonův svět - Odebírání vrcholů - zkušební kooperativa

Než pošleme Bystroňovi úkol, navrhuji vyzkoušet naše programy. Vygeneroval jsem několik zkušebních datových souborů a uvádím výsledky, které mi vyšly. Zkuste si je stáhnout a vyzkoušet, co vyjde vám. Pokud nám všem vyjde to samé, je dost velká šance, že to máme dobře :))

vrcholy/hustota 0,3 0,5 0,7 s cyklem
1 84 71 5
5 123 170 240
10 369 559 498 nelze
50 2490 2373 2341 nelze
100 5378 5233 5151 nelze
150 7198 7183 7689 nelze
200 9123 9949 9888 nelze
1000 50245 48908 48342

Grafy jsou vygenerovány náhodně a pro dané počáteční vrcholy neobsahují cykly (prošel jsem to do hloubky a odebral zpětné hrany). Počet vrcholů je od 1 do 1000. Hustotou se myslí poměr počtu hran vůči počtu hran úplného grafu. Nutno podotknout, že graf s touto hustotou byl před odebráním zpětných hran. Váhy jednotlivých uzlů jsou v intervalu 0 až 99.

Pokud by vám graf s počtem vrcholů 1000 připadal malý, tak vězte, že obsahuje skoro 350000 hran. Pro graf s 5000 vrcholy se začínáme pohybovat někde kolem 8 miliónů a má paměť pro to již byla značně nedostatečná :) Pokud si budete zkušební soubory stahovat, tak pozor, pro 1000 vrcholů a hustotu 0,7 má už skoro 3MB, takže to bude chvilku trvat.

Pokud vám to vyjde jinak, než mně, nezoufejte. Chyba je pravděpodobně na mé straně :) Rozhodně při jiných výsledcích se ozvěte, ať můžeme chybu najít.

Staon | 10.4.2006 Po 23:12 | <<< trvalý odkaz >>> | tisk | 8 komentářů

Komentáře k textu

Rss komentářů tohoto textu

[1] reaguj
Vychází stejně
nAS mejl 11.4.2006 Út 00:52

Alespoň pro ty nižší počty. Vyšší se mi nevejdou do paměti a nehodlám to překládat ještě v něčem jiném.

[2] reaguj
Staon mejl web 11.4.2006 Út 09:15

[1] nAS : paráda, to je dobrá zpráva :)

[3] reaguj
Ben mejl web 11.4.2006 Út 20:26

Hele, nechcete mluvit česky? :P Vůbec jsem to nějak nepobral. :D

[4] reaguj
Staon mejl web 12.4.2006 St 07:37

[3] Ben : ale no tak Bene, to je jen primitvní matfyzačtina uch z prváku… :))

[5] reaguj
Staon mejl web 12.4.2006 St 21:29

Zkusil jsem ještě jiný algoritmus a vyšlo mi úplně to samé, takže bych tyto výsledky považoval za správne :)))

[6] reaguj
Spaja 19.4.2006 St 20:03

Hele, ja nevim, jak to vyrabis, ale pokud to neni velkej problem, nemohl bys udelat jeste neco? Treba 200 prvku a pripadne taky nejaky s cyklama, ktery by nemely reseni… Uz mi to zaclo fungovat, tak to chci poradne ozkouset :o) Diky

[7] reaguj
Staon mejl web 19.4.2006 St 20:40

[6] Spaja : Tak jsem ti vygeneroval další zkušební data. Doufám, že jsem neudělal nekde chybu v psaní hodnot.

[8] reaguj
Spaja 19.4.2006 St 20:56

Supr, diky. Vychazi to :o) Ted uz to jenom predelat na standartni vstup a muzu to poslat :o)

Přidej komentář!

  Gravatar povolen.

Příspěvěk je formátován Texy! syntaxí. Není povoleno HTML, odkazy se převádějí automaticky.
Internetový časopis iHrom je?
Odpověd: počítačová hra časopis

Autor vzhledu: Staon. Stránky jsou postaveny na redakčním systému RS2 (verze RC2).