иметь вид Xi Xi

Xi I, . . ., Xin, ЧТО приводит к еле-

для графов, степени вершин которых лежат в вышеприведенных пределах 3 - 5, метод по существу не чувствителен к степеням вершин.

Вычислительные результаты, показанные на рис. 10.6 - 10.8, относятся к поиску одного гамильтонова цикла в графе. Небезынтересно сказать несколько слов о вычислениях с тремя алгоритмами, когда искались все гамильтоновы циклы. Так, для неориентированного графа с 20 вершинами со степенями вершин 3 -5 потребовалось 2 с, чтобы найти все гамильтоновы циклы, следуя алгоритму Робертса и Флореса (этих циклов оказалось 18). Улучшенный вариант того же алгоритма потребовал 1,2 с, а мультицепной алгоритм - 0,07 с. Вычисления проводились на ЭВМ CDC 6600.

4. Простая задача планирования

Во введении к данной главе мы описали пример промышленной фирмы, выпускающей продукты pi, р^, . . Рп с использованием единственного типа аппаратуры в циклическом режиме, и поставили вопрос о порядке производства продуктов, требующем наименьшего возможного числа перенастроек аппаратуры. Был построен граф G = (X, А), вершины х^ которого представляют продукты Pi (j = 1, 2, . . ., п), а дуги (х^, Xj) показывают, что продукт Pj можно производить вслед за продуктом Pi без перенастройки.

Если граф G = (Z, А) имеет гамильтонов цикл, например а^г,1 Х{, Xi . . ., Xini то соответствующая последовательность продуктов pi, Pi, Pi . . ., Pin может быть произведена на аппаратуре без какой-либо перенастройки, так как по определению гамильтонова цикла

(xi, Xi ) А для всех к = i,2, . . ., ixi i = Xj,) и А определено выше как множество {{xi, Xj) \ Cij = 0}.

Если G не имеет никакого гамильтонова цикла, то мы можем построить граф G = (Х^, Ai), где

х,=хиы

и

AiA[]{x, у1)\х£Х}[}{{у1,х)\х^Х},

т. е. ввести в граф G фиктивную вершину у^ вместе с дугами, ведущими в нее и исходящими из нее в каждую действительную вершину графа G.

Если у графа существует гамильтонов цикл, то он будет

Xi , . . . , Xi

Zi W El

mo продукты должны производиться в последовательности

Р^а.г^ ..., Pip, затем р,, Pi, ... и т.д. ...

затем pi, Pi, Рг, Pi.

Доказательство. Доказательство следует непосредственно из рассуждений, предшествующих теореме, с использованием индукции.

дующей последовательности производства продуктов

РЫ1, Pir2, Pin. Pil Рп Pir

с единственной операцией перенастройки после окончания производства последнего продукта и началом производства первого. Таким образом, фиктивная вершина играет роль метки, показывающей то место в последовательности, где необходима перенастройка аппаратуры. В терминах графа фиктивная вершина и ассоциированные с ней дуги обеспечивают существование цепи между двумя действительными вершинами. Таким образом, если существует последовательность продуктов с одной перенастройкой, т. е. если в G существует гамильтонов цикл, при условии, что можно использовать одну дугу {xt, Xj) А, то добавление вершины Ух к G всегда приведет к существованию в Gi гамильтонова цикла, так как лишняя необходимая дуга (xi, Xj) может быть заменена двумя фиктивными дугами (х Ух) и (i/i, Xj).

Если граф G] не имеет гамильтонова цикла, то мы построим граф = (Xj. а2) вместо графа Gx, где

Х2 = Х,иЫ

и

Л = Ли{(, У2)\Х^Х}\]{{У2, х)\х^Х}, и аналогично будем действовать далее.

Теорема I. Если граф G = {Хт, А^, определяемый как

т

X = U[U(J/;}]. (10.2)

т т

Am-A[}[\J {(X, yj) IXеХ}] и [ S {{Vj, х)\х^Х}], (10.3)

содержит гамильтонов цикл, а граф G-i такого цикла не содержит, то число т есть минимальное число необходимых перенастроек, и если гамильтонов цикл в G имеет вид

4.1. Вычислительные аспекты

В рассуждениях предыдущего раздела граф G каждый раз пополнялся единственной фиктивной вершиной. Если оптимал^,-ное решение задачи содержит т перенастроек аппаратуры, то нужно будет сделать ттг + 1 попыток отыскать гамильтоновы циклы в графах С, Gi, . . ., G-, причем только последняя из этих попыток окажется успешной и приведет к решению задачи. Очевидно, что число т ограничено сверху величиной пив общем случае в практических задачах оно будет лишь небольшой частью числа п. Тем не менее с вычислительной точки зрения необходимы различные процедуры для проверки наличия в графе гамильтоновых циклов и построения таких циклов, так как оказывается [6], что проще найти гамильтонов цикл в графе, имеющем такой цикл, чем доказать, что не существует никакого гамильтонова цикла в графе, его не имеющем. Этот факт подсказывает, что более подходящим будет алгоритм, который начинает с верхней границы В для оптимального (минимального) числа перенастроек аппаратуры и последовательно дает и проверяет графы G, Gg-i, ... и т. д. до тех пор, пока не будет найден граф С^-ц не имеющий гамильтоновых циклов. Краткое описание такого алгоритма дается ниже.

Шаг 1. Найти верхнюю границу В для оптимального (минимального) числа необходимых перенастроек аппаратуры (см. приложение).

Шаг 2. Используя формулы (10.2) и (10.3), построить граф

Шаг 3. Определить, имеет ли граф G гамильтонов цикл. Если да, то хранить этот цикл в виде вектора Н, записав его на место предыдущего хранящегося цикла, и перейти к шагу 4 или шагу 5.

Шаг 4. В <- В - 1, перейти к шагу 2.

Шаг 5. Останов, т = В -\- I является минимальным числом перенастроек аппаратуры, и последняя последовательность в ff является требуемой последовательностью производства продуктов.

Шаг 1 приведенного выше алгоритма требует дальнейших пояснений. Очевидно, что чем более точной будет начальная верхняя граница В, тем меньшее число итераций основного алгоритма придется сделать. Процедура получения хорошей оценки для верхней границы дана в приложении. Существование гамильтонова цикла в графе Gb может быть установлено с использованием мультицепного алгоритма разд. 2.S.