ЗА.Ь. Десятичный -восьмеричный-двоичный перевод (частные цели). Разработайте и реализуйте алгоритм для перевода десятичных чисел в двоичные и наоборот. В качестве подцели примите перевод в восьмеричные числа.

3.1.6. Игра (отрабатывание назад). Три человека играют в игру, в которой один выигрывает, а другие два проигрывают. Каждый проигравший дает выигравшему сумму, раввую количеству денег, которое было у выигравшего в начале игры. Были сыграны три игры, каждый игрок выиграл один р-аз, у 1-го игрока оказалось 4 доллара, у 2-го - 20 долларов, у 3-го - 6 долларов. Сколько денег было у каждого игрока в начале игры?

Рис. 3.1.4. Греческий крест.

*L3.1.7. Магические квадраты (постановка задачи и решение). Магический квадрат размерности п- это матрица пХп, содержащая первые п положительных целых чисел. Эти числа расположены так, что их суммы в каждой строке, столбце и вдоль двух главных диагоналей равны одному и тому же значению С.

(а) Сформулируйте алгебраическую задачу, решение которой даст магический квадрат для /г=3. Постарайтесь решить полученную систему уравнений без применения ЭВМ.

(б) Разработайте алгоритм нахождения магических квадратов для /г=3 и п=4. Эта процедура не обязательно должна основываться на вашей алгебраической модели. Реализуйте, проверьте и проанализируйте алгоритм на ЭВМ. Можно ли его использовать для больших значений п?

Рис. 3.1.5. Задача о ханойской башне.

*3.1.8. Ханойская башня (отрабатывание назад, частные цели). Рис. 3.1.5 иллюстрирует древнюю игру, известную под названием Ханойской башни. Игра начинается, когда п дисков разного диаметра расположены по возрастанию диаметров на одном из трех стержней. Цель игры - по одному перенести диски, чтобы они в конечном счете были расположены в том же порядке на другом стержне. Не разрешается класть диск большего диаметра иа диск меньшего диаметра.. Разработайте алгоритм, который проделывает эту процедуру за 2«-1 операций, где под операцией подразумевается перемещение диска с одного стержня на другой. Стержни, по существу, являются запоминающими устройствами типа стека, и переставлять можно только верхний диск в пирамиде.

3.1.9. Каннибалы и миссионеры. Следующая задача является классической, и для ее решения можно воспользоваться любым из трех основных методов, рассмотренных в этом ра.чдсле. Три миссионера и три каннибала находятся на одном берегу реки; лодка может перевезти двух человек. Все они хотят перебраться через реку. Нельзя допустить, чтобы на одном берегу находилась группа миссионеров с более многочисленной группой каннибалов. Разработайте процедуру, позволяющую всем шестерым перебраться через реку.

3.2. Эвристики

Эвристический алгоритм, или эвристика, определяется как алгоритм со следующими свойствами:

1. Он обычно находит хорошие, хотя не обязательно оптимальные 5ешения.

2. Его можно быстрее и проще реализовать, чем любой известный точный алгоритм (т. е. тот, который гарантирует оптимальное решение).

Понятия «хороший» и «обычно» в свойстве 1 меняются от задачи к задаче. Например, если для решения задачи все известные точные алгоритмы требуют нескольких лет машинного времени, то мы можем охотно принять любое нетривиальное приближенное решение, которое может быть получено за разумное время. С другой стороны, имея быстрое, близкое к оптимальному решение, мы можем стремиться все же к точному решению.

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

1. Те, которые легко удовлетворить.

2. Те, которые не так легко удовлетворить.

1. Те, которые должны быть удовлетворены.

2. Те, по отношению к которым мы могли бы пойти на компромисс.

Тогда цель построения алгоритма - создать алгоритм, гарантирующий выполнение требований 1-го класса, но не обязательрю 2-го. Это не означает, что для удовлетворения требований 2-го класса не делается никаких попыток, это просто означает, что не может быть дано никаких гарантий, что оии будут удовлетворены.

Часто очень хорошие алгоритмы должны рассматриваться как эвристические. Например, предположим, что мы построили быстрый алгоритм, который, кажется, работает на всех тестовых задачах, но мы не можем доказать, что алгоритм правильный. Пока не дано такое доказательство, алгоритм следует рассматривать как эвристику.

В качестве примера рассмотрим следующий «грубый» алгоритм решения задачи коммивояжера из разд. 1.3.

Algorithm GTS (коммивояжер). Построить приближенное решение TOUR со стоимостью COST для задачи коммивояжера с Л городами и матрицей стоимостей С, начиная с вершины U,

Шаг 0. [Инициализация] Set TOUR -е- 0; COST 0; F -ч- {/; помечаем V - «использована», а все другие вершины - «не использована». (Вершина V - положение на сети в данный момент.)

Шаг 1. [Посещение всех городов] For К-<- 1 to -1 do шаг 2 od. Шаг 2. [Выбор следующего ребра] Пусть (V, W) - ребро с наименьшей стоимостью, ведущее из F в любую неиспользованную вершину W; set TOUR TOUR+ + (F, W); COST <- COST+C(F, IF); помечаем W - «использована»; and set V-<r-W. Шаг 3. [Завершение тура] Set TOUR TOUR+ (F, 1); COST 4-C0ST+ +C(F, 1); and STOP.

Ha рис. 3.2.1, a изображена сеть с рис. 1.3.1; рис. 3.2.1,6 -е

Стоим 1=- В

Cmouii=7

Рис. 3.2.1. Иллюстрация алгоритма GTS.

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

Алгоритм GTS дает тур со стоимостью 14, а в гл. 1 мы нашли тур со стоимостью 13. Ясно, что алгоритм GTS не всегда находит тур с минимальной стоимостью.

Обычно грубые алгоритмы очень быстры и интуитивно привлекательны, но, как мы заметили, они не всегда работают *). Нам повезло,

) То есть не всегда дают оптимальное решение задачи.- Прим. ред.