Алгоритм построения самой длинной цепочки последовательности из заданных элементов

EndoCrinolog

Здравствуйте!

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

У башни есть нулевая высота, которая имеет определенный тип основания. К этому типу основания может подойти только определенный вид кирпича. У кирпичей две стороны – верхняя и нижняя. Нижняя сторона – крепится к продолжению стены башни, на верхнюю – ставится новый кирпич.

Если упростить всё выше сказанное – это что-то вроде мозаики, которая строится только вверх разными элементами.

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

Самого кода алгоритма пока еще нет, планирую его написать на PHP.
Исходные параметры такие:
Массив с типами кирпичей:

PHP:
  1. $Blocks = array(
  2.    “ZZ”    =>  array(
  3.       ‘amount’    =>  0,
  4.       ‘type’  =>  ‘1’
  5.    ),
  6.    “ZU”    =>  array(
  7.       ‘amount’    =>  0,
  8.       ‘type’  =>  ‘2’
  9.    ),
  10.    “ZA”    =>  array(
  11.       ‘amount’    =>  0,
  12.       ‘type’  =>  ‘3’
  13.    ),
  14.    “ZS”    =>  array(
  15.       ‘amount’    =>  0,
  16.       ‘type’  =>  ‘4’
  17.    ),
  18.    “UZ”    =>  array(
  19.       ‘amount’    =>  0,
  20.       ‘type’  =>  ‘5’
  21.    ),
  22.    “UU”    =>  array(
  23.       ‘amount’    =>  0,
  24.       ‘type’  =>  ‘6’
  25.    ),
  26.    “UA”    =>  array(
  27.       ‘amount’    =>  0,
  28.       ‘type’  =>  ‘7’
  29.    ),
  30.    “US”    =>  array(
  31.       ‘amount’    =>  0,
  32.       ‘type’  =>  ‘8’
  33.    ),
  34.    “AZ”    =>  array(
  35.       ‘amount’    =>  0,
  36.       ‘type’  =>  ‘9’
  37.    ),
  38.    “AU”    =>  array(
  39.       ‘amount’    =>  0,
  40.       ‘type’  =>  ’10’
  41.    ),
  42.    “AA”    =>  array(
  43.       ‘amount’    =>  0,
  44.       ‘type’  =>  ’11’
  45.    ),
  46.    “AS”    =>  array(
  47.       ‘amount’    =>  0,
  48.       ‘type’  =>  ’12’
  49.    ),
  50.    “SZ”    =>  array(
  51.       ‘amount’    =>  0,
  52.       ‘type’  =>  ’13’
  53.    ),
  54.    “SU”    =>  array(
  55.       ‘amount’    =>  0,
  56.       ‘type’  =>  ’14’
  57.    ),
  58.    “SA”    =>  array(
  59.       ‘amount’    =>  0,
  60.       ‘type’  =>  ’15’
  61.    ),
  62.    “SS”    =>  array(
  63.       ‘amount’    =>  0,
  64.       ‘type’  =>  ’16’
  65.    )
  66. );

Буквы – это различные типы соединения кирпичей. Запись SA, например, обозначает, что у кирпича верхняя часть S-типа, а низ A-типа. К примеру, SA можно поставить на AZ, а AZ можно поставить на ZU, и так далее. Amount – это количество, которое можно настраивать.

Массив с типами основания башен:

PHP:
  1. $TowersBasis = array(
  2.    ‘Z’ =>  ‘1_1’,
  3.    ‘U’ =>  ‘2_1’,
  4.    ‘A’ =>  ‘3_1’,
  5.    ‘S’ =>  ‘4_1’
  6. );

Ну и конечно же текущий последний кирпич башни, от которого надо начать стройку:

PHP:
  1. $CurrentTowerBase = ‘S’;

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

 

mkramer

Есть алгоритм, BackTracking. Рекурсивный. У Н. Вирта хорошо описан в его книге “Алгоритмы + структуры данных = программы”

 

EndoCrinolog

Так, интересно, будем читать

 

EndoCrinolog

Так, я понял, что алгоритм усложнился… По идее, на выходе должен получиться массив с массивами последовательностей кирпичей, где самая длинная и будет ответом.
Должно быть что-то вроде сетки с количеством блоков 0 – N и прогонами 0 – M[​IMG]

Количество M будет зависеть от того, какие последовательности были выбраны ранее.. И если все они исчерпаны, значит, больше последовательностей нет – надо вернуть..

Понимаю, что всё должно быть в рекурсиве, как мне подсказал @mkramer, но пока что-то в голову не влезает, как это осуществить…

 

Drunkenmunky

Почитайте-ка про теорию графов.
В частности, вас заинтересует Гамильтонова цепь.

 

MouseZver

Я понял )))

Ширина или высота, одна из них максимальное, известно ?

 

EndoCrinolog

По идее, получается граф, и мне нужно найти его максимально длинную цепочку
upload_2021-7-17_22-10-51.png

Максимальная цепочка (по хорошему счету) должна состоять из максимального количества кирпичей (N)

 

MouseZver

а не лучше каждый кирпич индексировать ?

5IfrLJT7GbI.jpg

 

EndoCrinolog

PHP:
  1. [$IndexedBlocks]: Array
  2. (
  3.     [0] => Array
  4.         (
  5.             [type] => U|S
  6.             [up] => U
  7.             [down] => S
  8.         )
  9.  
  10.     [1] => Array
  11.         (
  12.             [type] => U|S
  13.             [up] => U
  14.             [down] => S
  15.         )
  16.  
  17.     [2] => Array
  18.         (
  19.             [type] => U|S
  20.             [up] => U
  21.             [down] => S
  22.         )
  23.  
  24.     [3] => Array
  25.         (
  26.             [type] => U|S
  27.             [up] => U
  28.             [down] => S
  29.         )
  30.  
  31.     [4] => Array
  32.         (
  33.             [type] => U|S
  34.             [up] => U
  35.             [down] => S
  36.         )
  37.  
  38.     [5] => Array
  39.         (
  40.             [type] => U|S
  41.             [up] => U
  42.             [down] => S
  43.         )
  44.  
  45.     [6] => Array
  46.         (
  47.             [type] => A|S
  48.             [up] => A
  49.             [down] => S
  50.         )
  51.  
  52.     [7] => Array
  53.         (
  54.             [type] => S|S
  55.             [up] => S
  56.             [down] => S
  57.         )
  58.  
  59.     [8] => Array
  60.         (
  61.             [type] => S|S
  62.             [up] => S
  63.             [down] => S
  64.         )
  65.  
  66.     [9] => Array
  67.         (
  68.             [type] => S|S
  69.             [up] => S
  70.             [down] => S
  71.         )
  72.  
  73.     [10] => Array
  74.         (
  75.             [type] => S|S
  76.             [up] => S
  77.             [down] => S
  78.         )
  79.  
  80.     [11] => Array
  81.         (
  82.             [type] => Z|Z
  83.             [up] => Z
  84.             [down] => Z
  85.         )
  86.  
  87.     [12] => Array
  88.         (
  89.             [type] => Z|Z
  90.             [up] => Z
  91.             [down] => Z
  92.         )
  93.  
  94.     [13] => Array
  95.         (
  96.             [type] => Z|Z
  97.             [up] => Z
  98.             [down] => Z
  99.         )
  100.  
  101.     [14] => Array
  102.         (
  103.             [type] => Z|Z
  104.             [up] => Z
  105.             [down] => Z
  106.         )
  107.  
  108.     [15] => Array
  109.         (
  110.             [type] => Z|Z
  111.             [up] => Z
  112.             [down] => Z
  113.         )
  114.  
  115.     [16] => Array
  116.         (
  117.             [type] => Z|Z
  118.             [up] => Z
  119.             [down] => Z
  120.         )
  121.  
  122.     [17] => Array
  123.         (
  124.             [type] => Z|U
  125.             [up] => Z
  126.             [down] => U
  127.         )
  128.  
  129.     [18] => Array
  130.         (
  131.             [type] => Z|U
  132.             [up] => Z
  133.             [down] => U
  134.         )
  135.  
  136.     [19] => Array
  137.         (
  138.             [type] => Z|U
  139.             [up] => Z
  140.             [down] => U
  141.         )
  142.  
  143.     [20] => Array
  144.         (
  145.             [type] => Z|A
  146.             [up] => Z
  147.             [down] => A
  148.         )
  149.  
  150.     [21] => Array
  151.         (
  152.             [type] => Z|A
  153.             [up] => Z
  154.             [down] => A
  155.         )
  156.  
  157.     [22] => Array
  158.         (
  159.             [type] => Z|A
  160.             [up] => Z
  161.             [down] => A
  162.         )
  163.  
  164.     [23] => Array
  165.         (
  166.             [type] => Z|A
  167.             [up] => Z
  168.             [down] => A
  169.         )
  170.  
  171.     [24] => Array
  172.         (
  173.             [type] => Z|A
  174.             [up] => Z
  175.             [down] => A
  176.         )
  177.  
  178.     [25] => Array
  179.         (
  180.             [type] => Z|A
  181.             [up] => Z
  182.             [down] => A
  183.         )
  184.  
  185.     [26] => Array
  186.         (
  187.             [type] => Z|A
  188.             [up] => Z
  189.             [down] => A
  190.         )
  191.  
  192.     [27] => Array
  193.         (
  194.             [type] => U|Z
  195.             [up] => U
  196.             [down] => Z
  197.         )
  198.  
  199.     [28] => Array
  200.         (
  201.             [type] => U|Z
  202.             [up] => U
  203.             [down] => Z
  204.         )
  205.  
  206.     [29] => Array
  207.         (
  208.             [type] => U|U
  209.             [up] => U
  210.             [down] => U
  211.         )
  212.  
  213.     [30] => Array
  214.         (
  215.             [type] => U|U
  216.             [up] => U
  217.             [down] => U
  218.         )
  219.  
  220.     [31] => Array
  221.         (
  222.             [type] => U|U
  223.             [up] => U
  224.             [down] => U
  225.         )
  226.  
  227.     [32] => Array
  228.         (
  229.             [type] => U|A
  230.             [up] => U
  231.             [down] => A
  232.         )
  233.  
  234.     [33] => Array
  235.         (
  236.             [type] => U|A
  237.             [up] => U
  238.             [down] => A
  239.         )
  240.  
  241.     [34] => Array
  242.         (
  243.             [type] => U|A
  244.             [up] => U
  245.             [down] => A
  246.         )
  247.  
  248.     [35] => Array
  249.         (
  250.             [type] => A|Z
  251.             [up] => A
  252.             [down] => Z
  253.         )
  254.  
  255.     [36] => Array
  256.         (
  257.             [type] => A|Z
  258.             [up] => A
  259.             [down] => Z
  260.         )
  261.  
  262.     [37] => Array
  263.         (
  264.             [type] => A|Z
  265.             [up] => A
  266.             [down] => Z
  267.         )
  268.  
  269.     [38] => Array
  270.         (
  271.             [type] => A|Z
  272.             [up] => A
  273.             [down] => Z
  274.         )
  275.  
  276.     [39] => Array
  277.         (
  278.             [type] => A|U
  279.             [up] => A
  280.             [down] => U
  281.         )
  282.  
  283.     [40] => Array
  284.         (
  285.             [type] => A|A
  286.             [up] => A
  287.             [down] => A
  288.         )
  289.  
  290.     [41] => Array
  291.         (
  292.             [type] => A|A
  293.             [up] => A
  294.             [down] => A
  295.         )
  296.  
  297.     [42] => Array
  298.         (
  299.             [type] => A|A
  300.             [up] => A
  301.             [down] => A
  302.         )
  303.  
  304.     [43] => Array
  305.         (
  306.             [type] => S|Z
  307.             [up] => S
  308.             [down] => Z
  309.         )
  310.  
  311.     [44] => Array
  312.         (
  313.             [type] => S|Z
  314.             [up] => S
  315.             [down] => Z
  316.         )
  317.  
  318.     [45] => Array
  319.         (
  320.             [type] => S|Z
  321.             [up] => S
  322.             [down] => Z
  323.         )
  324.  
  325.     [46] => Array
  326.         (
  327.             [type] => S|Z
  328.             [up] => S
  329.             [down] => Z
  330.         )
  331.  
  332.     [47] => Array
  333.         (
  334.             [type] => S|Z
  335.             [up] => S
  336.             [down] => Z
  337.         )
  338.  
  339.     [48] => Array
  340.         (
  341.             [type] => S|U
  342.             [up] => S
  343.             [down] => U
  344.         )
  345.  
  346.     [49] => Array
  347.         (
  348.             [type] => S|U
  349.             [up] => S
  350.             [down] => U
  351.         )
  352.  
  353.     [50] => Array
  354.         (
  355.             [type] => S|U
  356.             [up] => S
  357.             [down] => U
  358.         )
  359.  
  360.     [51] => Array
  361.         (
  362.             [type] => S|A
  363.             [up] => S
  364.             [down] => A
  365.         )
  366.  
  367. )

Допустим… А дальше?…

 

EndoCrinolog

Нашел нубский вариант – рандомно ставить кирпичи, запуская повтор функции несколько тысяч раз, пока не выявится самая длинная цепочка…

 

MouseZver

 

EndoCrinolog

Ну не получилось у меня рекурсией(((

 

MouseZver

при создании нового кирпича, с более углубленным ходом, заранее в системе регистрируй его.

 

mkramer

@EndoCrinolog Если не получается рекурсия, значит не знаете, как она работает, за счёт чего. Загуглите “стек вызовов”

 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *