+++ /dev/null
-<HTML><HEAD><TITLE>Úloha oslíka</TITLE></HEAD>
-<BODY>
-<H1 ALIGN=CENTER>Oslík:</H1>
-
-<HR>
-<A NAME="soft"><H2>Pou¾itý software:</H2></A>
-<P>Jako interpretr prologu jsem pou¾il
-<STRONG><A HREF="http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html">SWI-Prolog</A></STRONG>,
-který je dodáván s vcelku pøijatelnými licenèními podmínkami
-(a zdrojové kódy jsou souèástí). Pøikládám <A HREF="pl-3.1.2.diff">krátký patch</A>, aby
-<STRONG><A HREF="http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html">SWI-Prolog</A></STRONG>
-nepoèítal percentuální podíly funkcí pøi profilování a vypnutí automatického
-<I>garbage collector</I>u.</P><UL>
-<LI>Profiling se mi hroutil díky nezablokování v¹ech signálù pøi volání <CODE>sigblock()</CODE>,
-ale mù¾e to být jen problém mé instalace
-<LI><I>Garbage collector</I> se spou¹tìl na mùj vkus pøíli¹ èasto, jeho automatické spou¹tìní
-jsem tedy vypnul a volám jej explicitnì z Prologu
-</UL>
-<P>Aèkoliv by oba programy (obì <STRONG>Prolog</STRONG> a jedna <STRONG>C</STRONG> verze)
-mìly být spustitelné na jakékoliv platformì, uvádím testované/vývojové prostøedí:</P><UL>
-<LI><A HREF="http://www.linux.org/">GNU/Linux</A>, èásteènì <A HREF="http://www.redhat.com/">RedHat 5.0</A>
-systém,
-<A HREF="http://www.kernel.org/pub/linux/kernel/v2.1/linux-2.1.132.tar.bz2">kernel Linus-2.1.132</A>,
-glibc-2.0.7-980507, gcc version pgcc-2.91.57 19980901 (egcs-1.1 release),
-GNU Make version 3.76.1, GNU textutils 1.22.
-<LI><A HREF="http://www.swi.psy.uva.nl/usr/jan/SWI-Prolog.html">SWI-Prolog</A> verze 3.1.2.
-</UL>
-<P>Díval jsem se také na
-<A HREF="http://www.binnetcorp.com/BinProlog/">BinProlog</A>, ale zdrojové
-kódy nebyly vùbec k dispozici, a tudí¾ nepøipadl v úvahu.</P>
-
-<HR>
-<H2>Øe¹ení úlohy:</H2>
-<P>Zadáním bylo pøevést hrací plochu ze vstupního tvaru:</P>
-<PRE>
- /-------\
- | {}{}# |
- | AB^#+ |
- | CDv#+ |
- | {}{}# |
- \-------/
-</PRE>
-<P>postupným pøesouváním kostek do tvaru:</P>
-<PRE>
- /-------\
- | ????? |
- | ???AB |
- | ???CD |
- | ????? |
- \-------/
-</PRE>
-<P>kde znaky "<STRONG>?</STRONG>" samozøejmì pøedstavují políèka,
-na kterých nezále¾í. Pro popis jednotlivých znaku bude lep¹í následující
-legenda:</P>
-<TABLE ALIGN=CENTER BORDER=1>
-<TR><TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>AB<BR>CD</CODE ></FONT> - 2x2</TD>
- <TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>{}</CODE ></FONT> - 2x1</TD>
- <TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>^<BR>v</CODE ></FONT> - 1x2</TD>
- <TD ALIGN=LEFT VALIGN=BOTTOM><FONT COLOR="BLUE"><CODE>#</CODE ></FONT> - 1x1</TD>
- <TD ALIGN=LEFT VALIGN=BOTTOM>-volno-<FONT COLOR="BLUE"><BR><CODE>+</CODE></FONT> - 1x1</TD>
-</TABLE>
-<P>Postupné stavy hrací plochy pøi jednotlivých krocích minimálního (nejkrat¹ího)
-øe¹ení jsou v souboru "<A HREF="minsol.txt">minsol.txt</A>". Rozbor
-øe¹ení úlohy je sumarizován zde:</P>
-<TABLE ALIGN=CENTER BORDER=1>
-<TR><TD>Velikost stavového prostoru <TD><STRONG>25955</STRONG></TD></TR>
-<TR><TD>Poèet rùzných øe¹ení <TD><STRONG>482 (+sym.)</STRONG></TD></TR>
-<TR><TD>Poèet tahù nejkrat¹ího øe¹ení <TD><STRONG>116</STRONG></TD></TR>
-<TR><TD>Poèet rùzných nejkrat¹ích øe¹ení <TD><STRONG>1 (+sym.)</STRONG></TD></TR>
-<TR><TD>Poèet tahù nejdel¹ího øe¹ení <TD><STRONG>158</STRONG></TD></TR>
-<TR><TD>Poèet rùzných nejdel¹ích øe¹ení <TD><STRONG>7 (+sym.)</STRONG></TD></TR>
-<TR><TD>Maximální poèet tahù bez opakování<TD><STRONG>167</STRONG></TD></TR>
-</TABLE>
-<P>V¹echny tyto výsledky lze získat ze v¹ech verzí
- (<STRONG>Prolog</STRONG> <A HREF="oslik-assert.pl">assert</A>
-/ <STRONG>Prolog</STRONG> <A HREF="oslik-hash.pl" >hash</A >
-/ <A HREF="oslik.c">C</A>),
-z rychlostních dùvodù ov¹em doporuèuji pou¾ít <STRONG>C</STRONG> verzi. Pro nìkteré výsledky je
-tøeba zapnout ladící výpisy (v obou verzích se zapínají rùznì a nezdokumentovanì).</P>
-<P>Poznámka "<STRONG>(+sym.)</STRONG>" znamená, ¾e takových øe¹ení
-je ve skuteènosti dvojnásobný poèet ne¾ je uvedeno, ale tato zbylá øe¹ení
-jsou symetrická dle X-ové osy. To vyplývá ze symetriènosti zadání dle osy X
-a tomu, ¾e v¹echny povolené tahy ¾ádným zpùsobem neupøednostòují èi neomezují
-smìr pohybu.</P>
-
-<HR>
-<A NAME="cost"><H2>Nároènost øe¹ení:</H2></A>
-<TABLE ALIGN=CENTER BORDER=1>
-<TR><TD>kategorie <STRONG>\</STRONG> verze<TD><A HREF="oslik-assert.pl">Prolog assert</A><TD><A HREF="oslik-hash.pl">Prolog hash</A><TD><A HREF="oslik.c">C</A></TD></TR>
-<TR><TD>doba bìhu bez výstupu<TD><STRONG>1m:55s=115s</STRONG><TD><STRONG>4m:27s=267s</STRONG><TD><STRONG>0m:0.22s=~1s</STRONG></TD></TR>
-<TR><TD>doba bìhu s výstupem<TD><STRONG>4m:29s=269s</STRONG><TD><STRONG>6m:19s=379s</STRONG><TD><STRONG>0m:1.90s=~2s</STRONG></TD></TR>
-<TR><TD>pamì»ová nároènost<TD><STRONG>cca 50MB</STRONG><TD><STRONG>cca 150MB (!)</STRONG><TD><STRONG>cca 1MB</STRONG></TD></TR>
-<CAPTION ALIGN=BOTTOM>Konfigurace:
-<A HREF="http://www.amd.com/">AMD</A>-<A HREF="http://www.amd.com/products/cpg/k623d/">K6-2</A> 350MHz,
-256MB SDRAM, 100MHz FSB</CAPTION>
-</TABLE>
-<P>V <STRONG>Prologu assert</STRONG> se vyu¾ívá funkcí <STRONG>assert</STRONG> a <STRONG>flag</STRONG>.
-Toto øe¹ení je rychlej¹í i pøehlednìj¹í ne¾ následující, ale neodpovídá duchu Prologovského programování.</P>
-<P>V <STRONG>Prologu hash</STRONG> pou¾ívám hashování s velikostí tabulky 150 polo¾ek (deklarace
-"<STRONG>geths(150).</STRONG>", èím¾ se sna¾ím
-pøevést stavový prostor do ètvercového tvaru, aby Prolog lineárnì procházel
-hash index i hash link-list celkovì minimální èas.</P>
-<P><U>Varování:</U> Pøi standardním spu¹tìní (pøes SWI-Prolog) Oslíka budou obì Prologovské verze dumpovat
-velké mno¾ství ladících informací. Pro "production" pou¾ití slou¾í <I>bash</I> skript
-"<A HREF="do">do</A>", který tyto ladící informace ve zdrojovém kódu zru¹í a spustí automaticky prolog.
-Pøi spu¹tìní bez parametrù vypí¹e tento skript help. Nadefinování prázdného termu jako funkce pro ladící
-výpis mìlo bohu¾el drtivý dopad na rychlost interpretace.</P>
-<P>Obì Prologovské verze víceménì neobsahují ¾ádné komentáøe, doporuèuji si pøípadnì k nim otevøít verzi
-v <A HREF="oslik.c">C</A>, kde je v¹e zøejmé.</P>
-
-<HR>
-<H2>Prùbìh vývoje:</H2>
-<H3>Velikost výpoètu</H3>
-Pùvodnì jsem byl varován, ¾e výpoèet bude trvat pøíli¹ dlouho
-a pravdìpodobnì nedobìhne. Èekal jsem tedy poèet stavù prostoru minimálnì v øádu milonù, v hor¹ím pøípadì miliard.
-Nynìj¹í "<A HREF="oslik.c">oslik.c</A>"
-se pùvodnì jmenoval "stategen.c" a mìl opravdu slou¾it pouze k pøedgenerování v¹ech mo¾ných stavù a jejich
-oèíslování (mìlo by se vejít do 32-bitù, jinak by to stejnì asi nemìlo smysl prohlédávat bez
-<A HREF="http://www.distributed.net/">distributed.net</A> for my pleasure). Byl jsem ¹okován, kdy¾ program ihned dobìhl
-(tj. i mì) s celkovým poètem 25955 stavù. Proto je také kód pro sledování prùbìhu výpoètu
-(makro "<CODE>STSTEP</CODE>")
-nyní jaksi nadbyteèný a pùsobí spí¹e humorným dojmem. Celý kód jsem se také sna¾il hned napoprvé napsat co mo¾ná nejrychlej¹í.
-Pro mno¾inu stavù mám konstantní hashovací pole, seznam doposud nezpracovaných stavù i zpìtné reference pro vypisování
-výsledku (tj. z kterého stavu jsme se do aktuálního dostali).
-<H3>Struktura stavu</H3>
-Stav se ukládá jako 20-ti (5x4) znakové pole, neukládám
-tedy polohu jednotlivých velkých kostek, ale naopak mám pro ka¾dé políèko hrací plochu uveden druh/èást kostky na nìm le¾ící
-("oslík" je tedy ze 4 èástí a tyto èásti mùsí v ka¾dém korektním stavu le¾et ve správném poøadí u sebe).
-Výchozí stav je tedy vyjádøen øetìzcem "<CODE>{}{}#AB^#+CDv#+{}{}#</CODE>".
-<H3>Struktura mno¾iny stavù</H3>
-Ústøedním problémem Oslíka
-je udr¾ování mno¾iny stavù, které jsme ji¾ prohledali èi jsme je ji¾ objevili, ale je¹tì nám zbývá je zpracovat.
-V "<A HREF="oslik-hash.pl">oslik-hash.pl</A>" verzi (první v Prologu)
-to byl úplnì nejdøíve lineární seznam, co¾ ov¹em bylo èasovì neúnosné. Profiler mi potvrdil dùvodné podezøení
-na kvadratickou èasovou slo¾itost programu díky tomuto seznamu, musel jsem ho tedy vymìnit. Pro jednoduchost implementace
-jsem zvolil hash tabulku jako v <A HREF="oslik.c">C verzi</A>, kterou jsem ov¹em byl nucen implementovat jako lineární seznam
-jenotlivých políèek a obsahem ka¾dého
-prvku seznamu byl vnoøený seznam v¹ech stavù, které mají stejnou hash hodnotu, a patøí tedy k sobì. Bohu¾el v takovémto
-uspoøádání neplatí obecné pravidlo hashù, ¾e èím vìt¹í, tím rychlej¹í (samozøejmì a¾ na úplnì extrémní pøípady díky
-inicializaci a efektu memory cache). Pøi pøíli¹ velké hash tabulce by bylo bohu¾el pøíli¹ èasovì nároèné dotraverzovat
-k pøípadnému prvku na konci hash tabulky (a tedy i na konci hash seznamu). Vzhledem k tomu, ¾e jsem ji¾
-z <A HREF="oslik.c">C verze</A> znal velikost úlohy, nastavil jsem velikost hash tabulky tak, aby
-byla pøibli¾nì stejná jako prùmìrný poèet prvkù v jednom hash políèku. Ve skuteènosti tedy vytvoøí taková tabulka ètverec
-a velikost hash tabulky (tj. jeho jedna strana) by mìla být odmocninou z celkového poètu prvkù. Zvolil jsem 150 prvkù
-(ideálnì pro 22500 stavù).
-<H3>Konverze stavu</H3>
-Vyjádøení stavu zùstalo jako 20-ti znakový øetìzec (jako v <A HREF="oslik.c">C verzi</A>),
-je-li tøeba, doèasnì jej konvertuji do seznamu a nazpìt (predikát "string_to_list"). Øetìzec by mìl být
-pamì»ovì efektivnìj¹í pro ukládání do mno¾iny stavù, jemné (v <STRONG>assert</STRONG> verzi dle profileru bohu¾el hlavní)
-zpomalení díky dvojitým konverzím je pravdìpodobnì levnìj¹í ne¾ zvý¹ené pamì»ové nároky (i kdy¾ jsem to reálnì nezkou¹el).
-<H3>Pøepsání do Prologu</H3>
-Co se týèe celkové implementace, pøiznám se, ¾e jsem víceménì pøepsal tu
-<A HREF="oslik.c">C verzi</A> s tím, ¾e jsem nìkteré cykly pøepsal na rekurzi. Hlavní kontrolní dvourozmìrná
-smyèka pro kontrolu korektnosti pohybu a smyèka pro pøesun kostek zùstaly implementovány pøes "forall", nebo»
-se vyu¾ívá èíselných hodnot øídících promìnných pro adresaci polí stavu. Jména promìnných v predikátu "chkpos"
-zùstala zachována z <A HREF="oslik.c">C verze</A>, lze ji tedy pou¾ít jako pomocný text, nebo» je IMHO mnohem
-prùhlednìj¹í a ilustrativnìj¹í.
-<H3>Verze s assert/flag</H3>
-Pøepsání pøedchozí prologovské verze za vyu¾ití
-"assert" a "flag" pro uchování mno¾iny stavù místo pøedchozí hash table emulované dvojitým seznamem
-je v "<A HREF="oslik-assert.pl">oslik-assert.pl</A>".
-Scope "assert"-u i "flag"-u je globální a odpadlo tedy velké mno¾ství nechutného tahání hash tabulky
-s sebou parametrem v¹ech funkcí a¾ dovnitø (jednou jako vstupní, podruhé jako výstupní) jako
-<A HREF="http://dm.cobaltmicro.com/~ninka/kotypic/koty.html">koèka ko»ata</A>. Výsledkem bylo kromì velkého zpøehlednìní
-a zjednodu¹ení kódu také výrazné zlep¹ení rychlosti i pamì»ové nároènosti (více viz <A HREF="#cost">nároènost øe¹ení</A>).
-Urèitì bych to byl býval psal tímto zpùsobem rovnou, bohu¾el jsem se o "assert"-u a "flag"-u dozvìdìl
-a¾ po napsání pøedchozí verze.
-<H3>Atomizace</H3>
-<P>V Prologu jsem se pùvodnì potýkal s problémem nefungující unifikace nezatomizovaných øetìzcù, ale poté, co jsem objevil
-predikát "string_to_atom" ji¾ SWI Prolog unifikoval jak mìl.</P>
-
-<HR>
-<H2>Dodané soubory:</H2>
-<TABLE ALIGN=CENTER BORDER=1>
-<TR><TD><A HREF="oslik.zip" >oslik.zip</A ><TD>celý package (vèetnì Makefile-u apod.)</TD></TR>
-<TR><TD><A HREF="oslik-assert.pl">oslik-assert.pl</A><TD>oslík v SWI-Prologu, <STRONG>assert</STRONG> verze</TD></TR>
-<TR><TD><A HREF="oslik-hash.pl" >oslik-hash.pl</A ><TD>oslík v SWI-Prologu, <STRONG>hash</STRONG> verze</TD></TR>
-<TR><TD><A HREF="do" >do</A ><TD><I>bash</I> skript pro spu¹tìní pøedchozích dvou programù</TD></TR>
-<TR><TD><A HREF="oslik.c" >oslik.c</A ><TD>oslík v ANSI C (+<A HREF="http://www.bsd.org/">BSD</A> extenze)</TD></TR>
-<TR><TD><A HREF="minsol.txt" >minsol.txt</A ><TD>minimální øe¹ení (CR/LF)</TD></TR>
-<TR><TD><A HREF="pl-3.1.2.diff" >pl-3.1.2.diff</A ><TD>patch pro SWI-Prolog 3.1.2 (viz <A HREF="#soft">vý¹e</A>)</TD></TR>
-</TABLE>
-
-<HR>
-<H2>Autor:</H2>
-<TABLE ALIGN=CENTER BORDER=1>
-<TR><TD>Datum:<TD ALIGN=CENTER>30. 12. 1998</TD></TR>
-<TR><TD>Autor:<TD ALIGN=CENTER>Jan Kratochvíl</TD></TR>
-<TR><TD>Kontakt:<TD ALIGN=CENTER>e-mail <A HREF="mailto:short@ucw.cz">short@ucw.cz</A></TD></TR>
-<TR><TD>Licence:<TD ALIGN=CENTER>Public domain</TD></TR>
-</TABLE>
-<P>Tento software je poskytnut bez jakýchkoliv záruk a autor nenese ¾ádnou zodpovìdnost
-za ¹kody zpùsobené jeho pou¾íváním. Autor se také vzdává jakýchkoliv práv, ale i závazkù,
-dle smyslu <I>public domain</I> licence.</P>
-
-</BODY></HTML>
git://git.jankratochvil.net / www.jankratochvil.net.git / blobdiff