Big O обозначения и фактор ветвления

Question

Допустим, вы пытаетесь понять, какой путь лучше выбрать. У вас есть z количество возможных ходов и вы можете сделать x количество ходов одновременно. Вы всегда делаете x ходов одновременно, не больше и не меньше. Как вы можете выяснить фактор ветвления в терминах х и г?

Answer 1

коэффициент ветвления в этом примере равен 1 - размер проблемы не увеличивается - у вас было x вариантов для начала, вы выполнили их все и у вас есть такое же количество доступных ходов. Вы, кажется, эффективно делаете 1 шаг вниз по каждой из x прямых линий одновременно. ветвления не происходит, если я неправильно понял ваш вопрос (что возможно, потому что я не вижу, что с этим связано z)

Answer 2

Если вы генерируете x новых состояний (по одному на каждое действительное движение, которое вы можете сделать) на каждом узле, тогда коэффициент ветвления равен x, если x всегда меньше z. Если z всегда меньше x, то коэффициент ветвления равен z (поскольку вы можете делать только правильные ходы).