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

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

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

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

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

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

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

Спойлер: $Blocks

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 — это количество, которое можно настраивать.

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

Спойлер: $TowersBasis

PHP:

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

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

Спойлер: $CurrentTowerBase

PHP:

1. $CurrentTowerBase = ‘S’;

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

 

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

 

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

 

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

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

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

 

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

 

Я понял )))

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

 

По идее, получается граф, и мне нужно найти его максимально длинную цепочку

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

 

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

 

Спойлер: $IndexedBlocks

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 Если не получается рекурсия, значит не знаете, как она работает, за счёт чего. Загуглите «стек вызовов»