Pomoc s algoritmem - Backtracking – Java – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Pomoc s algoritmem - Backtracking – Java – Fórum – Programujte.comPomoc s algoritmem - Backtracking – Java – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
dreIx0
Duch
30. 3. 2010   #1
-
0
-

Dobrý den,

chtěl bych vás poprosit, zda - li byste mi prosím pomohli vytvořit finální fázi mého úkolu do algoritmizace. Nevím si už rady... :smile10:

Dostaneme zadanoý obdelník M*N prvků a několik tetrisových kostiček. Naším úkolem je najít všechna řešení, jakými se dají tyto tetrisové kostičky nacpat do zadané šachovnice. Tyto kostičky lze otočit o 90°, 180° a 270°.

Zpracování velmi krkolomného vstupu už mám za sebou, mám

    public static List<int[][]> uloziste = new ArrayList<int[][]>();

public static List<int[][]> uloziste1 = new ArrayList<int[][]>();
public static List<int[][]> uloziste2 = new ArrayList<int[][]>();
public static List<int[][]> uloziste3 = new ArrayList<int[][]>();

kde v ulozisti jsou int [][] pole, ve kterém jsou originální kostičky a v ostatních jsou na stejných indexech jejich rotace.

a
int[][] podklad

což je ten obdelník, na který musím naházet všechny ty tetrisové kostičky a najít všechny varianty.

Teď nastává můj problém... Co jsem se tak dočetl, mělo by to jít rekurzí resp backtrackingem...ale jsem v koncích, žádné mé řešení nefunguje a termín odevzdání se blíží....

Prosím vás tedy, zkušené magiče, zda-li byste si nenašli chvilku na tento problém, mockrát děkuji :smile1:

Nahlásit jako SPAM
IP: 147.32.122.–
Reklama
Reklama
dreIx0
Duch
30. 3. 2010   #2
-
0
-

Zde přidávám zdroják :o)

Nahlásit jako SPAM
IP: 147.32.122.–
liborb
~ Redaktor
+18
Guru
31. 3. 2010   #3
-
0
-

Je samozřejmě několik možností, jak to řešit. Problém je totiž v tom, že nezáleží jenom na tom, kde se začne, ale i s jakou a jak natočenou kostičkou. Řešení by se tedy dalo rozdělit na 2 části: výběr kostiček (v daném pořadí a rotaci) a umisťování do hracího pole. Vytvořit si algoritmus na získání sady kostiček (pořadí + rotace - ne všechny jsou rozdílné v rotaci), tj. postupně vygenerovat všechny možnosti. A v druhé části je postupně umísťovat, stačí tupě zkoušet pozici po pozici (kolize jsou neperspektivní větve atd.).

Když budu mít zadané velké hrací pole a pouze jednu kostičku, tak vlastně všechny možnosti jsou i řešení. To je potřeba mít na paměti než začneš svoje řešení (až ho budeš mít) optimalizovat.

Nahlásit jako SPAM
IP: 85.207.166.–
dreIx0
Duch
31. 3. 2010   #4
-
0
-

To liborb :

Děkuji za odpověď!

Momentálně jsem ve stavu, kdy mám toto:

public static void Hledac(int indexKosticky, int[][] policko) {

int souradniceX = 0;
int souradniceY = 0;


// ----
for (int i = 0; i < policko.length - uloziste.get(indexKosticky).length + 1; i++) {
for (int j = 0; j < policko[0].length - uloziste.get(indexKosticky)[0].length + 1; j++) {

int zdaLi = 0;
// overovani kosticky
for (int k = 0; k < uloziste.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste.get(indexKosticky)[0].length; l++) {

if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste.get(indexKosticky)[k][l] == 0)) {
} else {
zdaLi++;
}
}
}
if (zdaLi == 0) {
souradniceY = i;
souradniceX = j;

// kopceni do pomocneho policka
for (int k = 0; k < policko.length; k++) {
for (int l = 0; l < policko[0].length; l++) {
copik[k][l] = policko[k][l];
}
}

for (int k = 0; k < uloziste.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste.get(indexKosticky)[0].length; l++) {
copik[k + souradniceY][l + souradniceX] += uloziste.get(indexKosticky)[k][l];
}

}

if (indexKosticky + 1 < uloziste.size()) {
Hledac(indexKosticky + 1, copik);
} else {
Vypisovac(copik);
}

}

}
}



// ---- otocene o 90
if (uloziste1.get(indexKosticky)[0][0] != -9) {
for (int i = 0; i < policko.length - uloziste1.get(indexKosticky).length + 1; i++) {
for (int j = 0; j < policko[0].length - uloziste1.get(indexKosticky)[0].length + 1; j++) {

int zdaLi = 0;
// overovani kosticky
for (int k = 0; k < uloziste1.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste1.get(indexKosticky)[0].length; l++) {

if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste1.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste1.get(indexKosticky)[k][l] == 0)) {
} else {
zdaLi++;
}


}
}
if (zdaLi == 0) {
souradniceY = i;
souradniceX = j;

// kopceni do pomocneho policka
for (int k = 0; k < policko.length; k++) {
for (int l = 0; l < policko[0].length; l++) {
copik[k][l] = policko[k][l];
}
}


for (int k = 0; k < uloziste1.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste1.get(indexKosticky)[0].length; l++) {
copik[k + souradniceY][l + souradniceX] += uloziste1.get(indexKosticky)[k][l];
}

}


if (indexKosticky + 1 < uloziste1.size()) {
Hledac(indexKosticky + 1, copik);
} else {
Vypisovac(copik);
}
}

}
}
}





// --- otocene o 180
if (uloziste2.get(indexKosticky)[0][0] != -9) {
for (int i = 0; i < policko.length - uloziste2.get(indexKosticky).length + 1; i++) {
for (int j = 0; j < policko[0].length - uloziste2.get(indexKosticky)[0].length + 1; j++) {

int zdaLi = 0;
// overovani kosticky
for (int k = 0; k < uloziste2.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste2.get(indexKosticky)[0].length; l++) {

if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste2.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste2.get(indexKosticky)[k][l] == 0)) {
} else {
zdaLi++;
}


}
}
if (zdaLi == 0) {
souradniceY = i;
souradniceX = j;

// kopceni do pomocneho policka
for (int k = 0; k < policko.length; k++) {
for (int l = 0; l < policko[0].length; l++) {
copik[k][l] = policko[k][l];
}
}


for (int k = 0; k < uloziste2.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste2.get(indexKosticky)[0].length; l++) {
copik[k + souradniceY][l + souradniceX] += uloziste2.get(indexKosticky)[k][l];
}

}




if (indexKosticky + 1 < uloziste2.size()) {
Hledac(indexKosticky + 1, copik);
} else {
Vypisovac(copik);
}
}

}
}
}




// --- otocene o 270
if (uloziste3.get(indexKosticky)[0][0] != -9) {
for (int i = 0; i < policko.length - uloziste3.get(indexKosticky).length + 1; i++) {
for (int j = 0; j < policko[0].length - uloziste3.get(indexKosticky)[0].length + 1; j++) {

int zdaLi = 0;
// overovani kosticky
for (int k = 0; k < uloziste3.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste3.get(indexKosticky)[0].length; l++) {

if ((policko[i + k][j + l] == 1) || (policko[i + k][j + l] > 1 && uloziste3.get(indexKosticky)[k][l] == 0) || (policko[i + k][j + l] == 0 && uloziste3.get(indexKosticky)[k][l] == 0)) {
} else {
zdaLi++;
}


}
}
if (zdaLi == 0) {
souradniceY = i;
souradniceX = j;

// kopceni do pomocneho policka
for (int k = 0; k < policko.length; k++) {
for (int l = 0; l < policko[0].length; l++) {
copik[k][l] = policko[k][l];
}
}


for (int k = 0; k < uloziste3.get(indexKosticky).length; k++) {
for (int l = 0; l < uloziste3.get(indexKosticky)[0].length; l++) {
copik[k + souradniceY][l + souradniceX] += uloziste3.get(indexKosticky)[k][l];
}

}




if (indexKosticky + 1 < uloziste3.size()) {
Hledac(indexKosticky + 1, copik);
} else {
Vypisovac(copik);
}
}

}
}
}

}


A je tam nějaká malilinkatá chybka - u některých zadání mi to vypíše pouze jedno řešení, jindy žádné... a zaboha nemůžu přijít na to, kde je chyba... :(

Nahlásit jako SPAM
IP: 147.32.122.–
liborb
~ Redaktor
+18
Guru
1. 4. 2010   #5
-
0
-

Pokud je není možné krokování, tak doporučuji ladící výpisy, abys viděl, kde se co děje a proč. Kde to končí a proč atd.

No a pokud chceš pomoci trochu víc :smile1:, tak se hoď kompletní zdroják i popis jak se to pohání (vstup).

Nahlásit jako SPAM
IP: 85.207.166.–
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, 32 hostů

Moderátoři diskuze

 

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