Hledání minimálního počtu uzlů ve stromě (C++) – C / C++ – Fórum – Programujte.com

Dobrý den,potřeboval bych poradit s program pro nalezení minimálního počtu uzlů ve stromě. Program "hrubou" silou mám, ale ještě mi chybí program pomocí dynamického programování. Můžete mi prosím poradit?Program hrubou silou: (Visual Studio 2013)

#include "stdafx.h"
#include <iostream>
#include <algorithm> 
using namespace std;
int opakovani = 0;

int image[4][4] = {
    { 1, 1 ,1 ,1 },
    { 0,0, 0 ,1 },
    { 0, 0, 0 ,1 },
    { 1, 1 ,1 ,1 },
    };

int deleni(int x1, int x2, int y1, int y2);

int main()
{
    int vysl = deleni(0,3, 0,3);
    cout <<"Nejmensi pocet uzlu je: "<< vysl << endl;
    cout << opakovani;
    cin.get();
    cin.get();
    return 0;
}

int deleni(int x1, int x2, int y1, int y2) {

    bool black = false;

    bool white = false;

    for (int i = x1; i <= x2; i++) {

        for (int j = y1; j <= y2; j++) {
            
             
            
            if (image[i][j] == 0)
            {
                    
                white = true;
            }
            if (image[i][j] == 1)
            {
                
                black = true;
            }

        }

    }
    
    
    if (!(black & white)) { opakovani++; return 1; }

    // TADY BYCH DAL TEST, JESTLI VÝSLEDEK S PARAMETRY int x1, int x2, int y1, int y2 UŽ JE V SEZNAMU, POKUD ANO, TAK HO ROVNOU VRÁTÍM

    int vysledek = 2 * (x2 - x1 + 1) * (y2 - y1 + 1) - 1;

    for (int i = y1; i < y2; i++) {
        
        vysledek = min(vysledek, deleni(x1, x2, y1, i) + deleni(x1, x2, i + 1, y2) + 1);
    }

    for (int i = x1; i < x2; i++) {
        vysledek = min(vysledek, deleni(x1, i, y1, y2) + deleni(i + 1, x2, x1, y2) + 1);
    }
    
    
    // TADY BYCH ULOŽIL DO SEZNAMU REŠENÍ S PARAMETRY int x1, int x2, int y1, int y2
    opakovani++;    
    return vysledek;
}

Nechce se mi nad tím přemýšlet, ale myslím si, že do toho prvního cyklu pro dělění podle Y můžeš rovnou hodit ještě dělení podle X a budeš to mít bez opakování.

Jinak na to ukládání předchozích výsledků je pohodlné použít std::map (ale myslím si, že to teda nepotřebuješ).

Tak ne, to dělení uvnitř je blbost.

#3 gna
A Nějaká jiná rada by nebyla?

A s čím chceš poradit? Máš to správně, jen doplň tu optimalizaci.

#5 gna
To mi právě nejde, nějak se přes to nemůžu dostat.

Ideální způsob by bylo použít std::unordered_map, ale pro ten by sis musel naimplementovat vlastní hashovací funkci, což není úplně sranda. Je tu ale i naivní přístup, který v tomto případě bude stačit, v praxi by byl paměťově dost drahý.

V první řadě: 2D pole je pomalejší než 1D pole. Pokud chci mít 2D pole s S sloupci a R řádky, stačí mi 1D pole o velikosti S x R. Pro přístup k položce na souřadnicích x,y mi pak stačí vzorec y * S + x. Toho bys mohl využít. Možných výsledků dělení je 16 x 16. Mohl by sis udělat 2D pole 16 x 16, naplněné hodnotami -1, které by znamenaly, že tam není nic vypočítaného. Pro přístup k výsledku dělení s parametry x1, y1, x2, y2 bys pak použil formuli výsledek[y1 * 4 + x1][y2 * 4 + x2]. Pokud by tam byla -1, musel by sis to spočítat, pokud by tam bylo cokoliv jiného, vrátil bys to. Mohl by sis dokonce zafajnšmekřit a implementovat to 1D polem (odvození výpočtu indexu nechám na tobě).

Existuje i třetí cesta střední obtížnosti a střední výkonosti - zjednodušená implementace řídkého vektoru. Velice zjednodušeně bys měl nafukovací pole, do kterého bys pro každý spočítaný výsledek vložil ntici x1,y1,x2,y2 a příslušný výsledek. Při hledání výsledku bys ale musel projít celé to nafukovací pole a hledat, zda v něm máš příslušný výsledek (stále je to ale výkonnější než to, co děláš teď). V jistém smyslu slova pro toto jde využít i std::map (která to prohledávání udělá za tebe), ale mám podezření, že bys do ní musel narvat porovnávací funkci, což není tak težké, jako ta hashovací, ale nevím, jestli na to stačí tvé zkušenosti.

Snad jsem to napsal dostatečně srozumitelně. Mmch pár připomínek ke kódu, který máš: podmínky v těch dvou zanořených forech nemusí být if a if, ale if a else if, neboť ty děláš buď a nebo. Postřeh 2: if (!black & white)) ti sice funguje, ale pochybuji, žes to tak napsal záměrně. Je rozdíl mezi & a &&. To první provede binární součin a podmínka něco a něco je realizována operátorem &&. Při importu knihovny ciso646 můžeš používat i podstatně výmluvnější klíčové slovo 'and' (a taky or a not).
 

#include <map>
#include <sstream>
...
// treba string -> int
map<string, int> cache;
...
int deleni(int x1, int x2, int y1, int y2) {
	...
	stringstream ss;
	ss << x1 << "," << x2 << "," << y1 << "," << y2;
	string key = ss.str();

	// pokud klic v mape neni, tak se timhle ctenim i vytvori
	// v nasem pripade to nevadi, protoze ho tam stejne budeme vkladat
	vysledek = cache[key];
	
	// pokud byl klic vytvoren, tak s vychozi hodnotu
	// v nasem pripade intu tedy 0, kterou tam jinak nevkladame
	// takze nenulova hodnota je drive explicitne vlozena hodnota
	if (vysledek)
		return vysledek;

	vysledek = vypocet...

	cache[key] = vysledek;

#8 gna
Velice elegantní řešení. Není nejrychlejší, ale zato je nejjednodušší

#8 gna
Děkuji mnohokrát.