Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:



optimalizacni problem

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: optimalizacni problem

Autor: kverulant

13:10:45 15.01.2011

Tak vnoření grafu to asi není, neuvědomil jsem si, že ty objekty nejsou propojené do grafu.

Citovat příspěvek

 

Re: optimalizacni problem

Autor: kverulant

13:08:03 15.01.2011

Můžeš zkusit ILP(integer linear programming). Všechny problémy z heuristikami jsou již implementované v solverech(např. open source glpk) a ty jenom formuluješ problém. Formulace toho problému bude IMHO používat stejný trik jako formulace obchodního cestujícího pomocí ILP. To se dá najít na netu.
Jinak tohle je nejspíš problém vnoření grafu ([url] http://en.wikipedia.org/wiki/Graph_embedding [/url]).

Citovat příspěvek

 

Re: optimalizacni problem

Autor: Maaartin

17:58:56 14.01.2011

> [ital]Co se tyce narocnosti, tak mam cca stovky vrcholu grafu a desetitisice objektu, heuristikou vyberu vhodnou podmozinu, ktera je stejne velka jako mnozina vrcholu.[/ital]

A tim to totalne podelas, IMHO. Optimalizujes jednu vec ve dvou krocich, kdyz prvni bude spatne, tak je to cely spatne. Jak rozdelis cas na vyber podmnoziny a nasledujici prirazeni? Jak bez prirazeni poznas, ze mas ta podmnozina neni uplne blbe?

> [ital]Zihanim, diferencialni evoluci nebo necim podobnym bych to asi utloukl, doufal jsem ale ze existuje chytrejsi (rychlejsi) reseni.[/ital]

Pri velikosti problemu bych si nedelal moc nadeje.

S tou rychlosti - optimum nenajdes nikdy a i kdyby tak to nepoznas. Spis jde o to najit v danym case co nejlepsi reseni nebo co nejrychleji najit reseni pod nakou hranici. Algoritmy jako zihani co furt produkuji naky (snad zlepsujici se) reseni jsou na tohle dobry.

> [ital]Neslo by pouzit non-parametric MDS?[/ital]

Mandriva Directory Server? Multi-Displacement System? Minimum detectable signal? A navic bez parametru?

> [ital]Nebo dynamicke programovani?[/ital]

To je schopny najit optimum a dokazat ze se o optimum jedna. Coz tady definitivne nehrozi. Proto bych do toho nesel, na miste jsou spis postupy kde reseni hadas, vylepsujes, kombinujes, ..., bez toho aby ses snazil o exaktni postup.

Citovat příspěvek

 

Re: optimalizacni problem

Autor: F

16:57:05 14.01.2011

Zihanim, diferencialni evoluci nebo necim podobnym bych to asi utloukl, doufal jsem ale ze existuje chytrejsi (rychlejsi) reseni. Neslo by pouzit non-parametric MDS?
Nebo dynamicke programovani? Moc se v tyhle oblasti neorientuju.

Co se tyce narocnosti, tak mam cca stovky vrcholu grafu a desetitisice objektu, heuristikou vyberu vhodnou podmozinu, ktera je stejne velka jako mnozina vrcholu.

Citovat příspěvek

 

Re: optimalizacni problem

Autor: tcesky

11:08:31 14.01.2011

[ital]Premyslim jestli SOM je mesto v Idii, Somalia nebo State of Michigan, [/ital][code]
ctry adm ctry_name region
SLM SLM Solomon Islands XR3
SMO SMO Samoa (Independent State of) XR3
SMR SMR San Marino (Republic of) XR1
SOM SOM Somali Democratic Republic XR1
SMA USA American Samoa XR3

[/code]

Zdravim

TC

Citovat příspěvek

 

Re: optimalizacni problem

Autor: Maaartin

0:27:37 14.01.2011

Hezky problem, sice jsem to cetl asi 6x, nez mi to doslo. Rekl bych ze je to NP-uplny. Tech objektu je stejne jako uzlu? Kolik toho je? Potrebujes exaktni reseni nebo heuristiku?

Premyslim jestli SOM je mesto v Idii, Somalia nebo State of Michigan, ale z nich asi nebude bijektivni nic. Self-organizing maps mozna jo, ale nejspis bez zaruky, navic zobrazuji neco do nakyho prostoru kde nevim jak bych na to napasoval ty objekty. No, nejak by to jit mohlo, ale zkusil bych neco jednodussiho.

Jako nejjednodussi obecny heuristicky alg mi prijde
http://en.wikipedia.org/wiki/Simulated_annealing
Zacnes nahodnym prirazenim, definujes sousedy jako prirazeni lisici se jednim swapem, no a uz jedes. Ne ze bych si od toho moc sliboval, ale urco se da vymyslet par rozumnych vylepseni (i na ty wiki je jich az moc).

Citovat příspěvek

 

optimalizacni problem

Autor: F

23:40:07 13.01.2011

Mam specifikovany graf, mnozinu objektu a funkci, ktera vraci vzdalenost dvou objektu (trojuhelnikova nerovnost nemusi platit). Uloha je priradit ke kazdemu vrcholu prave jeden objekt, tak ze celkova vzdalenost (urcuje fce) mezi sousedy (urcuje graf) bude minimalni.

Co pouzit? Je SOM bijektivni? Znate nejaky vhodny algoritmus? dik

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: