Идея метода решения задачи

Массивы mG, mDP, mDM инициализируются значениями true, что означает: горизонтали свободны, «Плюс»–диагонали и «Минус»–диагонали также свободны.

Перебрать все принципиально различные способы расстановки ферзей можно следующим образом.

Предположим, что предпринимается попытка поставить на доску i –й по номеру ферзь (i = 1, 2, …, 8). Он ставится на i –ю вертикаль. Это возможно не более, чем 8 способами, все они перебираются с помощью цикла по переменной j. Попытка «удачна», если (i, j)–е поле не находится под ударом ранее поставленных ферзей, что показано значением true в элементах mG[ j ], mDP[ i + j ], mDM[ i – j ].

Если i < 8, метод, удачно реализовавший попытку, рекурсивно обращается к себе ради попытки поставить (i + 1)–й по номеру ферзь. Но важно отметить два момента. Перед рекурсивным вызовом в элементы массивов mG[ j ], mDP[ i + j ], mDM[ i – j ] заносится значение false, что означает: только что поставленный ферзь объявил «занятыми» свою горизонталь и обе свои диагонали. А после рекурсивного вызова в элементы массивов mG[ j ], mDP[ i + j ], mDM[ i – j ] вновь заносится значение true, что означает: ферзь снимается с доски.

Если i = 8, метод, удачно реализовавший попытку, показывает очередной вариант расстановки ферзей.

В предлагаемом варианте кода «занятость» горизонтали и диагоналей выражается значениями элементов массивов mG[j - 1], mDP[i + j - 2], mDM[i - j + 7]. «Смещение» индексов понадобилось для того, чтобы их минимально возможные значения были равны нулю. «Смещение» не потребовалось бы при написании кода на языке Pascal.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace CA20130926

{

class Program

{

private static ConsoleKeyInfo c;

private static int n;

private static bool[] mG;

private static bool[] mDP; // Диагонали, параллельные побочной

private static bool[] mDM; // Диагонали, параллельные главной

private static int[] mX;

static int PutNextQueen(int i)

{

int j, k, l, ReturnCode;

// Word почему-то изображает букву «эль» похожей на единичку.

for (j = 1; j <= 8; j++)

{

if (mG[j - 1] && mDP[i + j - 2] && mDM[i - j + 7])

{

mX[i - 1] = j;

if (i < 8)

{

mG[j - 1] = false;

mDP[i + j - 2] = false; mDM[i - j + 7] = false;

ReturnCode = PutNextQueen(i + 1);

// Ставим следующего ферзя на следующую горизонталь

if (ReturnCode == 27) return ReturnCode;

mG[j - 1] = true;

mDP[i + j - 2] = true; mDM[i - j + 7] = true;

}

else

{

for (k = 1; k <= 8; k++)

{

for (l = 1; l <= 8; l++)

if (l == mX[k - 1])

System.Console.Write(" X");

else

System.Console.Write(".");

System.Console.WriteLine();

}

System.Console.WriteLine();

n++;

if (n % 20 == 0)

// Останавливать вывод после показа очередной порции из 20 вариантов

{

c = Console.ReadKey();

if (c.Key == ConsoleKey.Escape)

{

System.Console.WriteLine("Нажата клавиша Escape");

System.Console.ReadKey();

return 27;

}

}

}

}

}

return 0;

}

static void Main(string[] args)

{

int ReturnCode;

mX = new int[8];

mG = new bool[8];

mDP = new bool[15]; // Диагонали, параллельные побочной

mDM = new bool[15]; // Диагонали, параллельные главной

for (n = 1; n <= 8; n++) mX[n - 1] = 0;

for (n = 1; n <= 8; n++) mG[n - 1] = true; // Горизонтали свободны

for (n = 2; n <= 16; n++) mDP[n - 2] = true; // Плюс-диагонали свободны

for (n = -7; n <= 7; n++) mDM[n + 7] = true; // Минус-диагонали свободны

n = 0;

ReturnCode = PutNextQueen(1);

// Ставим первого ферзя на первую горизонталь

if (ReturnCode == 27)

System.Console.Write("Счёт прерван. Построено вариантов: n={0}", n);

else

System.Console.Write("Счёт завершён. Построено вариантов: n={0}", n);

System.Console.ReadKey();

}

}

}

Рекурсивные алгоритмы (продолжение)

Пример.Дана матрица , состоящая из M строк и N столбцов. Элементы матрицы – неотрицательные числа. Пошаговое движение по элементам матрицы начинается от левого верхнего элемента и завершается правым нижним элементом . Каждый шаг движения должен быть сделан либо вправо (если текущий столбец – не последний), либо вниз (если текущая строка – не последняя). Постановка на очередной элемент матрицы оплачивается ценой, равной значению этого элемента.

Найти «самый дешёвый» из путей. Назвать его цену.

Решение будет построено двумя способами. Первый из них основан на рекурсии. Во втором применяется т.н. метод динамического программирования (и сравнивается с рекурсивным подходом).

Текст консольного приложения приводится полностью.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace ConsoleApplication1

{

public enum Directions

{

Nowhere,

Right,

Down

}

public struct CellType

{

public int nPrice;

public int nTimes;

public Directions direction;

}

class Program

{

private static int M;

private static int N;

private static CellType[,] mCell;

static int NextStep(int i, int j)

{

int iD, iR;

mCell[i, j].nTimes++;

iD = -1;

iR = -1;

if (i < M-1)

iD = mCell[i + 1, j].nPrice + NextStep(i + 1, j);

if (j < N-1)

iR = mCell[i, j + 1].nPrice + NextStep(i, j + 1);

if (iD >= 0 && iR >= 0)

{

if (iD < iR)

{

mCell[i, j].direction = Directions.Down;

return iD;

}

else

{

mCell[i, j].direction = Directions.Right;

return iR;

}

}

else

if (iD >= 0)

{

mCell[i, j].direction = Directions.Down;

return iD;

}

else

if (iR >= 0)

{

mCell[i, j].direction = Directions.Right;

return iR;

}

else

{

mCell[i, j].direction = Directions.Nowhere;

return 0;

}

}

static void Main(string[] args)

{

int i, j, iPrice;

int[,] mPrices = new int[,]

{

{0, 5, 6, 4, 3},

{3, 4, 7, 9, 8},

{6, 3, 2, 4, 7},

{8, 4, 1, 7, 0},

};

M = 4;

N = 5;

mCell = new CellType[M, N];

for (i = 0; i < M; i++)

{

for (j = 0; j < N; j++)

{

Console.Write(" {0}", mPrices[i, j]);

mCell[i, j].nPrice = mPrices[i, j];

mCell[i, j].nTimes = 0;

mCell[i, j].direction = Directions.Nowhere;

}

Console.WriteLine();

}

Console.WriteLine();

iPrice = NextStep(0, 0);

Console.WriteLine("{0}", iPrice);

for (i = 0; i < M; i++)

{

for (j = 0; j < N; j++) Console.Write(" {0}", mCell[i, j].direction);

Console.WriteLine();

}

Console.WriteLine();

for (i = 0; i < M; i++)

{

for (j = 0; j < N; j++) Console.Write(" {0:D}", mCell[i, j].nTimes);

Console.WriteLine();

}

Console.ReadKey();

}

}

}

Метод динамического программирования

Пример. Найти наиболее «дешевый» путь от элемента матрицы размера до элемента . Второй способ решения задачи.

Идея метода динамического программирования состоит в следующем. Для каждого элемента строится оптимальный путь от него до конца пути. Сначала это делается для всех элементов, которые в одном шаге от конца пути. Затем для всех элементов, которые в двух шагах от конца пути. Затем для всех элементов, которые в трёх шагах от конца пути. И так далее.

Пусть матрица цен имеет размер и выглядит так:

Пусть есть цена оптимального пути от элемента до конца пути.

Множество предпоследних элементов (1-я волна):

, двигаться можно только вниз;

, двигаться можно только вправо.

Множество «предпредпоследних» элементов (2-я волна):

, двигаться можно только вниз;

, двигаться лучше вправо;

, двигаться можно только вправо.

Множество «предпредпредпоследних» элементов (3-я волна):

, двигаться можно только вниз;

, двигаться лучше вниз;

, двигаться лучше вправо;

, двигаться можно только вправо.

Таким образом, можно найти цены и начальное направления оптимального пути для всех «волн», а значит, и для всех элементов матрицы, заканчивая элементом . Результат поиска показан в виде постановки при каждом элементе матрицы двух индексов: цена оптимального пути от этого элемента до конца (нижний индекс), направление оптимального пути от этого элемента (верхний индекс).

К документу прилагается архив проекта, реализующего оба способа поиска оптимального пути.

Дата добавления: 2013-12-13