2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Двоичный перебор. Поиск в ширину.
Сообщение10.12.2011, 17:33 
Аватара пользователя
Добрый вечер! Сразу к задаче: Требуется найти последовательность чисел минимальной длины, обладающую нужными свойствами.
Ещё со школы помню очень простой алгоритм рекурсивного поиска для аналогичных задач:
Используется синтаксис C
void step(int n)
{ ...
  for(i=0; i<k; i++) {... step(n+1) ...}
  ...
}
 

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

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

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

Псевдокод такой:
код: [ скачать ] [ спрятать ]
Используется синтаксис C
Queue params
// ...
params.push(params0);
while (!params.isEmpty)
{
    step(params.pop());
}
// ...
void step(Params params)
{
    // ...
    params.push(newParams);
    // ...
}
 

 
 
 
 Re: Двоичный перебор. Поиск в ширину.
Сообщение10.12.2011, 19:44 
Аватара пользователя
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".

 
 
 
 Re: Двоичный перебор. Поиск в ширину.
Сообщение11.12.2011, 17:03 
kiyanyn в сообщении #514008 писал(а):
Ну, push и pop - это же типично стековые вызовы :) Тогда уж push_back и pop_front...
Вроде было хорошее название для замены одного из них, но забыл. А такие длинные в в стиле стандартной библиотеки C++ мне кажутся затуманивающими смысл. :-)

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

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

 
 
 
 Re: Двоичный перебор. Поиск в ширину.
Сообщение11.12.2011, 22:01 
Аватара пользователя
arseniiv
arseniiv в сообщении #513986 писал(а):
(Можно заметить, что от поиска в глубину отличается только очередью вместо стека.)

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

 
 
 
 Re: Двоичный перебор. Поиск в ширину.
Сообщение11.12.2011, 22:27 

(Оффтоп)

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group