C - Nalezení všech cest v poli
Dobrý den,
chci projít pole všemi možnými způsoby. Při zvolení čísla 9 za POCET (pole 7*7) je již doba výpočtu neúnosná. Co teprve, kdybych chtěl někam cesty vypsat. Jak je tuto úlohu možné realizovat s nižší časovou složitostí?
Díky za odpověď
#include <stdio.h>
#include <stdlib.h>
#define POCET 9 // Velikost pole +2 pro okraje
void init();
void jdi(int x, int y);
int mrizka[POCET][POCET]; // Prochazene pole + okraj pro snizeni poctu podminek
int main(void)
{
init();
jdi(1, 1);
return 0;
}
void init()
{
for (int i = 0; i < POCET; i++) { // Naplneni pole+okraje jednickami
for (int j = 0; j < POCET; j++) {
mrizka[i][j] = 1;
}
}
for (int i = 1; i < POCET-1; i++) { // Naplneni pole nulami
for (int j = 1; j < POCET-1; j++) {
mrizka[i][j] = 0;
}
}
}
void jdi(int x, int y)
{
mrizka[x][y] = 1;
if (mrizka[x+1][y] == 0) {
jdi(x+1, y);
mrizka[x+1][y] = 0;
}
if (mrizka[x-1][y] == 0) {
jdi(x-1, y);
mrizka[x-1][y] = 0;
}
if (mrizka[x][y+1] == 0) {
jdi(x, y+1);
mrizka[x][y+1] = 0;
}
if (mrizka[x][y-1] == 0) {
jdi(x, y-1);
mrizka[x][y-1] = 0;
}
}
Máš vôbec predstavu, akým tempom rastie počet všetkých ciest s každým zväčšením mriežky? Je to viac než exponenciálne:
Neviem si predstaviť, načo by si chcel tie cesty ešte aj niekam vypisovať. Len na vypísanie ciest by si potreboval viac než 10 GB miesta (ak 1 krok = 1 bajt).
Prvá optimalizácia by mohla byť taká, že využiješ symetriu: Na začiatku, keď ideš z pozície [1,1] buď na [2,1] alebo na [1,2], preskúmaš len jednu z týchto možností a počet ciest potom prenásobíš dvoma - takáto optimalizácia ti celý výpočet dvojnásobne zrýchli. Podobné finty ti môžu podstatne zrýchliť celý výpočet. Ďalšia optimalizácia by bola zbavenie sa tej rekurzie.
Otázka je, prečo niečo takéto vôbec potrebuješ robiť a tiež to, či ti nevadí, že nájdená cesta nemusí prejsť celú mriežku.
ten pocet moznosti mas nejak blbo, napr. pri 2x2 su len 2 moznosti
A1->A2->B2->B1
A1->B1->B2->A2
neviem takto sfleku vzorec ze kolko tych moznosti tam ak je n vyssie, ale ano pocet tych operacii bude rast exponencialne ptz teoreticky ak z kazdeho pola by som mohol ist aspon na 2 smery (ak 2smery by boli uz zablokovane ze uz som tam bol) tak ten pocet operacii by bol 2^(n*n) co pri n=7 by bolo 562 949 953 421 312.To neni skutocny pocet moznosti (presne vyjadrit pocet tych moznosti je podla mna komplikovane nechce sa mi to teraz ratat), to cislo len pre predstavu ze jak to rastie (rastie to omnoho prudsie nez jak si pisal)
Keby ten pocet bol len 793 milionov jak pises tak by to dnesne CPU zvladli dost rychlo (radovo sekundy)
Jaj, to prvé som blbo opísal, lebo keď vidím 2x2, tak automaticky píšem 4.
Tam má byť naozaj 2, ostatné sú dobre.
Keď som to tak zbežne u seba pustil, tak pre 7x7 to trvalo minútu a trištvrte, čo je podľa mňa k tomu počtu adekvátne.
faktorial by bolo este vacsie cislo jak som napisal ja, musis ratat faktorial z n*n (ptz permutacie by si robil zo vsetkych poli). Ten pocet vyratat presne je problem, ale bude to niekde v tom rozsahu 2^(n*n) podla mna, 2minuty to je nejakych min. 120miliard operacii CPU, takze potom teda niekde v rozsahu okolo 100miliard to je u 7*7 (niekde radovo v strede medzi tym co som pisal ja a ty :D)