1 Тема від Yola Востаннє редагувалося Yola (14.01.2016 23:11:26)

  • Yola
  • Yola
  • Replace Group
  • Поза форумом
  • Звідки: ukrainian.stackexchange.com
  • Дата реєстрації: 16.04.2013
  • Повідомлень: 1 222
    • Репутація: 617

Тема: Очікувана максимальна довжина шляху від кореня до листа у дереві

Припустимо маємо дерево, кожне ребро якого може мати довжину 1 або 2 з однаковими ймовірностями. Усі шляхи від кореня до листів мають однакову кількість ребер. Знайти очікувану максимальну довжину шляху від кореня до листа.

Наприклад для дерева

     *
    / \
   /   \
  *     *

очікувана максимальна довжина становить 1/4 * 1 + 3/4 * 2 = 7/4, оскільки можливі розподіли довжин ребер 00, 01, 10, 11, і три останні дають нам максимальну довжину від кореня до листа 2, а перший - 1.

Yola вебсайт

2 Відповідь від reverse2500

  • reverse2500
  • reverse2500
  • Я діск С на троянському коні
  • Поза форумом
  • Звідки: UA Львів
  • Дата реєстрації: 08.07.2014
  • Повідомлень: 2 744
    • Репутація: 1318

Re: Очікувана максимальна довжина шляху від кореня до листа у дереві

:|

Подякували: Yola1

reverse2500 вебсайт

3 Відповідь від Yola Востаннє редагувалося Yola (15.01.2016 20:23:30)

  • Yola
  • Yola
  • Replace Group
  • Поза форумом
  • Звідки: ukrainian.stackexchange.com
  • Дата реєстрації: 16.04.2013
  • Повідомлень: 1 222
    • Репутація: 617

Re: Очікувана максимальна довжина шляху від кореня до листа у дереві

Тип:

class Tree
{
public:
    Tree() {}
    Tree(std::initializer_list<Tree> children) : m_children(children) {}
    Tree(std::vector<Tree> children) : m_children(children) {}

    const std::vector<Tree>& GetChildren() { return m_children; }

private:
    std::vector<Tree> m_children;
};

Власне алгоритм:

const int EdgeFirst = 1;
const int EdgeSecond = 2;

map<int, float> empl_internal(Tree t)
{
    map<int, float> prev;
    prev[0] = 1.f;

    for (const auto& c : t.GetChildren())
    {
        map<int, float> current;

        for (auto& lpFirst : prev)
        {
            for (auto& lpSecond : empl_internal(c))
            {
                const bool firstPath = prev[0] == 1;

                if (firstPath)
                {
                    const float probability = lpSecond.second * 0.5; 
                        // * 0.5, бо додаватимемо ребро
                    current[lpSecond.first + EdgeFirst] += probability;
                    current[lpSecond.first + EdgeSecond] += probability;
                }
                else
                {
                    const float probability = lpFirst.second * lpSecond.second * 0.5; 
                        // * 0.5, бо додаватимемо ребро до правого дерева

                    const int l1 = max(lpFirst.first, lpSecond.first + EdgeFirst);
                    current[l1] += probability;

                    const int l2 = max(lpFirst.first, lpSecond.first + EdgeSecond);
                    current[l2] += probability;
                }
            }
        }

        swap(prev, current);
    }

    return prev;
}

float empl(Tree t)
{
    float expected = 0;
    for (const auto& a : empl_internal(t))
    {
        expected += a.first * a.second;
    }

    return expected;
}

Тести:

int main()
{
    cout << empl(Tree{}) << endl;
    cout << empl(Tree{ {} }) << endl;
    cout << empl(Tree{ {}, {} }) << endl;
    cout << empl(Tree{ { {}, {} }, {} }) << endl;
    cout << empl(Tree{ {}, {}, {} }) << endl;
    cout << empl(Tree{ { {} }, { {} } }) << endl;

    cin.get();
    return 0;
}

Yola вебсайт