Комбинаторика

SQL HowTo обрабатываем дерево упорядочиваем иерархию с рекурсией и без

19.10.2020 20:09:27 |

Автор: admin

Видимо, это осень так влияет, что за последний месяц на PostgreSQL уже и в Морской бой играли, и Жизнь Конвея эмулировали Что уж оставаться в стороне! Давайте и мы потренируем мозг в реализации нетривиальных алгоритмов на SQL.

Тем более, сегодняшняя тема родилась из обсуждения моей же статьи PostgreSQL Antipatterns: Бесконечность не предел!, или Немного о рекурсии, где я показал, как можно заменить рекурсивное чтение иерархичных данных из таблицы на линейное.

Прочитать-то мы прочитали, но ведь чтобы для вывода упорядочить элементы дерева в соответствии с иерархией, уж точно придется воспользоваться рекурсией! Или нет? Давайте разберемся, а заодно решим на SQL пару комбинаторных задач.

Давайте возьмем в качестве примера прочитанный из базы набор записей чего-то вроде справочника сотрудников. Они образуют ориентированное дерево из отделов и работающих в них сотрудников, которое выглядит примерно вот так:

Точнее, это нам хочется, чтобы оно выглядело именно так дочерний узел под родительским, правильная сортировка детей внутри одного предка, красивые отступы Но база-то нам отдаст записи отсортированными в том порядке, который удобнее ей скорее всего, по первичному ключу id:

Давайте все-таки сначала формально определим те правила, которым должен отвечать искомый порядок записей:

элемент-предок стоит раньше любого из элементов его поддерева
дочерние элементы внутри одного родительского упорядочиваются по дополнительному прикладному ключу

Второе требование отражает привычные для пользователя паттерны, когда папки внутри одного каталога отображаются отсортированными по названию, а ответы на сообщение в ветке форума по времени.

Мы, для простоты, возьмем в нашем примере в качестве такого ключа data.

Таков путь!

Собственно, а что мы такое можем сконструировать, чтобы сортировка этого чего-то давала нам желаемый результат?

Давайте для каждого элемента дерева вычислим путь цепочку из прикладных ключей всех элементов, которые надо пройти от корня, чтобы его достигнуть:

Но если на каждом шаге такого пути мы сортируем элементы согласно прикладному ключу, то и массивы, составленные из этих ключей, будучи отсортированными, дадут нам искомый порядок записей!

Рекурсивная сортировка

Сначала воспользуемся наиболее традиционным и очевидным способом получения нужного нам результата рекурсивным запросом:

WITH RECURSIVE src(id, pid, data) AS (  VALUES    (1, NULL, 'A')  , (2, 1, 'AA')  , (3, 2, 'AAA')  , (4, 1, 'AB')  , (5, 2, 'AAB')  , (6, 3, 'AAAA')  , (7, 5, 'AABA')  , (8, 4, 'ABA')  , (9, 7, 'AABAA')  , (10, 2, 'AAC')), T AS (  SELECT    id  , ARRAY[data] path -- инициализируем массив пути корневым элементом  FROM    src  WHERE    pid IS NULLUNION ALL  SELECT    s.id  , T.path || s.data -- наращиваем путь  FROM    T  JOIN    src s      ON s.pid = T.id)SELECT  *FROM  srcNATURAL JOIN  TORDER BY  path; -- сортируем согласно пути

 id | pid | data  |         path----+-----+-------+-----------------------  1 |     | A     | {A}  2 |   1 | AA    | {A,AA}  3 |   2 | AAA   | {A,AA,AAA}  6 |   3 | AAAA  | {A,AA,AAA,AAAA}  5 |   2 | AAB   | {A,AA,AAB}  7 |   5 | AABA  | {A,AA,AAB,AABA}  9 |   7 | AABAA | {A,AA,AAB,AABA,AABAA} 10 |   2 | AAC   | {A,AA,AAC}  4 |   1 | AB    | {A,AB}  8 |   4 | ABA   | {A,AB,ABA}

Подключаем комбинаторику

А теперь вернемся к началу статьи и подумаем, как же все-таки для той же самой задачи мы можем создать нерекурсивное решение. В этом нам поможет

Комбинаторика (комбинаторный анализ) раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка).

Сначала решим несколько небольших типовых задач из этой области.

Комбинации

Пусть у нас есть исходный массив {A,B,C}, все элементы которого уникальны. Получим все комбинации массивов той же длины, состоящие из его элементов:

{A,A,A}{A,A,B}{A,A,C}{A,B,A}{A,B,B}...{C,C,B}{C,C,C}

Достаточно очевидно, что при длине массива N таких вариантов будет ровно N^N, но как получить их на SQL?

Обратим внимание, что каждой комбинации элементов соответствует комбинация позиций этих элементов в исходном массиве, если пронумеровать их с нуля. А каждой такой комбинации число в N-ричной системе счисления:

3^2 |  0  0  0  0  0  0  0  0  0  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2  2  23^1 |  0  0  0  1  1  1  2  2  2  0  0  0  1  1  1  2  2  2  0  0  0  1  1  1  2  2  23^0 |  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2=== |  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Решение становится достаточно очевидным:

генерируем каждое число в диапазоне 0 .. N^N - 1
раскладываем в N-ричную систему счисления
берем элемент на соответствующей позиции разложения

SELECT  dstFROM  -- исходный набор элементов  (VALUES('{A,B,C}'::varchar[])) data(src)  -- кэшируем размер набора, LATERAL array_length(src, 1) n  -- кэшируем границу интервала, LATERAL (SELECT (n ^ n)::bigint l) X  -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num  -- формируем разложение числа в N-ричной системе, LATERAL (    SELECT      array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n    FROM      generate_series(0, n - 1) pos  ) Y  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      array_agg(src[num_n[pos] + 1]) dst    FROM      generate_subscripts(num_n, 1) pos  ) Z;

Перестановки

Но в оригинальном наборе у нас каждый элемент был уникален, а в полученных нами комбинациях это правило не соблюдается. Исправим, получив все возможные перестановки. Для этого отфильтруем из num_n только те, где встречаются все цифры:

JOIN LATERAL(  SELECT    count(DISTINCT unnest) = n cond  FROM    unnest(num_n)) flt  ON cond

Полный вариант запроса

SELECT  dstFROM  -- исходный набор элементов  (VALUES('{A,B,C}'::varchar[])) data(src)  -- кэшируем размер набора, LATERAL array_length(src, 1) n  -- кэшируем границу интервала, LATERAL (SELECT (n ^ n)::bigint l) X  -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num  -- формируем разложение числа в N-ричной системе, LATERAL (    SELECT      array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n    FROM      generate_series(0, n - 1) pos  ) Y  -- фильтруем комбинации с неполным набором "цифр"JOIN LATERAL(    SELECT      count(DISTINCT unnest) = n cond    FROM      unnest(num_n)  ) flt    ON cond  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      array_agg(src[num_n[pos] + 1]) dst    FROM      generate_subscripts(num_n, 1) pos  ) Z;

Это дает нам все возможные перестановки исходного набора:

{A,B,C}{A,C,B}{B,A,C}{B,C,A}{C,A,B}{C,B,A}

Можно использовать и неэкспоненциальный алгоритм на основе тасований, работающий за O(N*N!), но его реализация явно выходит за рамки данной статьи.

Подмножества

Сделаем шаг чуть в сторону и научимся генерировать все подмножества исходного набора с сохранением порядка. То есть для нашего набора {A,B,C} должно получиться вот это:

{}{A}{B}{A,B}{C}{A,C}{B,C}{A,B,C}

В принципе, задача очень близка к первой решенной нами. Только вместо позиции двоичная цифра означает отсутствие или наличие соответствующего элемента в результирующем наборе:

2^2 |  0  0  0  0  1  1  1  12^1 |  0  0  1  1  0  0  1  12^0 |  0  1  0  1  0  1  0  1=== |  0  1  2  3  4  5  6  7

Поскольку двоичная арифметика представлена в компьютерах гораздо эффективнее, мы можем воспользоваться функциями работы с битовыми строками:

  -- кэшируем разложение числа в двоичной системе, LATERAL (SELECT num::bit(64) num_n) Y  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') dst    FROM      generate_series(1, n) i  ) Z

Полный вариант запроса

SELECT  dstFROM  -- исходный набор элементов  (VALUES('{A,B,C}'::varchar[])) data(src)  -- кэшируем размер набора, LATERAL array_length(src, 1) n  -- кэшируем границу интервала, LATERAL (SELECT (2 ^ n)::bigint l) X  -- генерируем все числа на интервале, LATERAL generate_series(0, l - 1) num  -- кэшируем разложение числа в двоичной системе, LATERAL (SELECT num::bit(64) num_n) Y  -- собираем элементы согласно "цифрам", LATERAL (    SELECT      coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') dst    FROM      generate_series(1, n) i  ) Z;

Иерархия без рекурсии!

Теперь, вооруженные всеми приведенными выше алгоритмами, попробуем найти решение нашей задачи сначала в общем виде, а затем разберем один из типичных частных случаев.

Пути-дороги

Для начала воспользуемся тем фактом, что в качестве элементов пути, который идентифицирует конкретную запись, можно использовать уникальные ключи промежуточных записей в нашем случае это id.

Но сортировать по такому пути, конечно, будет некорректно поэтому для дальнейшей сортировки превратим id записей в соответствующее значение data, которое использовали в первом варианте.

Дано: газовая плита, чайник. Задача: вскипятить воду.
Физик: Зажечь плиту, наполнить чайник водой и поставить на плиту, ждать.
Математик: Аналогично.

Дано: зажженная газовая плита, наполненный водой чайник. Задача: вскипятить воду.
Физик: Поставить чайник на плиту, ждать.
Математик: Выливаем воду из чайника на плиту. Огонь погас, чайник пуст, задача сведена к предыдущей.
Народный анекдот

Но как найти путь до каждого из элементов без рекурсии? Вот здесь нам и пригодятся алгоритмы выше.

Корректный путь от корня до конкретного элемента обладает следующими свойствами:

Правило #1: начинается и заканчивается нужными нам элементами
path[1] = root AND path[array_length(path, 1)] = id
Правило #2: предок каждого элемента, кроме корневого, так же присутствует в наборе
pid = ANY(path) OR pid = root
Правило #3: из всех таких наборов искомый самой маленькой длины
Иначе для id=3 наборы {1,2,3} и {1,2,3,4} окажутся равноподходящими, поскольку предок id=4 (pid=1) тоже присутствует.
Правило #4: предок каждого элемента стоит ровно в предыдущей позиции
pid = path[pos - 1]

Итак, намечаем план действий:

генерируем все подмножества элементов, исключая root и id, формируя тело пути по правилу #1
проверяем выполнение правила #2
выбираем, согласно правилу #3, самый короткий набор
генерируем все перестановки его элементов
проверяем выполнение правила #4
что осталось искомый путь

Полный вариант запроса, смотреть с осторожностью

Я вас предупредил [источник картинки]

WITH src(id, pid, data) AS (  VALUES    (1, NULL, 'A')  , (2, 1, 'AA')  , (3, 2, 'AAA')  , (4, 1, 'AB')  , (5, 2, 'AAB')  , (6, 3, 'AAAA')  , (7, 5, 'AABA')  , (8, 4, 'ABA')  , (9, 7, 'AABAA')  , (10, 2, 'AAC'))-- кэшируем ID корневого элемента, root AS (  SELECT    id  FROM    src  WHERE    pid IS NULL  LIMIT 1)-- формируем уже известные пути и предварительные наборы, preset AS (  SELECT    *  , CASE      -- для корневого элемента путь состоит только из него самого      WHEN pid IS NULL THEN ARRAY[id]      -- для ссылающегося на корневой - из пары      WHEN pid = (TABLE root) THEN ARRAY[pid, id]    END prepath  , CASE      WHEN pid IS NULL THEN NULL      WHEN pid = (TABLE root) THEN NULL      -- все ID, кроме корневого и собственного - EXCLUDE CURRENT ROW      ELSE array_agg(id) FILTER(WHERE pid IS NOT NULL) OVER(ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING EXCLUDE CURRENT ROW)    END preset  FROM    src)-- формируем "переборные" пути, prepath AS (  SELECT    id  , prepath  FROM    -- отбираем только элементы, чей путь еще не определили    (      SELECT        id      , pid      , preset src -- комбинируемый набор      FROM        preset      WHERE        prepath IS NULL    ) data    -- подмножества  , LATERAL (      SELECT        dst pathset      FROM        -- кэшируем размер набора        LATERAL array_length(src, 1) n        -- кэшируем границу интервала      , LATERAL (SELECT (2 ^ n)::bigint l) X        -- генерируем все числа на интервале      , LATERAL generate_series(1, l - 1) num -- тут можно с 1, поскольку пустой набор нас заведомо не интересует        -- кэшируем разложение числа в двоичной системе      , LATERAL (SELECT num::bit(64) num_n) Y        -- собираем элементы согласно "цифрам"      , LATERAL (          SELECT            coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') || data.id dst          FROM            generate_series(1, n) i        ) Z        -- проверяем наличие предка в наборе      , LATERAL (          SELECT            NULL          FROM            (              SELECT                (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid              FROM                generate_subscripts(dst, 1) i            ) T          HAVING            bool_and(_pid = (TABLE root) OR _pid = ANY(dst))        ) rule2      -- отбираем первый подходящий минимальной длины      ORDER BY        array_length(dst, 1) -- rule3      LIMIT 1    ) X    -- перестановки  , LATERAL (      SELECT        dst prepath      FROM        -- исходный набор элементов        (SELECT pathset) data(src)        -- кэшируем размер набора      , LATERAL array_length(src, 1) n        -- кэшируем границу интервала      , LATERAL (SELECT (n ^ n)::bigint l) X        -- генерируем все числа на интервале      , LATERAL generate_series(0, l - 1) num        -- формируем разложение числа в N-ричной системе      , LATERAL (          SELECT            array_agg((num % (n ^ (pos + 1))::bigint) / (n ^ pos)::bigint ORDER BY pos DESC) num_n          FROM            generate_series(0, n - 1) pos        ) Y        -- фильтруем комбинации с неполным набором "цифр"      JOIN LATERAL(          SELECT            count(DISTINCT unnest) = n cond          FROM            unnest(num_n)        ) flt          ON cond        -- собираем элементы согласно "цифрам"      , LATERAL (          SELECT            array_agg(src[num_n[pos] + 1]) dst          FROM            generate_subscripts(num_n, 1) pos        ) Z        -- проверяем наличие предка в предыдущей позиции      , LATERAL (          SELECT            NULL          FROM            (              SELECT                (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid              , i              FROM                generate_subscripts(dst, 1) i            ) T          HAVING            bool_and((i = 1 AND _pid = (TABLE root)) OR _pid = dst[i - 1])        ) rule4    ) Y)SELECT  src.*  -- восстанавливаем "путь" из прикладных ключей, (    SELECT      array_agg(data ORDER BY i)    FROM      coalesce(X.prepath, ARRAY[(TABLE root)] || Y.prepath) p -- помним о необходимости добавить "корень"    , LATERAL generate_subscripts(p, 1) i    , LATERAL (        SELECT          data        FROM          src        WHERE          id = p[i]        LIMIT 1      ) T  ) pathFROM  srcLEFT JOIN  preset X    USING(id)LEFT JOIN  prepath Y    USING(id)ORDER BY  path;

А попроще можно?..

Можно и попроще, если заранее известно, что порядок детей внутри одного родителя определяется некоторым сквозным ключом. Например, это может быть некоторый монотонно возрастающий timestamp сообщений в ветке форума или, как в нашем случае, первичный ключ типа serial (id).

В таком случае, мы уже точно знаем порядок следования идентификаторов записей в нужном нам пути он совпадает с общей сортировкой по этому ключу. И нам надо только выкинуть лишние id из списка всех предстоящих:

WITH src(id, pid, data) AS (  VALUES    (1, NULL, 'A')  , (2, 1, 'AA')  , (3, 2, 'AAA')  , (4, 1, 'AB')  , (5, 2, 'AAB')  , (6, 3, 'AAAA')  , (7, 5, 'AABA')  , (8, 4, 'ABA')  , (9, 7, 'AABAA')  , (10, 2, 'AAC'))-- кэшируем ID корневого элемента, root AS (  SELECT    id  FROM    src  WHERE    pid IS NULL  LIMIT 1)-- собираем все предстоящие id в массив для текущего, prepath AS (  SELECT    id  , pid  , array_agg(id) OVER(ORDER BY id /*!!! сортировка по тому самому ключу*/ ROWS UNBOUNDED PRECEDING EXCLUDE CURRENT ROW) src  FROM    src  WHERE    pid IS NOT NULL)-- находим пути, pre AS (  SELECT    id  , path  FROM    prepath    -- подмножества  , LATERAL (      SELECT        dst path      FROM        -- кэшируем размер набора        LATERAL array_length(src, 1) n        -- кэшируем границу интервала      , LATERAL (SELECT (2 ^ n)::bigint l) X        -- генерируем все числа на интервале      , LATERAL generate_series(0, l - 1) num        -- кэшируем разложение числа в двоичной системе      , LATERAL (SELECT num::bit(64) num_n) Y        -- собираем элементы согласно "цифрам"      , LATERAL (          SELECT            coalesce(array_agg(src[i]) FILTER(WHERE get_bit(num_n, 64 - i) = 1), '{}') || id dst          FROM            generate_series(1, n) i        ) Z        -- проверяем наличие предка в предыдущей позиции      , LATERAL (          SELECT            NULL          FROM            (              SELECT                (SELECT pid FROM src WHERE id = dst[i] LIMIT 1) _pid              , i              FROM                generate_subscripts(dst, 1) i            ) T          HAVING            bool_and((i = 1 AND _pid = (TABLE root)) OR (i > 1 AND _pid = dst[i - 1]))        ) rule4    ) X)SELECT  src.*  -- восстанавливаем "путь" из прикладных ключей, (    SELECT      array_agg(data ORDER BY i)    FROM      (        SELECT          CASE            -- для корневого элемента путь состоит только из него самого            WHEN pid IS NULL THEN ARRAY[id]            -- для ссылающегося на корневой - из пары            WHEN pid = (TABLE root) THEN ARRAY[pid, id]            ELSE ARRAY[(TABLE root)] || pre.path          END p -- помним о необходимости добавить "корень"      ) p    , LATERAL generate_subscripts(p, 1) i    , LATERAL (        SELECT          data        FROM          src        WHERE          id = p[i]        LIMIT 1      ) T  ) pathFROM  srcLEFT JOIN  pre    USING(id)ORDER BY  path;

Понятно, что производительность таких экспоненциальных решений не особо велика и применять в бою надо с большой осторожностью, но как гимнастика для ума вполне.

Подробнее..

Категории: Ненормальное программирование , Алгоритмы , Postgresql , Sql , Блог компании тензор , Sql tips and tricks , Рекурсия , Lateral , Комбинаторика , Перестановки , Подмножества , Битовые строки

Четырёхмерные таблицы в комбинаторике два странных способа посчитать сочетания

30.11.2020 12:14:44 |

Автор: admin

В комбинаторике сочетанием из $inline$n$inline$ по $inline$k$inline$ называют набор $inline$k$inline$ элементов, выбранных из $inline$n$inline$ элементов. В отличие от размещений, число сочетаний не учитывает последовательность размещения элементов, например: Сколько групп из 4 человек, можно получить, если всего в классе 20 человек?. Хотя удобные способы подсчёта давно известны, на ещё два стоит взглянуть.

Обозначается сочетание из $inline$n$inline$ по $inline$k$inline$ так: $inline$C_n^k$inline$. В литературе они чаще обозначаются $inline$ \binom nk$inline$ (но мне больше нравится первый вариант, чтобы не путать с матрицами).

В комбинаторике известны несколько способов подсчёта:

$$display$$C_n^k = \frac{n!}{k!(nk)!}$$display$$

$$display$$C_n^k=\frac{n(n1)(n2)(nk+1)}{k!}=\frac{\prod\limits_{i = nk+1}^n i}{k!}$$display$$

Где $inline$n!$inline$ эн факториал, произведение всех целых чисел от 1 до n (например: $inline$4!=1\cdot2\cdot3\cdot4=24$inline$), а $inline$0!$inline$ считается равным единице. Для вышесказанной задачи получается:

$$display$$C_{20}^4 = \frac{20!}{4!(204)!} = \frac{17\cdot18\cdot19\cdot20}{1\cdot2\cdot3\cdot4} = 4845$$display$$

Или так:

$$display$$C_{20}^4=\frac{20\cdot19\cdot18\cdot17}{4!}=\frac{116280}{24}=4845$$display$$

Вторая формула сочетаний выводится очень просто. Есть понятие числа размещений из $inline$n$inline$ по $inline$k$inline$, когда последовательность элементов имеет значение (то есть набор первый со вторым с пятым это не тоже самое, что первый с пятым со вторым), обозначается $inline$A_n^k$inline$.

Например все размещения из 3 по 2 выглядят так:

Первый элемент можно выбрать $inline$n$inline$ способами, второй $inline$(n1)$inline$ способами, последний $inline$(n(k1))$inline$ способами. Поэтому число размещений из $inline$n$inline$ по $inline$k$inline$ равно $inline$n(n1)(n2)(nk+1)$inline$, всего $inline$k$inline$ множителей.

Для подсчёта сочетаний получившиеся число нужно разделить на $inline$k!$inline$, поскольку есть $inline$k!$inline$ способов разместить $inline$k$inline$ элементов. В данном случае $inline$2!=2$inline$ способа (первый со вторым и второй с первым это одно и тоже сочетание).

Вспомним, как идет счёт в шашках по круговой системе (когда все играют со всеми). Для этого пишут обычную таблицу:

По горизонтали и вертикали идут номера игроков. Диагональ можно закрасить игрок не может играть сам с собой. Результат каждой партии записывают в таблицу два раза. Как сыграл второй с пятым и как сыграл пятый со вторым. Таким образом, количество партий в турнире и есть число сочетаний по 2.

Число вычеркнутых клеток равно $inline$n$inline$, а число всех клеток это $inline$n^2$inline$. Стало быть, число сочетаний по 2 можно посчитать так:

$$display$$C_n^2=\frac{n^2n}{2}$$display$$

Когда я это заметил, не сразу увидел что это равно $inline$\frac{n(n1)}{2!}$inline$. Решил сделать также для $inline$k=3$inline$, с трёхмерной таблицей:

На каждом её слое, кроме диагонали исключаются еще клетки. Например, клетка 161 исключается, потому что единица повторилась два раза.

Всего на каждом слое исключается $inline$n+2(n1)$inline$ клеток.

$$display$$n+2(n1)=3n2$$display$$

Итак, на каждом слое исключается $inline$3n2$inline$ клетки. Всего $inline$n$inline$ слоёв, поэтому общее число исключившихся ячеек:

$$display$$n(3n2)=3n^22n$$display$$

А вся таблица $inline$n^3$inline$. Значит, число сочетаний по 3 можно посчитать так:

$$display$$C_n^3=\frac{n^3(3n^22n)}{3!}=\frac{n^33n^2+2n}{3!}$$display$$

Как уже сказано выше, это и есть общая формула, в которой просто раскрыли скобки:

$$display$$C_n^3=\frac{n^33n^2+2n}{3!}=\frac{n(n1)(n2)}{3!}$$display$$

И тут возник вопрос, можно ли посчитать сочетания, так же представив их через таблицы, не используя факториалы вообще? К слову, в комбинаторике уже известна рекуррентная формула для числа сочетаний: $inline$C_n^k=C_{n1}^{k1}+C_{n1}^k$inline$ (число сочетаний по 0 равно 1, из любого количества элементов можно получить только одну группу в которой 0 элементов). Итак, я попробовал посмотреть, какие еще клетки исключаются в трёхмерной таблице, когда мы делим число оставшихся клеток на $inline$k!$inline$.

Клетки ниже диагонали дублируют клетки, которые выше диагонали вычеркнем их (ячейка 431 то же самое, что и 341). Для того, чтобы получить такое же количество клеток, просто поделим число размещений на 2. Цифрами в самой таблице я отметил, в какой строке встретилось данное сочетание. Например, сочетание 251 впервые встретилось здесь во второй строке, поэтому отмечено цифрой 2. Посмотрим на следующий слой:

Закрашенные клетки с цифрой означают, что данное сочетание уже встречалось. Например, комбинация 152 уже встречалась во второй строке (в виде 251), поэтому отмечена цифрой 2 в закрашенной клетке.

Итак, на втором слое исключается ещё $inline$(n2)$inline$ клетки (кроме тех, которые вычеркнуты из-за повторяющихся чисел в них, и тех, которые вычеркнуты ниже диагонали, из-за того что дублируют верхние). Перебрав так всю таблицу, я получил следующее. На третьем слое исключается ещё $inline$(n2)+(n3)$inline$ клеток:

На четвертом слое вычеркивается ещё $inline$(n2)+(n3)+(n4)$inline$ клеток:

На пятом $inline$(n2)+(n3)+(n4)+(n5)$inline$:

На шестом, по видимому, $inline$(n2)+(n3)+(n4)+(n5)+(nn)$inline$:

Получается, что для подсчёта сочетаний по 3, из числа $inline$\frac{n(n1)(n2)}{2}$inline$ нужно вычесть такую сумму:

$$display$$(n2)+((n2)+(n3))+((n2)+(n3)+(n4))+\\((n2)+(n3)+(n4)+(n5))+((n2)+(n3)+(n4)+(n5)+(nn))$$display$$

Это можно переписать в таком виде:

$$display$$\sum_{i=2}^n{\sum_{j=2}^i(nj)}$$display$$

Ещё можно переписать эту сумму так:

$$display$$5(n2)+4(n3)+3(n4)+2(n5)+(nn)=\\(n1)(n2)+(n2)(n3)+(n3)(n4)+(n4)(n5)+(n5)(nn)$$display$$

То есть:

$$display$$\sum_{i=2}^{n1}{(ni)(ni+1)}$$display$$

Значит, число сочетаний по 3 можно вычислить так:

$$display$$C_n^3=\frac{n(n1)(n2)}{2}\sum_{i=2}^n\sum_{j=2}^i(nj)=\frac{n(n1)(n2)}{2}\sum_{i=2}^{n1}{(ni)(ni+1)}$$display$$

Например число сочетаний из 8 по 3:

$$display$$C_8^3=\frac{8\cdot7\cdot6}{2}\sum_{i=2}^7{(n-i)(n-i+1)}=\\ 168(6\cdot7+5\cdot6+4\cdot5+3\cdot4+2\cdot3+1\cdot2)=\\ 168112=56$$display$$

На этом этапе вряд ли видна какая-либо зависимость, посмотрим то же самое с четырёхмерной таблицей. Изобразить её можно в виде нескольких трёхмерных (у трёхмерной таблицы слои двухмерные, у четырёхмерной трёхмерные). То есть, первый фрагмент четырёхмерной таблицы будет выглядеть так (первая ячейка будет иметь координаты 1111):

Весь первый двухмерный слой этого слоя исключается (на нем единица везде повторяется). В итоге на первом трёхмерном слое вычитается такая сумма:

$$display$$\begin{pmatrix}-\\0+\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+(nn)\end{pmatrix}$$display$$

Слагаемые в столбик записаны лишь для наглядности. Прочерком я отметил первый двухмерный слой, который итак исключился весь. Посмотрим следующий слой четырёхмерной таблицы:

Значит, на втором слое исключается такая сумма:

$$display$$\begin{pmatrix}(n3)+(n4)+(n5)+\\-\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}$$display$$

Посмотрим на третий:

На третьем исключается сумма:

$$display$$\begin{pmatrix}(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\-\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}$$display$$

Уже здесь видно, что общая сумма, которая будет вычитаться будет такой:

$$display$$\begin{pmatrix}-\\0+\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\(n3)+\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\(n3)+(n4)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)+\\(n3)+(n4)+(n5)\end{pmatrix}$$display$$

её можно переписать в таком виде:

4(n3)+3(n4)+2(n5)+1(nn)+

5(n3)+4(n4)+3(n5)+2(nn)+

5(n3)+5(n4)+4(n5)+3(nn)+

5(n3)+5(n4)+5(n5)+4(nn)+

5(n3)+5(n4)+5(n5)+5(nn)+

5(n3)+5(n4)+5(n5)+5(nn)

Получаем:

$$display$$29(n3)+27(n4)+24(n5)+20(nn)$$display$$

Видно, что коэффициенты перед скобками уменьшаются на число, которое возрастает на единицу. Поэтому можем записать:

$$display$$C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i=3}^{n1}{(ni)\left(30\sum_{j=1}^{i2}j\right)}$$display$$

Однако, получившаяся формула будет работать только для $inline$n=6$inline$, ведь для других $inline$n$inline$ коэффициенты будут другие. И, поскольку я не увидел зависимости от $inline$k$inline$ и здесь, решил посмотреть тоже самое для $inline$k=5$inline$, через пятимерную таблицу, весь её первый трёхмерный слой исключается, поскольку единица здесь повторяется во всех ячейках:

Для наглядности запишем это так:

$$display$$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}$$display$$

Смотрим дальше:

Тут, как видно, вычитается такая сумма:

$$display$$\begin{pmatrix}-\\-\\0\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

Третий:

Тут вычитается:

$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\(n4)+(n5)+\\-\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\-\\(n4)+(n5)\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

Затем, шестой фрагмент:

$$display$$\begin{pmatrix}-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\\-\end{pmatrix}=\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

На этом первый четырёхмерный слой заканчивается. Не сложно понять, что трёхмерный слой 21 будет дублировать слой 12, а слой 22 исключится весь, также как 11.

Перейдем к слою 23:

Здесь встретилось последнее сочетание из 6 по 5 56423 (клетки, которые встретились впервые отмечены белым, если кто забыл)). Напишем, какую в итоге надо вычесть сумму из $inline$\frac{n(n1)(n2)(n3)(n4)}{2}$inline$, чтобы получить число сочетаний из $inline$n$inline$ по 5. На первом четырёхмерном слое исключилось:

$$display$$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}+\begin{pmatrix}-\\-\\0+\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

На втором:

$$display$$\begin{pmatrix}-\\-\\-\\-\\-\\-\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\\\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}+\begin{pmatrix}-\\-\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)+\\(n4)+(n5)\end{pmatrix}$$display$$

Получается что каждая сумма в скобке обозначает исключившиеся ячейки на трёхмерных слоях. Всего $inline$n$inline$ четырёхмерных слоёв. Запишем это в виде суммы:

$$display$$\begin{aligned} &C_n^5=\frac{n(n1)(n2)(n3)(n4)}{2}\sum_{i_3=1}^n\sum_{i_2=1}^{nk+4}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=i_3=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_12+i_2+i_3, \ если \ i_12+i_2+i_3\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$

Получается, что последняя сумма суммирует исключившиеся ячейки на одномерных слоях, образуя исключения на двухмерных. Предпоследняя сумма складывает исключившиеся ячейки на двухмерных слоях, образуя исключившиеся ячейки на трёхмерных и т.д.

Индекс второй суммы берем до $inline$(nk+4)$inline$, поскольку она образует исключения на четырёхмерных слоях, суммируя вычеркнутые ячейки на трёхмерных, как мы могли видеть выше, у пятимерной таблицы на каждом четырёхмерном слое исключается один трёхмерный, то есть для $inline$n=6$inline$, на каждом четырёхмерном остается пять трёхмерных слоёв, $inline$65+4=5$inline$.

Для $inline$k=6$inline$, шестимерную таблицу можно не смотреть, достаточно выписать индексы её последних трёх измерений:

111 121 131 141 151
161

112 122 132 142 152 162

113 123 133 143 153 163

114 124 134 144 154 164

115 125 135 145 155 165

116 126 136 146 156 166



211

212

Опять же, вычеркнули мы те слои, где хоть одна цифра повторилась. Уже по первому пятимерному слою видно, что на пятимерных слоях для шестимерной таблицы останется на один четырёхмерный слой меньше. Количество оставшихся четырёхмерных слоёв равно $inline$(nk+5)$inline$. А трёхмерных слоёв на каждом четырёхмерном остается все также $inline$(nk+4)$inline$ (по 4 в данном случае: $inline$66+4$inline$). Запись в виде сумм получилась такой:

$$display$$\begin{aligned} &C_n^6=\frac{n(n1)(n2)(n3)(n4)(n5)}{2}\sum_{i_4=1}^n\sum_{i_3=1}^{nk+5}\sum_{i_2=1}^{nk+4}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=i_3=i_4=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_13+i_2+i_3+i_4, \ если \ i_13+i_2+i_3+i_4\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$

Запись для $inline$k=3$inline$ можно переписать так:

$$display$$\begin{aligned} &C_n^3=\frac{n(n1)(n2)}{2}\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=k1\\ &b=\left\{ \begin{aligned} &i_1, \ если \ i_1\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$

Для $inline$k=4$inline$ получается:

$$display$$\begin{aligned} &C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i_2=1}^n\sum_{i_1=a}^n\sum_{i_0=k1}^b(ni_0)\\ &a=\left\{ \begin{aligned} &k1, \ если \ i_2=1 \\ &k2, \ иначе \\ \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_11+i_2, \ если \ i_11+i_2\leqslant n1 \\ &n1, \ иначе \\ \end{aligned}\right. \end{aligned}$$display$$

Для $inline$k=5$inline$:

В общем виде запись для $inline$k\geqslant2$inline$ получается такой (сумма, которую мы вычитаем вычисляется рекуррентно):

$$display$$\begin{aligned} &C_n^k=\frac{\prod\limits_{i=nk+1}^ni}{2}c_k\\ &k_0=k\\ &c_k=\left\{\begin{aligned} &0, \ k=2 \\ &\sum_{i_3=a}^{n}\sum_{i_2=k1}^{b}(ni_2), \ k=3 \\ &\sum_{i_k=1}^{nk_0+k}c_{k1}, \ k\geqslant4 \end{aligned}\right. \\ &a=\left\{ \begin{aligned} &k_01, \ если \ i_4=i_5==i_k=1 \ или \ k_0=3 \\ &k_02, \ иначе \end{aligned}\right.\\ &b=\left\{ \begin{aligned} &i_3(k_03)+i_4+i_5++i_k, \ если\ i_3(k3)+i_4+i_5++i_k\leqslant n1 \ и \ k_0>3 \\ &i_3, \ если\ i_3\leqslant n1 \ и\ k_0=3 \\ &n1, \ иначе \end{aligned}\right. \end{aligned}$$display$$

Второй способ

Как я уже писал выше, число сочетаний по 3 можно записать через одну сумму:

$$display$$C_n^3=\frac{n(n1)(n2)}{2}\sum_{i=2}^n\sum_{j=2}^i(nj)=\frac{n(n1)(n2)}{2}\sum_{i=2}^{n1}{(ni)(ni+1)}$$display$$

А число сочетаний из 6 по 4 можно записать так:

$$display$$C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i=3}^{n1}{(ni)\left(30\sum_{j=1}^{i2}j\right)}$$display$$

Оказывается, что 30 во вторых скобках, это $inline$n(n1)$inline$ (логического обоснования этому я так и не смог найти).

$$display$$C_n^4=\frac{n(n1)(n2)(n3)}{2}\sum_{i=3}^{n1}{(ni)\left(n(n1)\sum_{j=1}^{i2}j\right)}$$display$$

Вторые скобки здесь представляют собой коэффициент, который умножается на $inline$(ni)$inline$. Для $inline$k=3$inline$ этот коэффициент просто уменьшается на 1 с каждым слагаемым первой суммы. Для $inline$4$inline$ число, на которое уменьшается этот коэффициент возрастает на 1. Затем я просто посчитал количество слагаемых $inline$(n4)$inline$, $inline$(n5)$inline$ и $inline$(nn)$inline$ в сумме которая вычитается для $inline$5$inline$:

$$display$$119(n4)+116(n5)+110(nn)$$display$$

Число, на которое увеличивается число, на которое уменьшается коэффициент, возрастает на 1. Этот коэффициент можно записать через две суммы:

$$display$$C_n^5=\frac{n(n1)(n2)(n3)(n4)}{2}\sum_{i=4}^{n1}{(ni)\left(n(n1)(n2)\sum_{j_1=1}^{i3}\sum_{j_0=1}^{j_1}j_0\right)}$$display$$

Зависимость ясна для $inline$k=6$inline$ эта формула будет выглядеть так:

$$display$$C_n^6=\frac{n(n1)(n2)(n3)(n4)(n5)}{2}\\\sum_{i=5}^{n1}{(ni)\left(n(n1)(n2)(n3)\sum_{j_2=1}^{i4}\sum_{j_1=1}^{j_2}\sum_{j_0=1}^{j_1}j_0\right)}$$display$$

А в общем виде (опять же, для $inline$k\geqslant2$inline$) получилось так:

$$display$$\begin{aligned} &C_n^k=\frac{\prod\limits_{i=nk+1}^ni}{2}c_k\\ &k_0=k\\ &c_k=\left\{ \begin{aligned} &0, \ k=2 \\ &\sum_{i=k1}^{n1}{(ni)\left(\prod_{j_k=nk+3}^nj_kd_k\right)}, \ если \ k\geqslant3 \\ \end{aligned}\right.\\ &d_k=\left\{ \begin{aligned} &i1, \ k=3 \\ &\sum_{j_4=1}^lj_4, \ k=4 \\ &\sum_{j_k=1}^ld_{k1}, \ если \ k>4 \\ &l=j_{k+1}, \ если \ k\neq k_0 \\ &l=ik_0+2, \ если \ k = k_0 \\ \end{aligned}\right.\\ \end{aligned}$$display$$

Под конец скажу, что метод действительно получился неоптимальный, хотя мне и было интересно найти его. Фактически, деление на факториал здесь просто заменяется вычитанием, но думаю лишним не будет.

Подробнее..

Категории: Алгоритмы , Математика , Комбинаторика , Перестановки , Сочетания , Размещения , Факториал

Жадный алгоритм, ветви и границы для расписания мерчендайзеров (кейс Хакатона на оптимизацию)

11.05.2021 14:17:08 |

Автор: admin

Это пилотная статья. Будем благодарны за обратную связь. Если тема вызовет интерес, мы возможно примем решение выложить на GitHub наши исходники (python) и входные data-setы.

В марте 2021 г. случилось мне поучаствовать в хакатоне с задачей на комбинаторику и оптимизацию. Команду решил собрать свежую, из одиночек, дрейфующих в пуле самого хака. Довольно быстро нашлись front и back, и втроем мы принялись старательно думать, как потратим деньги, когда выиграемJ Так как сам кейс показался нам по началу не сложным. Надо сказать, что в хаках я не так давно, но уже успел поучаствовать и в ЛЦТ(Лидеры Цифровой Трансформации), и в Цифровом Прорыве. В последнем даже удалось занять бронзу в финале. Роль всегда у меня была project+product+ppt (хотя опыт в программировании у меня также имеется). Не редко в хакатонских кейсах проблемы немного надуманы, решения этих проблем немного фееричны и не несут практического смысла, а побеждает профессиональная преза и поставленный питч. Так вот этот мартовский хакатон меня заинтересовал живостью и насущностью бизнес проблем, которые там решались. Опытные хакатонщики, читающие эти строки, поймут. Но полно про хакатоны и про то, какие они бывают, а то собьемся с курса.

В этам хаке преза и даже front мало интересовали кейсодержателей. Это был натуральный бизнес хакатон с абсолютно живыми дата сетами и с натуральной бизнес болью. Кстати на хакатоне ни одна из команд не предоставила решение. Вроде одни ребята "нарисовали" в своей презе оптимизацию в минус 1 агент, но демонстрацию на защите они не представили. Наша команда не стала исключением и заняла скромное третье место (всего до защиты дошло 5 команд). Теперь наконец к условию:

Есть 204 ТТ (торговые точки). Каждую из них нужно посетить минимум раз в неделю, а некоторые больше одного раза. Длительности посещения каждой ТТ известны и не изменяются внутри недели.

Также предоставлена матрица 204х204 с расстояниями между точками (см. Табл.1 ниже ). Матрица не симметричная, т.к. при составлении учитывались знаки ПДД (одностороннее движение и пр.). Видимо она была получена через API Яндекс.Карт по адресам ТТ. Требовалось найти оптимальное расписание для торговых агентов (мерчендайзеров), улучшив показатели текущего AS IS (оно тоже предоставлено). Важные ограничения: каждая ТТ должна быть закреплена за определенным мерчендайзером (торговым агентом). Другими словами, если торговый агент (далее агент) посещает Магнит на улице Ленина в понедельник, то этот же Магнит в другие дни недели должен посещать именно он. Время работы каждого агента не должно превышать 9,5 часов в день с учетом работы в ТТ и перемещению между ними.

	0	1	2	...	203
0	0	4031	4152	....	8853
1	4021	0	817	....	10196
2	4239	926	0	....	10306
....	....	....	....	0	10345
203	10071	10610	10289	10886	0

Таблица 1. Матрица расстояний между точками

Предоставленное расписании AS IS распределено на 14 агентов. И как вы уже догадались, решение должно было предложить альтернативное расписание, сократив по возможности количество агентов и их время в пути.

Спустя какое-то время после хакатона наш back(python) призвал на помощь коллегу с курсов по deep learning. Парни погуглили, поискали готовый алгоритм, почитали про метод отжига, муравьев, генетику и пришли еще раз к выводу, что подходящего метода и примеров кода именно для этой задачи, куда можно было бы взять и вставить матрицу расстояний, как входной параметр на просторах интернета - нет. Если кто знает где есть поделитесь, будем благодарны.

Позднее, и даже в параллель я сам начал изучать тему Задачи коммивояжера и эвристические методы, зарекомендовавшие себя для ее решения. Но ни хабр, ни youtube, ни Википедия не давали готового ответа именно для этого частного случая. Останавливаться все равно не хотелось. Наоборот, по мере продвижения вперед интерес подогревался. Мотивации добавило то, что классическая задача коммивояжера относится к NP полным задачам. Если решать задачу полным перебором (brutal force), то уже при 66 торговых точках нужно несколько миллиардов лет и компьютер размером с Землю. Согласитесь, мощь трансвычислительных задач завораживает! И действительно, для решения классической задачи TSP (Travelling salesman problem ) существуют различные эвристические методы, такие как Метод Имитации Отжига, Муравьиный алгоритм, Генетический метод и др. Оставалось решить один вопрос: как применить что-то из этой эвристики к сквозному недельному расписанию нескольких торговых агентов с ограничением по времени. Возможно толковый математик, который кожей чувствует физический смысл дифференцирования, логарифмов, пределов, силу числа e и т.д., справился бы с этой задачей. Но я не такой математик. Формулы счастья по-прежнему в интернете не находилось. Я даже изучил основы нейросетей, но когда я начинал проектировать свою нейросеть для решения - вырастала непреодолимая стена.

И все-таки решение родилось! Ну во-первых я обратился за помощью к своему коллеге, Черкасову Евгению @eny01. Он как раз недавно прошел курсы по data science и python, и рвался в бой, чтобы применить все приобретённые навыки. К слову сказать, бОльшую часть алгоритма именно он и разработал. Себе я взял часть, отвечающую за рекурсивный метод ветвей и границ. Но об этом позже. Вдвоем мы разработали следующий план.

Мы декомпозировали задачу до каждого агента. Набираем ТТ сначала для одного агента до предела по очереди для всех дней недели, затем для второго и т.д.;
Процесс набора ТТ происходит с помощью жадного алгоритма (метод ближайшего соседа);
В случае, когда набор подходит к пределу (9,5 часов) - применяем оптимизацию и считаем, что для данного агента в этот день недели оптимальное расписание составлено. Переходим к следующему дню;

Алгоритм набора расписания для каждого агента более подробно можно увидеть на блок-схеме ниже:

Теперь чуть подробнее про основные моменты:

Ближайшие сосед:

Первой точкой расписания дня недели мы берем точку, наиболее объемную по времени посещения и наиболее частую в неделе. Второй и последующими точками становятся ближайшие к уже отобранным точкам. Каждый раз при добавлении новой точки в расписание дня производится оптимизация по подбору наилучшей первой точки для получаемого кратчайшего пути в расписании. Мы попросту перебираем точки, подставляя каждую в качестве первой и перенабираем к ней при помощи того же жадного алгоритма отдельный массив. В итоге выбираем самый лучший вариант по минимальному пути для прохождения точек.

Важно следить за переполнением не только в том дне, в котором идет набор, но и параллельно приглядывать за остальными днями торгового представителя- последующими и предыдущими. Так как выбирая точку, скажем для четверга, мы можем переполнить ею пятницу или понедельник.

Когда в одном из дней достигается предел рабочего времени (>=9,5 ч.), система сбрасывает точку приведшую к переполнению и пробует добрать следующую ближайшую. Кстати, мы пробовали вставлять сюда вместо оптимизации "первой точки" и ближайшего соседа полный перебор с ветвями и границами. И результат, !внимание!, получался в итоге тот же. Но времени на перебор с ветвями и границами потребовалось гораздо больше. Около 3,5 часов против 5 минут для всех 204 точек. Таким образом полный перебор был абсолютно избыточен и неэффективен при частом применении. Вследствие чего в этом месте было решено от перебора с ветвями и границами отказаться, но добавить его в финальную оптимизацию составленного расписания.

2. Метод ветвей и границ:

Ну тут все относительно просто. Утвержденное недельное расписание мы прогоняем через полный перебор, используя метод ветвей и границ. Реализация этой функции потребовала применения рекурсии. Причем если сравнивать работу полного перебора через библиотеку itertools (python), то время на перебор 8 точек составило 21 сек, в то время как наша рекурсия с ветвями и границами отрабатывала за 0.4 с. Что не может не радовать! Цель применения ветвей и границ - оптимизация уже готовых расписаний. Привязка ТТ и агентов уже не меняется, но оптимизируется время в пути (решаем классическую задачу коммивояжера).

Результаты:

Описанным выше образом мы производим набор точек для второго агента, затем для третьего и т.д. В результате работы алгоритма нам удалось не только снизить количество агентов с 14 до 13, но и сократить суммарную траекторию перемещения между ТТ вдвое. Ниже представлены результаты, которых нам удалось добиться:

Параметр	До оптимизации	После оптимизации (с брутфорсом в наборе расписания)	Дельта	Относительное изменение, %
Число Мерчендайзеров	14	13	1	7,14%
Суммарная средняя траектория всех ТП, км	25,06	13,54	11,52	45,96%
Суммарная траектория всех маршрутов всех ТП, км	1729,342	839,69	889,65	51,44%
Средняя длительность рабочего дня для ТП	469,43	508,03	-38,6	-8,22%
Общая продолжительность работы всех ТП, час	539,85	524,97	14,88	2,76%

Время работы алгоритма для всех агентов на всех днях недели составило 8 минут на домашнем ПК.

И в качестве финального аккорда мы позволили себе выкрутить лимит с 9 часов 30 минут до 9 часов 38 минут. И получили сокращение до 12 агентов с небольшой погрешностью. Из 60 дневных расписаний 14 уходят в переработки от 1 до 8 минут (51 минута в сумме).

Ждем ваших комментариев, замечаний и предложений! Ответим на все вопросы. Пишите, как бы вы решали эту задачу. Особенно ценны для нас будут мнения практиков. Как математиков, так и data science'ов. Возможно кто-то предложит существующие библиотеки python для решения задачи. Мы, как я уже сказал, подходящих библиотек не нашли. Всем спасибо, что дочитали до конца!

Подробнее..

Категории: Алгоритмы , Python , Математика , Хакатоны , Клиентская оптимизация , Комбинаторика , Задача коммивояжера , Эвристика , Жадный алгоритм

Часть 2. Dракоши. Комбинаторика мира Dракош

24.08.2020 14:14:04 |

Автор: admin

В этой части я расскажу как рассчитывал вероятности обнаружения агентов в ячейках в зависимости от плотности заселения пространства Dракошами. А также о том, как можно наблюдать что Dракоши становятся более сознательными жильцами своей вселенной.
Кто такие Dракоши смотрите в первой части.

1. Зачем нам вероятности?
2. Постановка задачи
3. Подсчет способов расстановки агентов
4. Моделирование вероятностей методом Монте-Карло
5. Что получилось?

1. Зачем нам вероятности?

Как уследить за Dракошами

Прежде чем начать запускать моделирование надо бы понять, а как мы будем смотреть на мир Dракош? Ведь их будут тысячи, каждый будет заниматься своими делами, куда-то идти, что-то кушать и т.д.

Поэтому в самом начале пришлось задумался о параметрах, которые будут описывать текущее состояние моделируемой системы и показывать динамику происходящих в ней изменений. Получилось всего 24 величины, за которыми интересно проследить, помимо самого пространства с распределением агентов и пищи. Среди этих параметров есть вполне очевидные: количество агентов, количество пищи в пространстве, рождаемость и смертность Но о них более подробно будет рассказано в третей части. Сейчас же я больше остановлюсь на специальной группе параметров, которые позволят оценить степень осознанности действий агентов. Другими словами, отличить случайное поведение от осознанного.

Напомню, агенты могут совершать шесть разных действий: Pass, Step 1, Step 2, Eat, Attack, Sex. Для каждого из них можно рассчитывать долю агентов, которые его совершает в течении каждого такта времени: $f_{Pass}$ , $f_{Stp 1}$ , $f_{Stp 2}$ , $f_{Eat}$ , $f_{Att}$ , $f_{Sex}$ . Эти шесть параметров позволят понять, что делают Dракоши.

Все действия кроме Pass могут быть успешными или неуспешными, в зависимости от сложившейся ситуации в текущей и в соседних ячейках, а также от желаний соседа по занимаемой ячейке. Для отслеживания успешности используются четыре параметра: $L_{Stp}$ , $L_{Eat}$ , $L_{Att}$ , $L_{Sex}$ . Они показывают какая доля из совершенных действий была успешной. При этом оба действия Step 1 и Step 2 учитываются в одном параметре $L_{Stp}$ .

Индексы осознанности или зачем нам вероятности

На начальном этапе, когда нейронная сеть агентов еще не обучена, действия агентов будут носить случайный характер. А по мере эволюционного развития, под действием отбора, можно ожидать увеличения степени осознанности и следовательно повышения успешности действий. Но необходимо учесть, что успешность действий зависит так же и от окружающей обстановки.

Так успешность действий Step 1/2 определяется наличием в ячейке, которую агент выбрал для перемещения, свободного места (всего в ячейках есть по два места для агентов). И будет зависеть как от правильности выбора агента, так и от количества агентов в пространстве. Текущее количество агентов удобно отслеживать с помощью параметра $inline$ плотность агентов в пространстве, которая равна отношению количества агентов к количеству ячеек в пространстве. Когда агентов в пространстве мало, плотность близка к нулю и вероятность того, что в выбранной агентом ячейке будет свободное место близка к единице. Поэтому несмотря на наличие или отсутствие осознанности у агентов при низкой плотности агентов ( $inline$ ) успешность действий Step 1/2 будет высокой ( $L_{Stp}1$ ). По мере увеличения количества агентов вероятность обнаружить в выбранной случайно ячейке свободное место снижается вместе с успешностью $L_{Stp}$ , если только выбор ячейки для совершения шага не будет делаться осознано. Когда количество агентов будет близко к максимальной емкости пространства ( $inline$ ) вероятность найти свободное место станет близкой к нулю ( $L_{Stp}0$ ). Можно ввести параметр осознанности действий Step 1/2, который рассчитаем, как разность между текущей успешностью $L_{Stp}$ и вероятностью обнаружить свободное место в ячейке $inline$ :

$I_{Stp}=L_{Stp}-(1-W_2)$

Здесь $inline$ обозначает вероятность присутствия в выбранной ячейке двух агентов.
Таким же образом успешность действий Attack и Sex будет зависеть от вероятности ( $inline$ ) что агент обнаружит в ячейке, которую он занимает, еще одного агента.
Осознанность совершения атаки можно определить как превышение успешности $L_{Att}$ над вероятностью $inline$ :

$I_{Att}=L_{Att}-W_1$

А вот успешность $L_{Sex}$ зависит не только от вероятности найти партнера в ячейке, но и от вероятности что партнер тоже совершает в данный момент действие Sex. Но даже если партнер оказался сговорчивым, для успешного полового акта необходимо что бы в окружающем пространстве нашлось место для малыша. Поэтому вероятность случайного успеха будет произведением вероятностей трех независимых событий: $inline$ в ячейке есть потенциальный партнер, $f_{Sex}$ партнер так же совершает действие Sex, $inline$ в ячейке, которую выбрала мать для размещения ребенка, есть свободное место. Поэтому осознанность брачного поведения предлагаю определить таким образом:

$I_{Sex}=L_{Sex}-f_{Sex}W_1(1-W_2)$

2. Постановка задачи

Для вычисления введенных выше индексов осознанности необходимо научится рассчитывать две вероятности: $inline$ и $inline$ . Очевидно, что они зависят от плотности агентов в пространстве, а также от равномерности их распределения по пространству. Но для упрощения расчетов в дальнейшем будем предполагать равномерное распределения агентов по пространству. То есть будем считать, что эти вероятности не зависят от положения агента в пространстве.
Сформулируем задачу следующим образом.

Имеется пространство из $inline$ ячеек. В одной ячейке может находится не более $inline$ агентов. В этих ячейках располагаются $inline$ агентов ( $N\leqslant eS$ ). Необходимо определить вероятность того, что в выбранной ячейке с одним агентом будет находится еще один агент $inline$ . И вероятность того, что в выбранной ячейке будет $inline$ агентов $inline$ .

Для решения данной задачи я применил два подхода. Первый это расчет вероятности в классическом ее понимании, как отношение количества различных расстановок агентов, которые благоприятствуют искомому событию, к полному количеству расстановок агентов по ячейкам. Для вычислений воспользовался методом производящих функций.

Во втором подходе использовалось понятие частотной вероятности. Расчеты выполнялись с применением метода Монте-Карло. Вероятно, есть и другие способы вычислить эти вероятности, и возможно даже более простые. Буду благодарен за наводку на таковые.

3. Подсчет способов расстановки агентов

Вывод рекуррентной формулы

Предложенный ниже подход к расчету вероятностей позволяет решить поставленную задачу даже в более общей постановке, когда вместимости ячеек различны. Зададим вместимости ячеек пространства в виде последовательности $inline$ , где $inline$ номер ячейки (от $inline$ до $inline$ ). Для удобства вычислений перенумеруем ячейки таким образом что бы у выбранной для определения вероятностей ячейки был номер $inline$ .

Поставленную задачу можно свести к подсчёту количества способов расставить агентов по ячейкам пространства. Тогда вероятность $inline$ это отношение количества способов расстановки агентов, при которых в ячейку $inline$ попадает хотя бы один агент, к полному количеству способов расставить $inline$ агентов по $inline$ ячейкам пространства. Для мира Dракош вместимость всех ячеек равна двум. Но при расчете $inline$ вместимость ячейки $inline$ принимается $inline$ , т.к. изначально известно, что в этой ячейке уже есть один агент (см. определение вероятности $inline$ выше).

Вероятность $inline$ это отношение количества способов расстановки агентов, при которых в ячейку $inline$ попадает предельное для этой ячейки количество агентов $inline$ , к полному количеству способов расставить $inline$ агентов по $inline$ ячейкам пространства.

Обозначим через $inline$ количество способов расставить $inline$ агентов по ячейкам с $inline$ по первую. Так же для вычислений нам понадобится знать количество свободных мест в ячейках с $inline$ по первую $\sigma_i$ :

$\sigma_i=\sum_{k=i}^{1}e_k$

Рассмотрим процесс, при котором мы последовательно перебираем все ячейки пространства (от $inline$ до $inline$ ) и на каждом шаге помещаем в очередную ячейку $inline$ некоторое количество агентов $inline$ , пока не расставим все $inline$ неразмещенных агентов или не исчерпаем все ячейки. В ячейку $inline$ можно поместить от $inline$ до $inline$ агентов. Но если агентов осталось меньше максимальной вместимости ячейки, то в текущую ячейку можем поместить не более $inline$ агентов. Таким образом $j=0..\min(n,e_i)$ .

Количество способов заполнить ячейку агентами это сочетание без повторений из $inline$ по $inline$ :

$C_n^j=\frac{n!}{j!(n-j)!}$

Поместив $inline$ агентов в ячейку $inline$ , останется еще $inline$ агентов для расстановки в ячейки с $inline$ по $inline$ . И каждому $inline$ будет соответствовать $F_{i-1}(n-j)$ способов расстановки оставшихся агентов. Произведение $C_n^jF_{i-1}(n-j)$ даёт нам количество способов разместить $inline$ агентов в ячейке $inline$ и $inline$ агентов по остальным ячейкам. Суммируя по всем допустимым значениям $inline$ , получим искомое количество способов расстановки:

$F_i(n)=\sum_{j=0}^{\min(n,e_i)}{C_n^jF_{i-1}(n-j)}$

Для того что бы воспользоваться полученной рекуррентной формулой необходимо задать граничные условия:

Если $inline$ , т.е. у нас не осталось агентов которых можно поместить в ячейку, тогда у нас есть всего один способ выполнить расстановку агентов никого не помещать в ячейку:

$display$
Для последней ячейки $inline$ так же есть только один способ расставить агентов оставить все $inline$ агентов в ней, но только если им хватит места:

$F_1(n)=1,\qquad n\leq\sigma_1$
Если места не хватает для размещения $inline$ агентов в ячейках с $inline$ по $inline$ , то способов заполнить ячейку нету:

$F_i(n)=0,\qquad n>\sigma_i$

Теперь можем записать выражения для вероятности $inline$ :

$W_1=\frac{F'_S(N-1)}{F_S(N-1)}$

где $inline$ это количество способов расстановки агентов, при которых в ячейку $inline$ попадает один и более агентов:

$F'_S(N-1)=\sum_{j=1}^{\min(N-1,e_S)}{C_{N-1}^jF_{S-1}(N-1-j)}$

Обратите внимание, здесь начинаем суммировать с единицы, т.к. нас интересуют те расстановки, при которых в ячейку $inline$ попадает хотя бы один агент.

Выражения для вероятности $inline$ :

$W_2=\frac{F''_S(N)}{F_S(N)}$

где $inline$ это количество способов расстановки агентов, при которых в ячейку $inline$ попадает предельное для этой ячейки количество агентов:

$F''_S(N)=C_N^{e_S}F_{S-1}(N-e_S)$

Пример вычисления вероятностей для S=5

Рассмотрим пример вычисления количества способов расстановки агентов по пяти ячейкам ( $inline$ ), вместимость которых равна двум ( $inline$ ).

Результаты вычислений сведены в таблицу:

Упрощение и переход приведенному виду

Количество расстановок очень быстро растет и уже для $inline$ чисел двойной точности не хватит. Даже если воспользоваться пакетами символьных вычислений с произвольной точностью (например, Symbolic Math Toolbox и Variable-precision arithmetic в среде MatLab) останется проблема переполнения стека вызовов рекуррентной функции при больших размерах пространства. Поэтому полученные выше выражения необходимо преобразовать. А еще лучше вывести формулу, с помощью которой сразу вычисляется $inline$ без необходимости считать предыдущие значения.

Первое что можно сделать это вынести из-под знака суммы $inline$ .

Но прежде введем обозначение приведенного количества расстановок $inline$ агентов по $inline$ ячейкам, которое в $inline$ раз меньше:

$f_{i,n}=\sum_{j=0}^{\min(n,e_i)}{\frac{1}{j!(n-j)!}F_{i-1}(n-j)}=\sum_{j=0}^{\min(n,e_i)}{\frac{1}{j!}f_{i-1,n-j}}$

Маленький алгебраический трюк

$F_i(n)=\sum_{j=0}^{\min(n,e_i)}{\frac{n!}{j!(n-j)!}F_{i-1}(n-j)}=n!\sum_{j=0}^{\min(n,e_i)}{\frac{1}{j!(n-j)!}F_{i-1}(n-j)}$

Полное количество способов расстановки теперь будет:

$F_i(n)=n!f_{i,n}$

Аналогично для $F_{i-1}(n-j)=(n-j)!f_{i-1,n-j}$ , и после подстановки в $f_{i,n}$ получим:

$f_{i,n}=\sum_{j=0}^{\min(n,e_i)}{\frac{1}{j!}f_{i-1,n-j}}$

И можем сократить выражения для вероятностей на факториал:

$W_1=\frac{F'_S(N-1)}{F_S(N-1)}=\frac{(N-1)!f'_{S,N-1}}{(N-1)!f_{S,N-1}}=\frac{f'_{S,N-1}}{f_{S,N-1}} \\ W_2=\frac{F''_S(N)}{F_S(N)}=\frac{N!f''_{S,N}}{N!f_{S,N}}=\frac{f''_{S,N}}{f_{S,N}}$

Где

$f'_{i,n}=\sum_{j=1}^{\min(n,e_i)}{\frac{1}{j!}f_{i-1,n-j}} \\ f''_{i,n}=\frac{1}{e_i!}f_{i-1,n-e_i}$

После введения новых обозначения требуется переписать выражения для граничных условий. Для дальнейших выкладок удобнее представить граничные условия в следующем виде:

$f_{0,0}=1$ , при $inline$ , $inline$ ;
$f_{i,0}=f_{i-1,0}$ , при $inline$ , $inline$ ;
$f_{i,1}=f_{i-1,1}+f_{i-1,0}$ , при $inline$ , $inline$ ;
$f_{i,n}=0$ , при $n>\sigma_i$ .

Полученные выражения для приведенных количеств расстановок смотрятся поинтереснее т.к. коэффициенты в рекуррентной формуле постоянны и не растут со скоростью факториала как в формулах выше. Но все равно быстро и надежно вычислить вероятности при размерах пространства порядка 10⁴ не очень получится.

Пример вычисления вероятностей для S = 5 в приведенном виде

Самое время проверить что ничего не испорчено нашими упрощениями.

Следующим шагом предлагаю избавится аж от трех видов выражений для приведенного количества расстановок: $f_{i,n}$ , $f_{i,n}$ , $f_{i,n}$ . Для этого достаточно выразить вероятности через $f_{S-1,n}$ . Тут нам придется вспомнить что вместимость ячеек в мире Dракош везде $inline$ , кроме выбранной ячейки в которой одно место уже занято и поэтому $inline$ . Дальнейшие решение поставленной задачи в общей постановке (когда вместимость ячеек произвольна) существенно усложнит выкладки в и так затянувшемся погружении в мир комбинаторики.

Избавление

Распишем $f_{S,N-1}$ , $f_{S,N}$ , $f_{S,N-1}$ , $f_{S,N}$ согласно их основным формулам и подставим в выражения для $inline$ и $inline$ :

$W_1=\frac{F'_S(N-1)}{F_S(N-1)}=\frac{f'_{S,N-1}}{f_{S,N-1}}=\frac{f_{S-1,N-2}}{f_{S-1,N-1}+f_{S-1,N-2}}=\frac{1}{1+\frac{f_{S-1,N-1}}{f_{S-1,N-2}}}$

$W_2=\frac{F''_S(N)}{F_S(N)}=\frac{f''_{S,N}}{f_{S,N}}=\frac{\frac{1}{2}f_{S-1,N-2}}{f_{S-1,N}+f_{S-1,N-1}+\frac{1}{2}f_{S-1,N-2}}=\frac{1}{1+2\frac{f_{S-1,N}}{f_{S-1,N-2}}+2\frac{f_{S-1,N-1}}{f_{S-1,N-2}}}$

Готовые выражения для вероятностей теперь зависят только от приведенного количества способов расстановки агентов одного вида $f_{i,n}$ :

$W_1=\frac{1}{1+\frac{f_{S-1,N-1}}{f_{S-1,N-2}}}$

$W_2=\frac{1}{1+2\frac{f_{S-1,N}}{f_{S-1,N-2}}+2\frac{f_{S-1,N-1}}{f_{S-1,N-2}}}$

Построение производящей функции

Осталось научится рассчитывать элементы последовательности $f_{i,n}$ для произвольно больших значений $inline$ и $inline$ . Порывшись в учебниках по комбинаторике я нашёл довольно популярный и мощный метод для решения всяческих комбинаторных вопросов метод производящих функций.

Хорошим пособием для начинающих комбинаторов по производящим функциям можно назвать учебник Ландо С.К. [3]. Еще один ресурс типа справочник по производящим функциям. И еще вот этот пост на хабре. Но наиболее полезными для меня были видео лекции Игоря Клейна по производящим функциям, выложенные тут.

Но в перечисленных ресурсах в основном речь ведется о производящих функциях для одномерных последовательностей, с одним индексом. А наша последовательность двумерная, с двумя индексами. Производящие функции от двух переменных лишь упоминаются. Поэтому пришлось рискнуть и попробовать вывести производящую функцию для нашей двумерной последовательности на основе одномерных примеров.

Пару слов о том, что такое производящая функция последовательности

Это формальная замена последовательности $inline$ , $inline$ , $inline$ , $inline$ , степенным рядом:

$\langle a_0,a_1,a_2,a_3,...\rangle \Leftrightarrow G(x)=\sum_{i=0}^\infty{a_ix^i=a_0+a_1x+a_2x^2+a_3x^3+\dots}$

Идея метода в том, что получив каким-то из способов выражение для производящей функции $inline$ можно затем разложить его в степенной ряд $\sum_{i=0}^\infty{a_ix^i}$ и тем самым, например, получить выражение для общего члена последовательности $inline$ в замкнутом виде (не требующем вычисления предыдущих членов последовательности). Это как раз то, что нам требуется.

Суммируя то, что имеется на данный момент по нашей последовательности приведенных количеств расстановок запишем рекуррентную формулу для $f_{i,n}$ совместно с граничными условиями.

$$display$$\left\{ \begin{array}{} f_{0,0}=1 \\ f_{i,0}=f_{i-1,0} \\ f_{i,1}=f_{i-1,1}+f_{i-1,0} \\ f_{i,n}=f_{i-1,n}+f_{i-1,n-1}+\frac{1}{2}f_{i-1,n-2}, \text{ при } n\geqslant 2 \\ f_{i,n}=0, \text{ при } n>2i \end{array} \right.$$display$$

Наша последовательность $f_{i,n}$ зависит от двух индексов: $inline$ количество ячеек в пространстве для расстановки агентов, $i=0\dots S$ ; $inline$ количество агентов для расстановки в ячейках, $n=0\dots N$ . Поэтому и производящая функция ей нужна двумерная $\mathscr{F}(x,y)$ .

$\mathscr{F}(x,y)={ f_{0,0}x^0y^0+f_{0,1}x^0y^1+f_{0,2}x^0y^2+f_{0,3}x^0y^3+f_{0,4}x^0y^4+\dotsb \\ f_{1,0}x^1y^0+f_{1,1}x^1y^1+f_{1,2}x^1y^2+f_{1,3}x^1y^3+f_{1,4}x^1y^4+\dotsb \\ f_{2,0}x^2y^0+f_{2,1}x^2y^1+f_{2,2}x^2y^2+f_{2,3}x^2y^3+f_{2,4}x^2y^4+\dotsb \\ \ldots }$

Используя специальный технический примем можно из рекуррентного выражения для элементов последовательности получить выражение для производящей функции. У меня получилось вот это:

$\mathscr{F}(x,y)=\frac{1}{1-x \left(1+y+\frac{1}{2}y^2 \right)}$

Тот самый технический прием

Суть приема в том, чтобы выписать первые элементы последовательности в столбик согласно рекуррентной формуле и умножить каждую строку на соответствующий множитель $inline$ .

$$display$$\begin{array}{cccccccc} i=0: \qquad & x^0y^0 \times \qquad & f_{0,0}= & \color{Blue}{1} \\ i=1: \qquad & x^1y^0 \times \qquad & f_{1,0}= & \color{Blue}{f_{0,0}} \\ \qquad & x^1y^1 \times \qquad & f_{1,1}= & \color{Blue}{0} & + & \color{Green}{f_{0,0}} \\ \qquad & x^1y^2 \times \qquad & f_{1,2}= & \color{Blue}{0} & + & \color{Green}{0} & + & \color{Red}{\frac{1}{2}f_{0,0}}\\ i=2: \qquad & x^2y^0 \times \qquad & f_{2,0}= & \color{Blue}{f_{1,0}} \\ \qquad & x^2y^1 \times \qquad & f_{2,1}= & \color{Blue}{f_{1,1}} & + & \color{Green}{f_{1,0}} \\ \qquad & x^2y^2 \times \qquad & f_{2,2}= & \color{Blue}{f_{1,2}} & + & \color{Green}{f_{1,1}} & + & \color{Red}{\frac{1}{2}f_{1,0}}\\ \qquad & x^2y^3 \times \qquad & f_{2,3}= & \color{Blue}{0} & + & \color{Green}{f_{1,2}} & + & \color{Red}{\frac{1}{2}f_{1,1}}\\ \qquad & x^2y^4 \times \qquad & f_{2,4}= & \color{Blue}{0} & + & \color{Green}{0} & + & \color{Red}{\frac{1}{2}f_{1,2}}\\ i=3: \qquad & x^3y^0 \times \qquad & f_{3,0}= & \color{Blue}{f_{2,0}} \\ \qquad & x^3y^1 \times \qquad & f_{3,1}= & \color{Blue}{f_{2,1}} & + & \color{Green}{f_{2,0}} \\ \qquad & x^3y^2 \times \qquad & f_{3,2}= & \color{Blue}{f_{2,2}} & + & \color{Green}{f_{2,1}} & + & \color{Red}{\frac{1}{2}f_{2,0}}\\ \qquad & x^3y^3 \times \qquad & f_{3,3}= & \color{Blue}{f_{2,3}} & + & \color{Green}{f_{2,2}} & + & \color{Red}{\frac{1}{2}f_{2,1}}\\ \qquad & x^3y^4 \times \qquad & f_{3,4}= & \color{Blue}{f_{2,4}} & + & \color{Green}{f_{2,3}} & + & \color{Red}{\frac{1}{2}f_{2,2}}\\ \qquad & x^3y^5 \times \qquad & f_{3,5}= & \color{Blue}{0} & + & \color{Green}{f_{2,4}} & + & \color{Red}{\frac{1}{2}f_{2,3}}\\ \qquad & x^3y^6 \times \qquad & f_{3,6}= & \color{Blue}{0} & + & \color{Green}{0} & + & \color{Red}{\frac{1}{2}f_{2,4}}\\ \ldots \qquad & \ldots \qquad & \ldots \end{array}$$display$$

Просуммируем полученные выражения в столбик следующим образом. Отдельно суммируем левый от равно столбец и получим собственно производящую функцию $\mathscr{F}(x,y)$

Суммируя синие слагаемые справа от равно, получим:

$\color{Blue}{1+f_{0,0}x^1y^0+f_{1,0}x^2y^0+f_{1,1}x^2y^1+f_{1,2}x^2y^2+\cdots}$

Замете, что начиная со второго слагаемого можно вынести за скобки множитель $inline$ и там останется наша производящая функция:

$\color{Blue}{1+x \left( f_{0,0}x^0y^0+f_{1,0}x^1y^0+f_{1,1}x^1y^1+f_{1,2}x^1y^2+\cdots \right) = 1 + x \mathscr{F}(x,y)}$

Суммируя зеленые слагаемые, получим:

$\color{Green}{ \begin{array}{c} f_{0,0}x^1y^1+f_{1,0}x^2y^1+f_{1,1}x^2y^2+f_{1,2}x^2y^3+\cdots = \\ = xy \left( f_{0,0}x^0y^0+f_{1,0}x^1y^0+f_{1,1}x^1y^1+f_{1,2}x^1y^2+\cdots \right) = \\ = xy \mathscr{F}(x,y) \end{array} }$

Суммируя красные слагаемые, получим:

$\color{Red}{ \begin{array}{c} \frac{1}{2}f_{0,0}x^1y^2+\frac{1}{2}f_{1,0}x^2y^2+\frac{1}{2}f_{1,1}x^2y^3+\frac{1}{2}f_{1,2}x^2y^4+\cdots = \\ = \frac{1}{2}xy^2 \left( f_{0,0}x^0y^0+f_{1,0}x^1y^0+f_{1,1}x^1y^1+f_{1,2}x^1y^2+\cdots \right) = \\ = \frac{1}{2}xy^2 \mathscr{F}(x,y) \end{array} }$

После выполненных суммирований получим уравнение относительно искомой функции:

$$display$$\mathscr{F}(x,y)=\color{Blue}{1+x\mathscr{F}(x,y)}+\color{Green}{xy\mathscr{F}(x,y)}+\color{Red}{\frac{1}{2}xy^2\mathscr{F}(x,y)}$$display$$

Решая которое относительно $\mathscr{F}(x,y)$ получим выражение для производящей функции.

Теперь дело за малым, разложить полученную производящую функцию в ряд по степеням $inline$ . Собственно, произвести элементы последовательности:

$\mathscr{F}(x,y)=\sum_{i=0}^{\infty}{\left( 1+y+\frac{1}{2}y^2 \right)^i x^i}=\sum_{i=0}^{\infty}{\sum_{k=0}^i{\sum_{m=0}^k{\frac{1}{2^m}C_i^kC_k^m y^{k+m}}}}$

Процесс разложения в ряд

Для начала обозначим:

$\begin{array}{c} Y=1+y+\frac{1}{2}y^2=1+z \\ z=y \left( 1+\frac{1}{2}y \right)=y(1+p) \\ p=\frac{1}{2}y \end{array}$

С учетом этих обозначений производящая функция запишется:

$\mathscr{F}(x,y)=\frac{1}{1-Yx}$

Вот тут лежит аж семь объяснений того почему $\frac{1}{1-x}$ это степенной ряд $\sum_{i=0}^{\infty}x^i=1+x+x^2+x^3+\cdots$ . С учетом этого наша функция раскладывается в ряд по степеням $inline$ следующим образом:

$\mathscr{F}(x,y)=\sum_{i=0}^{\infty}Y^ix^i$

Теперь разберемся с $inline$ .

$display$

А это уже бином Ньютона:

$(1+z)^i=\sum_{k=0}^iC_i^kz^k$

Аналогично для $inline$ :

$z^k=y^k(1+p)^k=y^k\sum_{m=0}^k{C_k^mp^m}=y^k\sum_{m=0}^k{\frac{1}{2^m}C_k^my^m}=\sum_{m=0}^k{\frac{1}{2^m}C_k^my^{k+m}}$

Осталось подставить полученное выражение для $inline$ в производящую функцию:

$\mathscr{F}(x,y)=\sum_{i=0}^{\infty}Y^ix^i=\sum_{i=0}^{\infty}{\sum_{k=0}^i{\sum_{m=0}^k{\frac{1}{2^m}C_i^kC_k^m y^{k+m}}}}$

Теперь все что нам нужно это выделить коэффициент при $inline$ , это и будет искомое выражение для элемента последовательности $f_{i,n}$ :

$[x^iy^n]\mathscr{F}(x,y)=f_{i,n}$

Для этого необходимо сгруппировать все слагаемые, у которых степень $inline$ $inline$ равна $inline$ . Пределы суммирования при этом будут следующими: при $inline$ , $inline$ ; при $inline$ , $k = \frac{n}{2}$ .

В результате получим два выражения, одно для чётного $inline$ :

$\eta=\frac{n}{2},\qquad f_{i,n}=\sum_{k=\eta}^{2\eta}{\frac{1}{2^{2\eta-k}}C_i^kC_k^{2\eta-k}}$

и одно для нечетного $inline$ :

$\eta=\frac{n+1}{2},\qquad f_{i,n}=\sum_{k=\eta}^{2\eta-1}{\frac{1}{2^{2\eta-k-1}}C_i^kC_k^{2\eta-k-1}}$

Полученные выражения уже можно попробовать вычислить, но так как биноминальные коэффициенты, которые входят в них, всё же растут довольно быстро, для расчетов необходимо воспользовался инструментами символьных вычислений MatLab.

Пример реализации в MatLab

Вычисление $f_{i,n}$ .

function out = f(i,n)%% Символьное вычисление f(i,n)nu = ceil(n/2); % нижний предел суммированияsyms kif mod(n,2)==0 % если n чётное    syms S(t,h)     S(t,h) = symsum(nchoosek(t,k)*nchoosek(k,2*h-k)/2^(2*h-k), k, h, 2*h);    out = S(i,nu);else % если n нечётное    syms S(t,h)    S(t,h) = symsum(nchoosek(t,k)*nchoosek(k,2*h-k-1)/2^(2*h-k-1), k, h, 2*h-1);        out = S(i,nu);end

Вычисление $inline$ .

function out = W1sym(ii,N)%% Символьное вычисление вероятности обнаружить второго агента в ячейке пространстваout = 1/(1 + f(ii-1,N-1)/f(ii-1,N-2));

Вычисление $inline$ .

function out = W2sym(ii,N)%% Символьное вычисление вероятности обнаружить второго агента в ячейке пространстваout = 1/(1 + 2*f(ii-1,N)/f(ii-1,N-2) + 2*f(ii-1,N-1)/f(ii-1,N-2));

4. Моделирование вероятностей методом Монте-Карло

Метод Монте-Карло или метод статистических испытаний это большая группа численных методов решения математических задач (причем не только вероятностной природы) при помощи моделирования случайных величин. Один из вариантов метода Монте-Карло предполагает что смоделированная случайная величина с известным распределением (зачастую равномерно распределённая на отрезке 0..1) используется для установления статистических характеристик других случайных величин или для приближённой оценки некоторого значения $inline$ . Во втором случае придумывается некоторая случайная величина $\xi$ , такая что ее мат. ожидание равно искомой величине $inline$ . Тогда рассчитав $inline$ независимых значений случайной величины $\xi_1$ , $\xi_2$ , , $\xi_N$ определяют величину $inline$ как среднее арифметическое выборки $\xi_1$ , , $\xi_N$ [2].

Для установления статистических характеристик случайных величин, например, для определения вероятности $inline$ случайного события $inline$ , можно реализовать другой вариант метода Монте-Карло. Когда проводится моделирование такой случайной величины $\delta_i$ , которая равна $inline$ при реализации случайного события $inline$ на испытании $inline$ , или равна $inline$ если события $inline$ не наступило. При проведении $inline$ независимых испытаний частота события $inline$ , равная $\frac{1}{N}\sum_{i=1}^N\delta_i$ , стремится к искомой вероятности $inline$ по мере роста количества испытаний $inline$ [3]. Если для моделирования случайной величины $\delta_i$ в модели полностью или частично воспроизводится изучаемый естественный процесс, то такой подход так же называют имитационным моделированием.

На сегодня метод имитационного моделирования развился в самостоятельное направление методов исследований. Но для решения поставленной в разделе 2 задачи использовался подход, который с одной стороны является примером реализации методов Монтер-Карло, с другой это пример имитационного моделирования, т.к. использовался естественный процесс изменения положения агентов в пространстве.

Обзор алгоритма

В рамках метода Монте-Карло поставленная в разделе 2 задача сводится к оценке частоты реализации соответствующих событий. Так вероятность $inline$ это частота обнаружения агентами соседей по ячейке. А вероятность $inline$ это частота обнаружения ячеек с двумя агентами.

Будем рассматривать процесс заполнения $inline$ ячеек $inline$ агентами, так что в одной ячейке может быть не более $inline$ агентов. На каждом шаге будем пересаживать агентов в новые ячейки, и если при попытке пересадить агента окажется что в выбранной ячейке нет свободного места, то оставляем агента на старом месте.

После каждого этапа пересаживаний будем подсчитывать количество $inline$ полностью заполненных ячеек (с двумя агентами).

$W_1=\frac{2C_2}{N}$

Частота обнаружения ячеек с двумя агентами (вероятность $inline$ ) это просто:

$W_2=\frac{C_2}{S}$

Можно предложить несколько вариантов реализации этапа пересаживания:

Scenario 1 почти полная имитация: для пересаживания случайно выбираются 50% агентов и каждый из них пересаживается в одну из 18 соседних клеток выбранных случайно;
Scenario 2 пересаживаются все агенты и каждый из них пересаживается в одну из 18 соседних клеток выбранную случайно;
Scenario 3 для пересаживания случайно выбираются 50% агентов и каждый из них пересаживается в случайную ячейку пространства;
Scenario 4 пересаживаются все агенты и каждый из них пересаживается в случайную ячейку пространства;

Scenario 1 назван почти полной имитацией процессов в настоящем мире Dракош, так как доля агентов совершающих действия Step 1/2 различна для каждого такта времени и может иметь любое значение а не только 50%. Ниже мы посмотрим, как результаты вычислений зависят от сценария пересаживания агентов.

Процесс начинаем со случайной расстановки агентов по ячейкам. Затем в цикле $inline$ раз повторяются два этапа:

Пересаживаем агентов согласно выбранного сценария;
Определяем количество заполненных ячеек $inline$ и соответствующие значения $inline$ и $inline$ .

Возникает вопрос: сколько же раз необходимо повторить цикл? С ростом $inline$ неопределенность вычислений убывает пропорционально $1/\sqrt{n}$ . Т.е. для увеличения точности в 10 раз необходимо увеличить количество испытаний в 100 раз. Метод Монте-Карло похож на натурные физические эксперименты в том плане что точность результатов можно определить только после получения результата эксперимента. Точнее случайную составляющую неопределенности. И так же как в натурном эксперименте ею можно управлять изменяя количество измерений.

На графике ниже показана зависимость вероятности $inline$ для $inline$ и $inline$ ( $inline$ ) от количества испытаний. Для каждой точки показаны планки неопределенности, которая рассчитывалась на основе стандартного отклонения полученных выборок и коэффициента охвата $inline$ (надежность 99.7%).

$u_{W_1}=k\sqrt{\frac{\sum_{i=1}^n{(w_{1_i}-\overline{w_1}})^2}{n(n-1)}}$

Горизонтальной чертой отмечено точное значение, рассчитанное способом, описанным в разделе 3.

По результатам расчетов получены следующие значения неопределенности (надежность 99.7%):

Для $inline$ неопределенность составила 0.0014 (0.24%);
Для $inline$ 0.00047 (0.080%);
Для $inline$ 0.00015 (0.025%);
Для $inline$ 0.000066 (0.011%);

Т.к. время вычислений растет пропорционально количеству испытаний (для $inline$ составило около 6.5 часов), а желания сильно оптимизировать код у меня не было, решено было для последующих экспериментов использовать по 1000 испытаний.

Результаты Монте-Карло

Давайте посмотрим, как зависит рассчитываемые значения вероятностей от используемого сценария пересаживания агентов. Ниже показаны результаты вычислений для разных сценариев, при $inline$ и $inline$ ( $inline$ ) и количестве испытаний по $inline$ .

Как можно видеть отличия между рассчитанными значениями вероятностей с использованием разных сценариев намного меньше неопределенности этих результатов. Это позволяет заключить что более точная имитации мира Dракош привела бы к такому же результату. Поэтому не зачем тратить время.

5. Что получилось?

На графике ниже показаны зависимость вероятностей $inline$ и $inline$ от плотности агентов в пространстве. Синяя и красная области это массивы данных, насчитанные методом Монте-Карло (по 1000 итераций для каждого значения $inline$ ). Черные линии это точные значения, вычисленные методом, описанным в разделе 3.

Совпадение результатов, полученных разными методами, позволяет надеяться, что серьезных ошибок не было допущено.

Теперь можем посмотреть, как выглядит успешность действий Step 1/2, Attack и Sex при полностью случайном (неосознанном) поведении агентов. А точнее на вторые слагаемые в выражениях для индексов осознанности, которые как раз и задают базовый уровень успешности, обусловленный вероятностями обнаружения агентов в пространстве:

$\begin{array}{1} I_{Stp}=L_{Stp}-(1-W_2) \\ I_{Att}=L_{Att}-W_1 \\ I_{Sex}=L_{Sex}-f_{Sex}W_1(1-W_2) \end{array}$

Для однозначности примем что частота действия Sex $f_{Sex}=1$ (т.е. если партнер был замечен в ячейке, то он принимает участие в размножении ~~18+ content~~).

В дальнейшем мы сравним полученные результаты с успешностью Тупиков (раса агентов без нейронной сети) и полноценных Dракош и посмотрим, как будет расти успешность в результате развития нейронной сети агентов.

Ландо С.К. Лекции о производящих функциях. 2007. 144 c.
Соболь И.М. Численные методы Монте-Карло. 1973. 312 с.
Бусленко Н.П., Шрейдер Ю.А. Метод статистических испытаний (Монте-Карло) и его реализация на цифровых вычислительных машинах. 1961. 226 с.

Подробнее..

Категории: Matlab , Математика , Искусственный интеллект , Эволюционное моделирование , Мультиагентные системы , Искусственная жизнь , Комбинаторика , Производящие функции , Метод монте-карло , Имитационное моделирование

Из песочницы Каков вопрос таков ответ формализуя задачу мы уже предопределяем возможный ответ

19.09.2020 18:15:27 |

Автор: admin

В интересной и поучительной статье Случайный трамвай посреди незнакомого города предлагается такой эксперимент:

Представьте себе, что некто взял полоску фотографической пленки длинной N см и решил пронаблюдать за тем, как на ней будут оставлять свой след приходящие из космоса частицы. В масштабах эксперимента плотность вероятности попадания частиц на пленку будет описываться равномерным распределением на отрезке от 0 до N. В этом опыте экспериментатор сообщает вам расстояние k между левым краем пленки и точкой, куда угодила первая зарегистрированная частица. Как и прежде, от вас требуется дать приемлемую оценку для неизвестного вам N.

Для решения этой задачи было сделано такое предположение:

Представьте теперь, что в одном эксперименте расстояние от места попадания частицы до левого края фотопленки было равным Р1, а в другом эксперименте Р2, причем Р1<Р2. Не будет ли тогда разумным, длине фотопленки в первом эксперименте дать меньшую оценку, чем во втором?

Мне стало интересно в цифрах всегда ли и насколько это разумно?

Эти заметки не продолжение и не обсуждение статьи из которой взята цитата, это попытка посмотреть как сама постановка задачи, введенные ограничения, допущения и условия принимаемые на этапе формализации отразятся на полученном ответе. Я не буду приводить формулы и постараюсь не использовать специальные термины, мне кажется так будет отчетливей видна сама проблема зависимости результата от принятых или не принятых допущений.

Для начала, я изменю, упрощу и приземлю эксперимент

Судьба или наш помощник имеет мешочек в котором лежат пронумерованные по порядку бочонки, как в лото. Помощник (мне его представить легче чем судьбу) в тайне от нас достает наугад бочонок и насыпает в первый сундук пронумерованных шаров по числу на бочонке. Затем он повторяет процедуру случайного извлечения бочонка и насыпает соответствующее число пронумерованных по порядку шаров во второй сундук. Перед нами стоят два сундука с неизвестным количеством шаров в каждом из них. Мы достаем наугад один шар из первого и один шар из второго сундука, и делаем разумное предположение, что шару с большим номером соответствует сундук с большим количеством шаров.
Оценим насколько предположение разумно?

Формализуем и уточним задачу

1. Раз уж бочонки лежат в мешочке, то они должны быть ограничены каким-то числом. Помня о первоисточнике про число трамвайных линий, ограничил пока число бочонков в 30.

2. А как поступить если мы вынули из сундуков шары с одинаковыми номерами? У нас есть варианты:

2.1 признать исход неудачным, не принимать решения и попросить помощника сделать новое заполнение сундуков.

2.2 бросить монетку и наугад решить в каком сундуке шаров больше. В этом варианте не будет неудачных исходов.

2.3 решить что раз номера одинаковые, то и количество шаров в сундуках тоже одинаковое. В этом варианте тоже не будет неудачных исходов.

Тут я хочу заметить, что я не выбираю какой вариант лучше. Моя цель посмотреть как разные варианты скажутся на полученном ответе.

3. Раз у нас появилось разное количество исходов, то встает вопрос: А от какого количества исходов считать долю правильных ответов? От всех опытов или только от удачных исходов? Посчитаем оба варианта.

4. Вот вынул помощник первый бочонок, посмотрел номер, насыпал соответствующее число шаров в первый сундук. Стоп! А что он сделал с вынутым бочонком затем? У него два варианта: положить бочонок назад в мешок, а можно не класть назад в мешок. Или что тоже самое, помощник мог достать сразу два бочонка и насыпать шары в сундуки по вынутым числам на бочонках, помощники бывают ленивые, а мы не видим что он там творит. В этом случае у нас никогда не будет равное число шаров в сундуках, и следовательно неудачных исходов. Этот пункт явным образом отступает от задачи из цитаты, там бочонок возвращается назад в мешок, но у меня другие цели, да и невозвращение бочонка это типичная ситуация в жизни, посчитаем и такой вариант.

Итак, у нас есть три варианта как считать исходы опыта при которых номера шаров одинаковы, два варианта подсчета доли правильных ответов и два варианта наполнения сундуков шарами. Итого 12 вариантов результатов эксперимента!

Как вероятность правильного ответа будет зависеть от количества бочонков в мешке судьбы, то есть от максимально возможного числа шаров в сундуке? Может быть все варианты будут одинаковыми? Может быть варианты будут иметь одинаковую тенденцию? Вот в этот момент я попробовал проверить свою интуицию заполнив такую табличку:

Оказалось, забегая вперед, что тренировать и тренировать мне еще интуицию. Я подчистил табличку от многих своих соображений.

Чтобы не утомлять формулами, которые хоть и красивы, но рекуррентны, а свести рекуррентные формулы к замкнутым мне не под силу, опишу общий алгоритм расчета:

1. Для каждого числа бочонков в мешке, мы можем составить список всех вариантов наполнения сундуков шарами.

Пример: Если число бочонков 4, то получим 16 вариантов наполнения двух сундуков по количеству шаров: 1и1, 1и2, 1и3, 2и1, 2и2 4и4.

2. Для каждого варианта наполнения сундуков подсчитываем число правильных ответов для трех вариантов подсчета равных шаров.

Пример: Для наполнения сундуков 2и3, (в первом сундуке 2 шара, во втором 3) получится следующая таблица.

3. Для выбранного числа бочонков складываются все правильные ответы для каждого варианта наполнения сундуков.

4. Вычисляем долю правильных для двух вариантов подсчета (по отношению к общему числу опытов и к числу успешных).

5. Считаем так же пункты с 3 по 4 для варианта когда бочонок не возвращается в мешок, то есть когда у нас не может быть равное число шаров в сундуках.

Я подсчитал для числа бочонков с 1 до 8 и 30, чтобы была видна тенденция. Приведу графики.

Сначала для варианта когда бочонок возвращается в мешок

При увеличении числа бочонков в мешке, а следовательно увеличении возможного числа шаров в сундуках вероятность правильной оценки растет и разница между вариантами уменьшается. Любопытно, что вероятность не всегда выше 0,5. Так же любопытен желтый график, на нем есть спад и только потом подъем. Вообще, диапазон от 1 до 7 оказался не очевидным для меня.

Получается, что если шаров меньше 8, то для варианта подсчета Равные считаются неудачей. Доля правильных считается от всех опытов случайный ответ даст лучший результат чем следование правилу Больше номер шара, значит сундук содержит больше шаров.

Графики для варианта когда бочонок не возвращается в мешок и следовательно в сундуках не может быть одинаковое число шаров

Графика три, так как два совпадают, они обозначены красным цветом.

Для четырех вариантов вероятность правильного ответа падает и стремится, видимо, к 0,5!(?) Другими словами, в этих вариантах для большого числа шаров в сундуках, можно вообще не проводить опыта, а просто подбрасывать монетку результат одинаков. Собственно, вот ради этого я и решил просчитать различные варианты, я ждал каких-то неожиданностей. Я не имею строгого доказательства, что вероятность стремится именно к 0,5. Это опять моя интуиция, а она часто подводит.

Хочу еще раз подчеркнуть, что эти заметки не посвящены выбору правильной стратегии или оценке какой вариант лучше. Интерес заключался в том чтобы посмотреть влияние разных вариантов задания условий на получаемый результат.

P.S. Как и хотелось, мне удалось не использовать формул и употребить специальный термин рекуррентная формула всего один раз.

P.P.S. Если лень смотреть Википедию, то рекуррентная формула это когда вам требуется прийти в дом 30, но вы обязаны предварительно посетить все предыдущие дома с номерами от 1 до 29.

Подробнее..

Категории: Математика , Занимательные задачки , Теория вероятностей , Комбинаторика , Математическая статистика

	Русский
	English

Комбинаторика

SQL HowTo обрабатываем дерево упорядочиваем иерархию с рекурсией и без

Таков путь!

Рекурсивная сортировка

Подключаем комбинаторику

Комбинации

Перестановки

Подмножества

Иерархия без рекурсии!

Пути-дороги

А попроще можно?..

Четырёхмерные таблицы в комбинаторике два странных способа посчитать сочетания

Второй способ

Жадный алгоритм, ветви и границы для расписания мерчендайзеров (кейс Хакатона на оптимизацию)

Часть 2. Dракоши. Комбинаторика мира Dракош

1. Зачем нам вероятности?

Как уследить за Dракошами

Индексы осознанности или зачем нам вероятности

2. Постановка задачи

3. Подсчет способов расстановки агентов

Вывод рекуррентной формулы

Упрощение и переход приведенному виду

Построение производящей функции

4. Моделирование вероятностей методом Монте-Карло

Обзор алгоритма

Результаты Монте-Карло

5. Что получилось?

Из песочницы Каков вопрос таков ответ формализуя задачу мы уже предопределяем возможный ответ

Для начала, я изменю, упрощу и приземлю эксперимент

Формализуем и уточним задачу

Сначала для варианта когда бочонок возвращается в мешок

Графики для варианта когда бочонок не возвращается в мешок и следовательно в сундуках не может быть одинаковое число шаров

Категории

Последние комментарии