Двоичный перебор. Поиск в ширину.

[Legioner93]

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

Используется синтаксис C

void step(int n)
{ ...
  for(i=0; i<k; i++) {... step(n+1) ...}
  ...
}
 

В википедии прочитал, что это называется поиском в глубину. Однако для моей задачи этот алгоритм, очевидно, не годится. Даже если заранее известно, что существует короткое решение (и даже что их очень много), то рекурсия почти всегда уходит в бесконечность, потому что решений на, например, самых левых листьях может просто не быть. И даже если добавить кучу ограничений для завершения рекурсии, она всё равно может уйти очень далеко по "неперспективным" веткам. Немного поразмыслив, я пришел к выводу, что нужно перебирать не обычным способом (всегда самую левую вершину), а по возрастанию глубины. Берем корень, потом перебираем все узлы первого поколения, потом второго и т.д. Тогда минимальное решение найдется гораздо быстрее (заранее известно, что оно существует).
В википедии прочитал, что это называется поиском в ширину. Прошу помощи в реализации. Не очень представлю, как бы это применить к данной задаче. Хочется чего-нибудь изящного и короткого.

[arseniiv]

Я как-то что-то искал в ширину (и не нашёл). Сделал очередь, запихивал в неё параметры, с которыми вызывать функцию, вместо немедленного вызова. После возврата из функции вызываем её с параметрами из очереди, если не пуста. (Можно заметить, что от поиска в глубину отличается только очередью вместо стека.)

-- Сб дек 10, 2011 21:44:51 --

Псевдокод такой:

Используется синтаксис C

Queue params
// ...
params.push(params0);
while (!params.isEmpty)
{
    step(params.pop());
}
// ...
void step(Params params)
{
    // ...
    params.push(newParams);
    // ...
}
 

[kiyanyn]

arseniiv в сообщении #513986 писал(а):

-- Сб дек 10, 2011 21:44:51 --

Псевдокод такой:

Используется синтаксис C

Queue params
// ...
params.push(params0);
while (!params.isEmpty)
{
    step(params.pop());
}
// ...
void step(Params params)
{
    // ...
    params.push(newParams);
    // ...
}
 

Ну, push и pop - это же типично стековые вызовы :) Тогда уж push_back и pop_front...

А по сути - для Legioner93 - почитайте что угодно простенькое про поиск в ширину в графах, типа "Алгоритмы - просто как 2x2".

[arseniiv]

kiyanyn в сообщении #514008 писал(а):

Ну, push и pop - это же типично стековые вызовы :) Тогда уж push_back и pop_front...

Вроде было хорошее название для замены одного из них, но забыл. А такие длинные в в стиле стандартной библиотеки C++ мне кажутся затуманивающими смысл.

-- Вс дек 11, 2011 20:06:13 --

А, вот нашёл: Enqueue и Dequeue.

[Legioner93]

arseniiv

arseniiv в сообщении #513986 писал(а):

(Можно заметить, что от поиска в глубину отличается только очередью вместо стека.)

Вот это самое главное. Всё сразу встало на свои места в голове! Большое спасибо:)

[arseniiv]

(Оффтоп)

Не за что! Увы, не помню, откуда это во мне. Наверно, из какой-то полезной книги, а название забыл, чтобы посоветовать.