Nejkratsi cesta a pocet diamantu v labyrintu – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

Nejkratsi cesta a pocet diamantu v labyrintu – C / C++ – Fórum – Programujte.comNejkratsi cesta a pocet diamantu v labyrintu – C / C++ – Fórum – Programujte.com

 

david900
~ Anonymní uživatel
2 příspěvky
27. 11. 2010   #1
-
0
-

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:



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.

Nahlásit jako SPAM
IP: 174.36.199.–
david900
~ Anonymní uživatel
2 příspěvky
27. 11. 2010   #2
-
0
-

To david900 : Dostal jsem tento projekt a vubec netusim jak na nej.Pomuzete mi?

Nahlásit jako SPAM
IP: 174.36.199.–
Marian B.
~ Anonymní uživatel
1 příspěvek
23. 12. 2010   #3
-
0
-

Nejdříve zdravim kolegu z FIT ČVUT, který se tímto zpusobem snaží vyřešit svoji semestrálku.

Nejdříve si vypočti vzdálenosti mezi každýma 2 věcma v bludišti tímto algoritmem:

http://en.wikipedia.org/wiki/Pathfinding

Potom pomocí jendoduché rekurze vyzkoušíš všechny možné trasy (kombinatorika) a vytiskneš tu nejkratší. A je to.

Nahlásit jako SPAM
IP: 81.90.175.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 92 hostů

Podobná vlákna

Nejkratsi cesta — založil Jardan

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032024 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý