Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| # Vypracovani semestralky | |
| Line 2: | Line 3: |
| # Format diskuse # | <{ForumPost(poster="aliandroo", timestamp=2010-11-27 02:40:05)}> Potreboval bych pomoc s vypracovanim teto semestralky: Mate-li zajem napiste mi [aliandro@seznam.cz](mailto:aliandro@seznam.cz) Zadání Úkolem je realizovat program, který dokáže vypočítat efektivní průchod labyrintem s diamanty. Vstupem programu je mapa labyrintu. Mapa je předaná v textové podobě na standardním vstupu. Pro jednoduchost předpokládáme, že mapa má obdélníkový tvar. V mapě jsou naznačené diamanty (znaky *), nepřekonatelné zdi (znak #) a volné prostranství (znak mezera). Labyrint má jediný vchod v některé z obvodových zdí. Zadávání labyrintu probíhá po řádcích. Každý řádek vstupu představuje jeden řádek mapy. Zadávání celého labyrintu je signalizováno koncem souboru (feof(stdin) je aktivní). Výstupem programu je informace o tom, kolik diamantů lze z labyrintu odnést a dále informace o tom, kolik kroků v labyrintu je na to nejméně potřeba. Předpokládáme, že se můžeme pohybovat pouze ve směru vlevo/vpravo/nahoru/dolů, kde každý pohyb (o jedno políčko) je právě jeden krok. Cesta vždy začíná a končí vstupem do labyrintu. Program musí být schopen detekovat nesprávný vstup. Pokud je zadaná neplatná mapa, program vypíše chybové hlášení a ukončí se. Formát chybového hlášení je zřejmý z ukázek níže. Za chybu je považováno: * v zadání labyrintu byly jiné znaky než mezera, hvězdička, křížek a odřádkování, * labyrint není obdélníkového tvaru, * labyrint není obehnán zdí, * do labyrintu není žádný vstup nebo naopak více než jeden vstup, * v labyrintu je celkem více než 20 diamantů (pro jednoduchost předpokládáme toto omezení). Program je testován v omezeném prostředí. Je omezena doba běhu i dostupná paměť. Doba běhu je nastavena tak, aby vyhovělo i řešení hrubou silou bez heuristik. Výjimkou je bonusový test, který řešení bez alespoň základní heuristiky (zahazování neperspektivních průchodů) nezvládne časově. Nápověda * Nejprve si spočtěte matici vzdáleností mezi jednotlivými diamanty a mezi vstupem a diamanty. Zde se hodí algoritmus procházení do šířky (BFS) ve variantě semínkového vyplňování (seed fill). * Sestavte cestu, která začíná a končí vstupním bodem a prochází všemi diamanty. Takových cest existuje mnoho (počet_diamantů faktoriál), postupně vypočtěte jejich délky (vzdálenosti znáte z matice vzdáleností vypočtené v předchozím bodě) a určete nejkratší z nich. * Pro vygenerování všech možných cest budete potřebovat rekurzi. * Může se stát, že některé diamanty nebudou dostupné, takové musíte z výpočtu cest vyloučit. * Popsané řešení (hrubou silou) není příliš rychlé. Proto je volen malý rozsah úlohy (do 20 diamantů), aby výpočet skončil v rozumné době. Řešená úloha (nalezení nejkratší cesty mezi diamanty) je optimalizační variantou problému obchodního cestujícího (TSP - traveling salesman problem). Úloha TSP patří mezi tzv. NP-úplné problémy, tedy problémy, pro které neznáme efektivní algoritmus jejich řešení. Úlohy tohoto typu dokážeme řešit pouze zkoušením všech možností, což mívá vysokou operační složitost (zde například faktoriální). Řešení bývá možné urychlit heuristikami, kdy se preferují perspektivní řešení (zde např. krátké cesty), naopak neperspektivní možnosti řešení (zde např. velmi dlouhé cesty) se buď vůbec nepočítají nebo se odkládají na později. * Referenční řešení používá dvě jednoduché heuristiky - pokud v průběhu vytváření cesty mezi diamanty zjistí, že cesta je delší než dosavadní nalezené minimum, dále již cestu nedokončuje a začne vytvářet cestu jinou. Druhou možností je preference cesty směrem k nejbližšímu diamantu (při vytváření cesty se první zkusí nejbližší diamant). Tím se program relativně brzy dostane k rozumné délce cesty (ale pozor - takto nalezená cesta nemusí být nejkratší). Výhodné je obě popsané heuristiky spojit. Ukázka práce programu: |
| Line 4: | Line 47: |
| Diskuse se delaji po vlaknech `== Tema ==`, dalsi prispevky se odsazuji pomoci `*, **, ***, ...` a podepisuji pomoci `~~~~`. | Zadejte mapu: # ###### # * *# # * # ######## Diamantu: 3 Delka cesty: 14 Zadejte mapu: ############## # ############ # #* # ############## Diamantu: 1 Delka cesty: 50 Zadejte mapu: ##################### ###### #* # # ############ # ############# # # # # # ############ # ######### # # *# # # # ############## # ######### # # # # ######################## # #* * * # ############################ Diamantu: 5 Delka cesty: 148 Zadejte mapu: ############# #*# * # * #*# # # # # # # # # * # * # * # ###### ###### Diamantu: 7 Delka cesty: 46 Zadejte mapu: ############################ # * * # # ######## # # * # * # # # # ###### # # * * # # ############ * # # # * * # # # # * * # # # * ############ * # # * # ###################### ##### Diamantu: 10 Delka cesty: 86 Zadejte mapu: ############# # * # # # # # # # *# ###### ###### Diamantu: 1 Delka cesty: 12 Zadejte mapu: ##### ####### # # # # # *# ###### ###### Nespravny vstup. Zadejte mapu: ############# # # # a # # *# ###### ###### Nespravny vstup. |
| Line 6: | Line 130: |
| Kala oti einai aderfi einai oeanoflro .alla einai toso ksefonimeni na isxyrizetai oti i Kaneli tou askise prwti swmatiki via????Ase pou i Kaneli 2 lekseis na pei ton exei tapwsei to mapa giati n askhsei via? An k einai toso aderfi pou xalara ton exei tou xeriou tis i kaneli .Malista pisteuw den antapedwse ta xtypimata giati fovithike mh toy xalasei to make upVy jste banda ,ktere1 se věnuje trestne9 činosti !!!!!!!! Propagujete sve9 pojstoe nezakonnfdm jednanedm.A tedm chcete doke1zat co? Že jste banda krimine1lnedk s plnou hubou kecu,kteřed nedovedou nic jine9ho,než čme1rat po cizedm majetku!!?? To už jste doke1zali | |
| Line 8: | Line 131: |
| ## gUcqGxCFhUmHRmMy ## | <{/ForumPost}> |
| Line 10: | Line 133: |
| I would like to express my tnahks to the writer just for rescuing me from such a problem. Right after checking throughout the world wide web and finding opinions which were not powerful, I figured my entire life was well over. Living minus the solutions to the problems you have solved through this guide is a critical case, and the ones that could have badly damaged my career if I hadn't noticed your site. Your own personal skills and kindness in taking care of all areas was very useful. I'm not sure what I would have done if I had not encountered such a stuff like this. It's possible to at this point relish my future. Thanks for your time so much for your high quality and sensible guide. I will not think twice to endorse your web site to anybody who needs to have guidance on this situation.J1rfl6 , \[url=http://quejpgvrgilf.com/]quejpgvrgilf\[/url], \[link=http://wktcufzbeakr.com/]wktcufzbeakr\[/link], http://gsobadwjiubm.com/ |