0042949 20240103182919.720071024235959.9 000263387000012 67650311310 10.1162/neco.2008.10-07-623 35 s. cav_un_epca*02573090899-7667212 (2009)583-617 sequential triangle strip combinatorial optimization Hopfield network minimum energy simulated annealing cav_un_auth*0100836 Šíma Jiří UIVT-O Department of Theoretical Computer Science Ústav informatiky AV ČR, v. v. i. cav_un_auth*0101154 Lněnička Radim UTIA-B Ústav teorie informace a automatizace AV ČR, v. v. i. 1M0545 GA MŠk CZ cav_un_auth*0203502 1ET100300517 GA AV ČR cav_un_auth*0001446 1M0572 GA MŠk cav_un_auth*0001814 CEZ:AV0Z10300504 CEZ:AV0Z10750506 The important task of generating the minimum number of sequential triangle strips (tristrips) for a given triangulated surface model is motivated by applications in computer graphics. This hard combinatorial optimization problem is reduced to the minimum energy problem in Hopfield nets by a linear-size construction. In particular, the classes of equivalent optimal stripifications are mapped one to one to the minimum energy states that are reached by a Hopfield network during sequential computation starting at the zero initial state. Thus the underlying Hopfield network powered by simulated annealing (i.e. Boltzmann machine) which is implemented in a program HTGEN can be used for computing the semi-optimal stripifications. Practical experiments confirm that one can obtain much better results using HTGEN than by a leading stripification program FTSG although the running time of simulated annealing grows rapidly near the global optimum. Nevertheless, HTGEN exhibits empirical linear ... Důležitá úloha generování minimálního počtu sekvenčních trojúhelníkových pásů (tristrips) pro daný triangulovaný povrchový model je motivována aplikacemi v počítačové grafice. Tento těžký kombinatorický problém je redukován na problém minimální energie v Hopfieldových sítích pomocí konstrukce lineární velikosti. Speciálně třídy ekvivalentních optimálních stripifikací jsou vzájemně jednoznačně zobrazeny na stavy s minimální energií, které jsou dosaženy Hopfieldovou sítí během sekvenčního výpočtu začínajícího v nulovém počátečním stavu. Tedy příslušnou Hopfieldovu síť zesílenou o simulované žíhání (tj. Boltzmannův stroj), která je implementována v programu HTGEN, lze použít pro výpočet semioptimálních stripifikací. Praktické experimenty potvrzují, že HTGEN může dosáhnout mnohem lepších výsledků než vedoucí konvenční stripifikační program FTSG (který představuje referenční stripifikační metodu, která není založena na neuronových sítích), i když výpočetní čas simulovaného žíhání roste ... 2009 IN 4 O 4o 20231122133552.0 http://hdl.handle.net/11104/0136070 2.967 0.375 9.8 0.01389 1.175 7456 128 2009 Soubory v repozitáři: 0042949.pdf 67650311310 SCOPUS 000263387000012 WOS cav_un_epca*0257309 Neural Computation 0899-7667 1530-888X Roč. 21 č. 2 2009 583 617