2014 dxdy logo

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

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




 
 Последовательность действий
Сообщение10.03.2012, 18:25 
Помогите, пожалуйста, привести пример последовательности действий, приводящей от исходных данных к результату, но не обладающей свойством детерминированности.
Заранее благодарю!

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 18:57 
Аватара пользователя
Может быть что-то, использующее генератор случайных чисел?

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 19:24 
acme в сообщении #546970 писал(а):
Помогите, пожалуйста, привести пример последовательности действий, приводящей от исходных данных к результату, но не обладающей свойством детерминированности.
Заранее благодарю!

Да практически любой алгоритм, где не регламентируется, какое из множества возможных действий выполнить. Например, нужно выполнить поиск в глубину по некоторому графу. Входя в очередную вершину, выбираем любое исходящее ребро и переходим в следующую вершину. На выходе будет дерево обхода, но какое именно - заранее неизвестно.

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

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 20:26 
Поскольку речь идёт о последовательности действий, то
сделаем так:
- сначала идёт линейный участок последовательности действий
- потом точка разветвления
- имеем список участков последовательности действий (ветви)
- в точке разветвления генерируем случайный переход на элемент списка (на ветвь).
Куда идут ветви - уже не важно.
Кажется, таким образом.

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 20:48 
Но сообщение Zealint более общо.

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 21:35 
Еще относительно конкретный вариант: генетический алгоритм оптимизации

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 21:54 
Zealint в сообщении #547008 писал(а):
Входя в очередную вершину, выбираем любое исходящее ребро

Как это -- "любое"?...

Какой-то выбор мы вынуждены будем жёстко запрограммировать, пусть и неявным образом.

А если нет, то всё и тривиально, и вообще к программированию не имеет отношения.

 
 
 
 Re: Последовательность действий
Сообщение10.03.2012, 23:03 
Zealint в сообщении #547008 писал(а):
Однако важно понимать, что как только Вы запрограммируете поиск в глубину, то он тут же станет детерминированным. Если, конечно, для выбора исходящего ребра не используется какой-нибудь квантовый генератор случайных чисел, для которого принципиально невозможно определить последовательность выдаваемых чисел.

 
 
 
 Re: Последовательность действий
Сообщение11.03.2012, 05:10 
ewert в сообщении #547071 писал(а):
Как это -- "любое"?...

Какой-то выбор мы вынуждены будем жёстко запрограммировать, пусть и неявным образом.

А если нет, то всё и тривиально, и вообще к программированию не имеет отношения.

Очень просто. Практически в любом учебнике, где описан поиск в ширину, написано, находясь в вершине $i$ выбираем ребро $(i,j)\in E$ (какое? - любое). Автор не спрашивает про программирование, он просит указать последовательность действий. Про программирование я ответил - там действительно всё жёстко.

 
 
 
 Re: Последовательность действий
Сообщение12.04.2012, 18:47 
Аватара пользователя
acme в сообщении #546970 писал(а):
Помогите, пожалуйста, привести пример последовательности действий, приводящей от исходных данных к результату, но не обладающей свойством детерминированности.
Заранее благодарю!

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

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


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