Matematické Fórum

aliandro · 27. 11. 2010 02:50

Mam tento ukol.Vubec netusim jak na nej.Pomuzete mi? uvitam jakoukoliv radu

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.

Lumikodlak · 27. 11. 2010 12:28

Nejdriv normalne si ten labyrint muzes nacist do pole a pak overit ty podminky - jestli je obdelnikovy a tak podobne. Pak nejspis provedes nejaky ten BFS - tim dostanes matici, pak budes provadet to dalsi.

Vis, jak to nacist do pole a jak overit ty podminky?
Vis, jak se provadi ten BFS? (lepe podle me zabyvat se tim az kdyz to mas nactene do toho pole)
O tom dalsim kdyztak potom.

Tomasakr

Chtěl bych požádat o radu. Je nás víc, kdo tento úkol dělají. Mám všechno hotový, ale zasekl jsem se u rekurze. Postupně, když jsem procházel bludiště vytváře jsem si tabulku vzdáleností v tomto tvaru:

Code:

0   1  5   5   9    9   12 12 
1   0  4   4   8    8   11 11 
5   4  0   8   4    12 7   15 
5   4  8   0   12  4   15 7 
9   8  4   12 0    16 3   19 
9   8  12  4  16  0   19  3 
12 11 7   15 3   19  0   22 
12 11 15 7   19 3    22 0

Kde index [0] je vchod a ostatni indexy jsou poradi diamantu, jak jsem si určil průchodem grafu.

Nemáte pls nějaký nápad, jak vygenerovat všechny možné cesty ?

vojta01 · 22. 01. 2011 14:05

Ahoj, já si myslím, že řešením této úlohy je hledání tvz. Hamiltonovské kružnice.
Vrcholy grafu budou políčka s diamanty a hrany budou mezi každými dvěma vrcholy a její ohodnocení bude rovno nejkratší cestě (bez diamantů), nebo nekonečno, pokud na nejkratší cestě bude nějaký diamant.
Poté pomocí známého algorimtu vyhledám nejlevnější Hamiltonovskou kružnici - tedy takovou kružnici, která začíná a končí ve vchodu/východu a prochází všemi vrcholy s diamanty právě 1×.

Lumikodlak

Vsechny mozne cesty jsou vlastne vsechny permutace s tolika prvky, kolik je diamantu (v tom tvem prikladu 7). Poradi prvku v permutaci je poradi, ve kterem se ten diamant sbira. Jak je psano v zadani, bude jich (počet_diamantů faktoriál) coz je hodne. Vygenerovat vsechny jde treba rekurzivnim volanim (jak je psano v zadani) - ze ze vsech nepouzitych diamantu postupne jeden vybiras a pak rekurzivne volas tu samou funkci na ty zbyvajici. Nebo bys chtel videt primo jak by mela vypadat ta funkce? (Nebo akorat nevis jak to napsat s tema heuristikama?)

Priklady cest: (aby z toho bylo videt ze jsou to permutace)
1 2 3 4 5 6 7
1 2 3 4 5 7 6
...
2 5 4 7 6 1 3
...
7 6 5 4 3 2 1

(uz jsem zase napsal hned po nekom prispevek :-) tak se omluvam Vojtovi)

Tomasakr · 22. 01. 2011 15:22

↑ Lumikodlak:
Já jsem se zasekl u generování všech permutací. Nevím, jak to dát dohromady s tou tabulkou. Respektive jsem nevymyslel takovej algoritmus, kterej by to z matice vzdáleností popořadě tahal. U těch heuristik mám představu.

Lumikodlak · 22. 01. 2011 16:46

Mas na mysli u samotneho generovani, nebo jak to dat dohromady s tou tabulkou? :-)

S tou tabulkou - mas napriklad tu permutaci 2 5 4 7 6 1 3 co jsem psal, coz je nejdrive od vchodu k diamantu 2, pak od diamantu 2 k diamantu 5, pak k diamantu 4 atd. Jestli to dobre chapu, tak v te tabulce na indexu[x][y] mas ulozenou vzdalenost mezi diamanty x a y. Prvni cesta je 0-2, takze vzdalenost mezi 0 a 2 je v tabulce na indexu [0][2], dalsi je cesta 2-5 coz je v tabulce index [2][5], pak dalsi index [5][4] atd (ty indexy muzou byt samozrejme opacne). Takhle sectes vsechny vzdalenosti.

V tom prikladu co jsem psal by s tou tvoji tabulkou vyslo:
0 - 2 : 5
2 - 5 : 8
5 - 4 : 16
4 - 7 : 19
7 - 6 : 22
6 - 1 : 11
1 - 3 : 4
3 - 0 : 3
Coz je dohromady vzdalenost 88 jestli jsem to dobre spocital (tohle zrovna neni asi moc kratky pruchod).

Tak kdyztak dej vedet, jestli to pomohlo, mozna jsem to spatne pochopil a problem je v necem jinem :-)

Tomasakr

Promin špatně jsem se vyjádřil. Konkrétní problém mám v tom, že neumim vytvořit tu funkci na generování všech cest (rekurzivně).

Lumikodlak · 22. 01. 2011 18:28

Da se k tomu neco najit na Foru nebo na Wikipedii napriklad, ale to nevim, jestli pomuze.

Jde to ruznymi zpusoby.

Nenapada bohuzel nic jednodussiho nez tohle treba: (nevim v cem to programujes, kdyztak to pak upravim jeste, tohle je v C)

Code:

void ProjitPermutace (int Delka, int Prvek, int Poradi[], char Pouzite[]){
    char NovePouzite [MAX_POCET];
    int NovePoradi [MAX_POCET];
    int DalsiDelka;
    int Index;

    if (Prvek == Pocet){
        //    Tady uz jsou pouzity vsechny diamanty, takze nejak zpracovat 
    }
    else{
        memcpy (NovePouzite, Pouzite, sizeof(NovePouzite));
        memcpy (NovePoradi, Poradi, sizeof(NovePoradi));
        for (Index = 0; Index < Pocet; Index++){
            if (NovePouzite [Index] == 0){
                NovePouzite [Index] = 1;
                NovePoradi [Prvek] = Index + 1;

                if (Prvek > 0) DalsiDelka = Delka + TabulkaVzdalenosti [Poradi [Prvek-1]] [Index + 1];
                else  DalsiDelka = Delka + TabulkaVzdalenosti [0] [Index + 1];

                ProjitPermutace (DalsiDelka, Prvek + 1, NovePoradi, NovePouzite);
                NovePouzite [Index] = 0;
            }
        }
    }
}

Doufam, ze je to citelne alespon trochu. Je to bez te heuristiky, takze to akorat projde vsechny moznosti, s tou heuristikou to bude potom jeste slozitejsi.

Tomasakr

Jj v céčku je to ideální. Jenom bych se chtěl zeptat:
Co znamena proměnná: prvek ( To je index diamantu? ).
Jak jsou nastaveny na pocatku pole: poradi a pouzite?
A jestli to dobře chápu: poradi (resp. noveporadi ) je pole, které uchovává aktuální pořadí celé cesty a použité je pole, do kterého se zadává stav ( jestli byl prvek zaclenen do cesty nebo jeste ne) ?
Děkuju.

Lumikodlak · 22. 01. 2011 22:40

Prvek - tim jsem myslel poradi diamantu / prvek v permutaci, ktery se zrovna prozkoumava a zkousi.
Poradi (NovePoradi) - je to tak, jak pises, tam se uchovavaji cisla diamantu v dane ceste. (Ten nazev je asi matouci)
Pouzite - take je to tak, jak pises.

(To pole Poradi a Pouzite by mohly byt klidne globalni/staticke, nemusely by se predavat v te funkci a vysledek by byl stejny)

Ten Index + 1 je tam proto, ze Index jde od nuly do Poradi-1, ale na nulove pozici v tabulce je vchod a diamanty zacinaji az od jedne.

Tomasakr · 22. 01. 2011 23:28

Děkuju moc. To je přesně to, co jsem potřeboval. Hodně jsi mi s tím pomohl.

Matematické Fórum

#1 27. 11. 2010 02:50

Pro zkusenejsi - algoritmus na labyrint s diamanty

#2 27. 11. 2010 12:28

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#3 22. 01. 2011 10:55 — Editoval Tomasakr (22. 01. 2011 12:44)

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

Code:

#4 22. 01. 2011 14:05

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#5 22. 01. 2011 14:08 — Editoval Lumikodlak (22. 01. 2011 14:10)

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#6 22. 01. 2011 15:22

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#7 22. 01. 2011 16:46

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#8 22. 01. 2011 17:04 — Editoval Tomasakr (22. 01. 2011 17:10)

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#9 22. 01. 2011 18:28

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

Code:

#10 22. 01. 2011 19:48 — Editoval Tomasakr (22. 01. 2011 21:44)

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#11 22. 01. 2011 22:40

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

#12 22. 01. 2011 23:28

Re: Pro zkusenejsi - algoritmus na labyrint s diamanty

Zápatí