Постановка проблемы

Алгоритм Фаулкса и его приложения

Введение

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

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

Ниже изложена простейшая теория и алгоритм Фаулкса [[1]].

На днях мы посетили нашего друга Фреголи, хорошо известного в Мексике, и спросили у него, не мог бы он раскрыть нам секрет, который сделал его замечательным циркачом, неизменно любимым детьми и даже взрослыми. В самом деле, известно, что Фреголи может полностью сменить одежду в рекордное время. «Речь идет не о секрете, — сказал он нам, — а о логическом методе одевания и раздевания, переданном мне моими предками». И как хорошо воспитанный человек он счел возможным добавить: «Несомненно, математика, которая является вашей профессией, позволила бы вам представить себе усилия, которых потребовало от моего прадеда решение подобных задач».

Быть может, читатель будет удивлен этим утверждением. Избавим его от сомнений. Если математика прошлого действительно позволяла подсчитать количество комбинаций, которые нужно испробовать для того, чтобы одеться или раздеться по возможности наиболее удобным способом, то математика сегодняшнего дня позволяет определить лучшую (или лучшие) среди этих комбинаций. Предположим для простоты, что, когда наш друг Фреголи собирается сменить одежду, он не снимает белья — ни рубашки, ни кальсон. Тем не менее, чтобы предстать в обличье денди, ему все еще остается напялить на себя целую форму, содержащую брюки, жилет, пиджак, галстук, пальто, носки, ботинки, перчатки, а затем взять в руку трость с серебряным набалдашником.

Посмотрим, что он может сделать по крайней мере с восемью первыми предметами; при этом любой согласится с тем, что:

1) взять свою трость он сможет в последнюю очередь,

2) ему остается исследовать самое большее

8! = 8 ∙ 7 ∙ 6 ∙ 5 ∙ 4 ∙ 3 ∙ 2 ∙ 1 = 40 320

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

Дата добавления: 2017-02-01