Ve vyhledávacím stromu níže je 11 uzlů, z nichž 5 jsou listy. Existuje 10 větví.
Je průměrný faktor větvení dán 10/6 nebo 10/11?
Jsou do výpočtu zahrnuty listy? Intuitivně bych si myslel, že ne, protože nás zajímají uzly s větvemi. Definice, kterou mi dal můj profesor, však byla „Průměrný počet větví všech uzlů ve stromu“, což by znamenalo, že jsou zahrnuty i listy.
Komentáře
- Skvělá otázka. ' jsem si dovolil přidat značku " ai-basics ". Vítejte ve Stacku: AI!
Odpověď
Řekl bych, že listy per se počítat také, ale pouze v případě, že jsou skutečnými listy, jako např. pozice šachových matů v šachu.
Takový uzel nemá ve skutečnosti žádné potomky a není nutný žádný další výpočet. Na rozdíl od uzlů, které dosud nebyly rozšířeny.
Pamatujte, že vždy počítání listů prokazatelně vede k (n-1)/n pro každou n -node thee!
odpověď
Z Wikipedie:
Ve výpočetní technice, stromových datových strukturách a teorii her je faktorem větvení počet dětí v každém uzlu , outdegree . Pokud tato hodnota není jednotná, lze vypočítat průměrný faktor větvení.
Outdegree význam – v případě směrovaných grafů počet hran vstupujících do uzel je znám jako stupeň příslušného uzlu a počet hran vycházejících z uzlu je znám jako stupeň příslušného uzlu.
Zapomněli jste outdegree část. V AI máme enerálně nakreslete směrované grafy z jednoho státu do druhého a outdegree je počet cest opouštějících konkrétní uzel. Ve vašem grafu směr není uveden. Váš graf také není symetrický, ale stále můžete zjistit větvicí faktor (s malou obtížností) nesymetrických řízených grafů, jak je uvedeno zde . Takže technicky je váš závěr správný, pokud se nepočítají listové uzly (za předpokladu, že jsou posledním stavem, ze kterého nelze dosáhnout jiného stavu – slepá ulička). Doufám, že to pomůže!