Как найти все варианты программирование

Это история об информатике, алгоритмах и понимании мощи компьютеров.

Представим такую ситуацию: компания по продаже компьютеров хочет написать самую эффективную рассылку для своих клиентов. Маркетологи сказали, что в письме обязательно должно быть 4 блока:

предложение скидки;
анонс новых товаров;
блок с самыми популярными товарами;
рассказ о том, почему нужно выбрать именно эту компанию.

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

О чём речь

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

Скидка → анонс → популярное → рассказ
Рассказ → скидка → анонс → популярное
Анонс → рассказ → скидка → популярное

Таких вариантов можно составить 4! («четыре факториал») — то есть 24 штуки. Восклицательный знак означает факториал, то есть нам нужно перемножить все числа от 1 до этого числа:

4! = 1 × 2 × 3 × 4 = 24

Получается, из четырёх блоков можно сделать 24 разных варианта письма. Вручную перебирать их все сложно, да и нет смысла: компьютер с этим справится гораздо быстрее. Для этого и сделаем алгоритм.

В чём идея

Чтобы перебрать все варианты, можно сделать так:

Смотрим, сколько у нас блоков — 4 штуки.
Делаем первый цикл.
Делаем второй цикл.
Делаем третий цикл.
Делаем четвёртый вложенный цикл.
Внутри этого перебираем все варианты и каждый раз проверяем, чтобы один блок не встречался два раза или больше.
Если условие выполняется — добавляем результат в итоговые варианты
На выходе получаем все варианты.

Но это сложно: нам нужно заводить для каждого цикла свою переменную, а потом следить, чтобы они не перепутались между собой. А ещё нужно не забыть:

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

А можно подойти к вопросу иначе:

Берём массив с блоками.
Берём оттуда первый элемент, откладываем его в сторону и дальше пока работаем с оставшимся массивом.
В оставшемся массиве тоже берём первый элемент, откладываем его в сторону и снова работаем с оставшимся массивом.
Так погружаемся в массив до тех пор, пока в нём не останется ни одного элемента.
А теперь на каждом этапе возврата назад мы переставляем наш отложенный первый элемент на соседнее место и запоминаем получившуюся комбинацию.
Так на каждом шаге мы будем получать всё новые и новые комбинации перестановок — сначала это будут перестановки из двух элементов, потом из трёх и так далее.
Возвращаемся к пункту 2 и делаем то же самое со вторым элементом.
Так проходим все элементы до последнего.

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

На самом деле мы только что описали рекурсию: функцию, которая вызывает сама себя, но на каждом шаге с новыми условиями.

Почему рекурсия лучше вложенных циклов

Когда вложенных циклов мало, то с ними проще: можно контролировать всё вручную. А вот когда циклов становится не три, а 10 или 50, то сильно вырастает вероятность ошибиться в переменной или забыть про какое-то условие. В рекурсии такой проблемы нет: мы один раз описываем, как нырнуть и как оттуда вынырнуть, и всё, остальное компьютер сделает сам.

Ещё бывает такое, что мы заранее не знаем, сколько будет блоков для перестановок — 4 или 40, например. Рекурсия здесь тоже выигрывает: достаточно в одном цикле перебрать все элементы массива, а дальше всё сработает само.

Так и сделаем.

Алгоритм

Единственное, что нам понадобится нового для рекурсии, о чём мы ещё не говорили, — это мемоизация.

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

В нашем случае за это будет отвечать такая строчка:

var memo = memo || [];

Она появляется в самом начале рекурсии и означает вот что:

Если в переменной memo уже что-то было — используется то, что было.
Если на момент запуска рекурсии в этой переменной ничего не было — создаётся пустой массив.

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

Теперь смотрите код и читайте комментарии:

var email = ['скидка', 'анонс', 'популярное', 'рассказ'];

// массив для результатов перестановок
var results = [];

// рекурсивная функция
// на вход получает текущий массив и массив с памятью предыдущих вычислений
function permute(arr, memo) {
  // переменная для хранения фрагмента массива
  var cur;

  // делаем переменную для хранения промежуточных результатов
  // в программировании это называется «мемоизация»
  var memo = memo || [];

  // какой размер входного массива — такой длины и делаем цикл, чтобы перебрать все элементы
  for (var i = 0; i < arr.length; i++) {

    // получаем новый массив cur, удаляя из входного массива один элемент, начиная с текущей позиции
    // при этом из входного массива этот элемент тоже удалится
    cur = arr.splice(i, 1);

    // если от входного массива ничего не осталось
    if (arr.length === 0) {
      // то приклеиваем текущее значение нарезки к варианту, который лежит в памяти, 
      // и добавляем получившийся результат в итоговый массив
      results.push(memo.concat(cur));
    }

    // вызываем новый виток рекурсии
    // в качестве аргументов передаём копию входящего массива и добавляем к кешу памяти то, что получилось после удаления одного символа из входящего массива
    permute(arr.slice(), memo.concat(cur));

    // возвращаем в исходный массив первый элемент из нового массива, но уже на другую позицию
    arr.splice(i, 0, cur[0]);
  }

  // возвращаем обратно массив с результатами перестановок
  return results;
}

permute(email);

Запустим код в консоли браузера:

Видно, что мы получили 24 перестановки, как и должно было быть. Они все разные, ни в одной нет повторений — то, что нам нужно. Теперь можно отдать эти последовательности дальше, чтобы по каждой из них собрали своё письмо для клиентов.

Если интересно, как рекурсия справится со сложными вариантами и сколько их получится, — сделайте в исходном массиве в коде не 4, а 10 элементов.

Что дальше

Попробуем использовать этот же подход в задаче коммивояжёра — там тоже есть много вложенных циклов. Должно сработать.

Вёрстка:

Кирилл Климентьев

Источник

Вариант 1 – полный рекурсивный перебор. Есть одна рекурсивная функция, которой передается следующее число, текущая сумма и текущий список взятых чисел. Функция или берет следующее число или пропускает его и вызывается рекурсивно для следующего числа. Если сумма слишком большая – просто возвращается сразу. Если сумма равна n – выводит текущие числа и возвращается.

Можно хранить список взятых чисел в глобальном массвие/списке. Но надо аккуратно его откатывать. Перед рекурсивным вызовом, если добавили новое число, то после вызова его из массива/списка удалите. Так будет потребление памяти O(n) вместо O(n^2).

Что-то типа такого:

void Generate(int n, int next, int sum, vector<int> taken) {
  if (next > n || sum > n) return;
  if (sum == n) {
   Output(taken);
  }
  Generate(n, next+1, sum, taken);
  taken.push_back(next);
  Generate(n, next+1, sum+next, taken);
}

...

Generate(n, 1, 0, {});

Но это решение будет не самым быстрым – ибо оно будет заходить в длинные “тупики”.

Вариант 2 – оптимизированный перебор, который не перебирает ничего лишнего. Сначала, как в задаче о рюкзаке, при решении динамическим программированием, найдем все варианты набрать каждую сумму.

Заведите двумерный массив n x (n+1). d[i][j] будет хранить, можно ли собрать сумму j используя числа от 1 до i.

База – d[0][0] = true (нет чисел – ноль набрать можно), d[i][0] = false (нет чисел. Не ноль набрать нельзя).

пересчет: d[i][j] = d[i-1][j-i] or d[i-1][j] (или берем текущее число или нет)
Естественно, первый вариант рассматривается только если i<=j. Можно подсчитать этот массив или рекурсивной функцией с запоминанием или просто тупо двумя вложенными циклами.

Потом модифицируем нашу рекурсивную функцию из первого варианта. Теперь она будет как бы идти с конца и параметры будут – сколько первых чисел мы можем использовать, какую сумму должны набрать и какие бОльшие числа уже взяли. В функции опять 2 варианта – или берем текущее число или нет. Но при этом смотрим в массиве d[][], а можем ли мы вообще набрать нужную сумму данными нам числами. Если нет – сразу возвращаемся. Когда пришли к оставшейся сумме в 0, выводим набранные числа.

Оба решения имеют временную сложность O(2^n), но второе будет в несколько раз быстрее, потому что не перебирает никаких тупиков. Возможно, если еще подумать можно избваиться от динамического программирования и вообще вывести формулу, когда из чисел от 1 до i можно собрать заданное число k (может там формула типа i*(i+1)/2 <= k).

Если у вас задача стоит не вывести все наборы (их много! Порядка 2^n), а подсчитать их количество, то тут не надо рекурсивного перебора, а можно подифицировать динамическое программирование, которое будет вместо true/false считать сколько способов собрать из i чисел сумму j. будет формула вида d[i][j] = d[i-1][j] + d[i-1][j-i]. Тогда все решение будет за O(n^2) по времени и можно сделать его O(n) по памяти, если немного подумать (и хранить только две или одну строку матрицы d).

Источник

Перестановка – это комбинация элементов из N разных элементов взятых в определенном порядке. В перестановке важен порядок следования элементов, и в перестановке должны быть задействованы все N элементов.

Задача: Найти все возможные перестановки для последовательности чисел 1, 2, 3.
Существуют следующие перестановки:

1: 1 2 3
2: 1 3 2
3: 2 1 3
4: 2 3 1
5: 3 1 2
6: 3 2 1

Перестановки без повторений

Количество перестановок для N различных элементов составляет N!. Действительно:

на первое место может быть помещен любой из N элементов (всего вариантов N),
на вторую позицию может быть помещен любой из оставшихся (N-1) элементов (итого вариантов N·(N-1)),
если продолжить данную последовательность для всех N мест, то получим: N·(N-1)·(N-2)· … ·1, то есть всего N! перестановок.

Рассмотрим задачу получения всех перестановок чисел 1…N (то есть последовательности длины N), где каждое из чисел входит ровно по 1 разу. Существует множество вариантов порядка получения перестановок. Однако наиболее часто решается задача генерации перестановок в лексикографическом порядке (см. пример выше). При этом все перестановки сортируются сначала по первому числу, затем по второму и т.д. в порядке возрастания. Таким образом, первой будет перестановка 1 2 … N, а последней — N N-1 … 1.

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

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

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

Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <iostream>
using namespace std;
void swap(int *a, int i, int j)
{
  int s = a[i];
  a[i] = a[j];
  a[j] = s;
}
bool NextSet(int *a, int n)
{
  int j = n – 2;
  while (j != -1 && a[j] >= a[j + 1]) j–;
  if (j == -1)
    return false; // больше перестановок нет
  int k = n – 1;
  while (a[j] >= a[k]) k–;
  swap(a, j, k);
  int l = j + 1, r = n – 1; // сортируем оставшуюся часть последовательности
  while (l<r)
    swap(a, l++, r–);
  return true;
}
void Print(int *a, int n)  // вывод перестановки
{
  static int num = 1; // номер перестановки
  cout.width(3); // ширина поля вывода номера перестановки
  cout << num++ << “: “;
  for (int i = 0; i < n; i++)
    cout << a[i] << ” “;
  cout << endl;
}
int main()
{
  int n, *a;
  cout << “N = “;
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = i + 1;
  Print(a, n);
  while (NextSet(a, n))
    Print(a, n);
  cin.get(); cin.get();
  return 0;
}

Результат выполнения

Перестановки с повторениями

Особого внимания заслуживает задача генерации перестановок N элементов в случае если элементы последовательности могут повторяться. Допустим, исходная последовательность состоит из элементов n₁, n₂… n_k, где элемент n₁ повторяется r₁ раз, n₂ повторяется r₂ раз и т.д. При этом n₁+n₂+…+n_k=N. Если мы будем считать все n₁+n₂+…+n_k элементов перестановки с повторениями различными, то всего различных вариантов перестановок (n₁+n₂+…+n_k)! . Однако среди этих перестановок не все различны. В самом деле, все r₁ элементов n₁ мы можем переставлять местами друг с другом, и от этого перестановка не изменится. Точно так же, можем переставлять элементы n₂, n₃ и т. д. В итоге имеем r₁! вариантов записи одной и той же перестановки с различным расположением повторяющихся элементов n₁. Таким образом, всякая перестановка может быть записана r₁!·r₂!·…·r_k! способами. Следовательно, число различных перестановок с повторениями равно

Для генерации перестановок с повторениями можно использовать алгоритм генерации перестановок без повторений, приведенный выше. Введем повторяющийся элемент в массив a. Ниже приведен код программы для генерации перестановок с повторениями (изменен только код функции main()).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include <iostream>
using namespace std;
void swap(int *a, int i, int j)
{
  int s = a[i];
  a[i] = a[j];
  a[j] = s;
}
bool NextSet(int *a, int n)
{
  int j = n – 2;
  while (j != -1 && a[j] >= a[j + 1]) j–;
  if (j == -1)
    return false; // больше перестановок нет
  int k = n – 1;
  while (a[j] >= a[k]) k–;
  swap(a, j, k);
  int l = j + 1, r = n – 1; // сортируем оставшуюся часть последовательности
  while (l<r)
    swap(a, l++, r–);
  return true;
}
void Print(int *a, int n)  // вывод перестановки
{
  static int num = 1; // номер перестановки
  cout.width(3); // ширина поля вывода номера перестановки
  cout << num++ << “: “;
  for (int i = 0; i < n; i++)
    cout << a[i] << ” “;
  cout << endl;
}
int main()
{
  int n, *a;
  cout << “N = “;
  cin >> n;
  a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = i + 1;
  a[1] = 1; // повторяющийся элемент
  Print(a, n);
  while (NextSet(a, n))
    Print(a, n);
  cin.get(); cin.get();
  return 0;
}

Результат работы приведенного выше алгоритма:

Назад: Алгоритмизация

Источник

Не уверен, что правильно понял задачу, поскольку у меня на данной последовательности чисел 42 не получается. Но ответ на всякий случай напишу.

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

На Python’е это выглядит вот так:

#!/usr/bin/python

numbers = [2, 9, 3, 6, 3, 8, 1, 10, 6, 7]

def combinations(selected=[], nexts=numbers):
    subtotal = 0
    for i, n in enumerate(nexts):
        if sum(selected) + n > 8:
            # print selected+[n]
            subtotal += 1
        else:
            subtotal += combinations(selected+[n], nexts[i+1:])
    return subtotal

print combinations()

Источник

2.3. МЕТОДЫ СИНТЕЗА ВАРИАНТОВ РЕАЛИЗАЦИЙ ПРОГРАММ

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

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

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

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

Метод проб и ошибок — это последовательное выдвижение и рассмотрение идей. Человек, сталкиваясь с проблемой, многократно мысленно ищет ответ, перебирает варианты и, наконец, находит решение. Десятки, сотни, тысячи попыток на протяжении дней, недель, лет. В конце концов в большинстве случаев решение находится. В программировании этот метод традиционно применяется для оптимизации архитектуры систем и структуры программ.

Главный недостаток метода проб и ошибок — это, во-первых, медленное генерирование новых идей, а во-вторых, отсутствие защиты от психологической инерции, т. е. выдвижение идей тривиальных, обыденных, неоригинальных.

Следующим шагом в совершенствовании технологии явился переход к направленным методам поиска решений, которые базируются на раскрытии и описании процесса решения, представлении его в виде некоторого эвристического алгоритма. Направленность эвристических методов — “раскачать” мышление, помочь по-новому увидеть задачу, преодолеть стереотипы.

Если, решая конкретную задачу, проектировщик не ограничится достижением только сиюминутной цели, а сможет “заглянуть в будущее” и выделить инвариантные части системы, то эти части, являясь как бы строительным материалом для данной системы, могут послужить основой и для систем, которые еще будут проектироваться. Будущие системы могут решать совсем иные задачи. В этой связи полезно было бы создавать и накапливать библиотеки инвариантных частей системы или даже параллельно проектировать несколько систем (объектов), преследующих как сходные, так и различные цели. “Заглянуть в будущее” можно лишь хорошо зная прошлое и настоящее, а также новые достижения программирования.

Целенаправленные методы творчества вполне применимы не только к техническим системам, но и программным. Рассмотрим наиболее известные из них, а также их возможное применение как при коллективном, так и индивидуальном использовании.

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

При успешном решении какой-либо творческой задачи человек получает два результата — само решение поставленной задачи и методический опыт, т. е. уяснение процесса решения данной конкретной задачи. Но проблема заключается в том, что решение одной задачи нельзя просто перенести на решение другой. Поэтому только после решения определенного числа задач у человека появлялся набор правил, указаний или приемов решения той или иной задачи. Такие методические правила называют эвристическими приемами.

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

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

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

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

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

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

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

Однако предпочтительным является иной вариант действий. Как показывает опыт, во многих ситуациях содержатся скрытые ресурсы, использование которых позволяет кардинальным образом разрешить противоречие. Такими скрытыми ресурсами во многих случаях являются три вида ресурсов: временные, пространственные и “бросовые”. К “бросовым” мы относим ресурсы, имеющиеся в системе (но, как правило, не считающиеся ресурсом, по крайней мере, в рамках решаемой задачи), использование которых не связано с какими-то дополнительными затратами.

Наиболее продуктивные способы разрешения противоречий — разнесение их во времени, пространстве или использование “бросовых” ресурсов. Эти общие рекомендации могут иметь различную трактовку в конкретных ситуациях.

Целесообразность использования метода эвристических приемов для постановки задач разработки программ проверена педагогической практикой авторов. Зачастую достаточно короткой подсказки обучаемым в виде эвристического приема, чтобы они самостоятельно правильно сформулировали задачу.

Используя фонд эвристических приемов, Б.С. Воинов и В.В. Костерин успешно синтезировали ряд новых механизмов алгоритма поиска глобального экстремума функций многих переменных на сетке кода Грея.

Пример использования метода эвристических приемов для создания алгоритмов описан в книге Д. Пойа. Укороченный фонд эвристических приемов для программирования описан в приложении 3.

Метод мозгового штурма — один из популярных методов коллективного творчества. Его психологическая основа — взаимная стимуляция мышления в группе. Конкуренция между людьми за количество выдвинутых идей делает этот метод более эффективным по сравнению с работой каждого отдельного человека вне группы. Метод мозгового штурма является по сути тем же методом проб и ошибок, однако он создает условия для психологической активизации творческого процесса, снижает инерцию мышления, чему особенно способствует наличие в группе людей со стороны. Метод прост, доступен и эффективен. Реализация метода выглядит следующим образом.

Решение проводится в два этапа — генерации и анализа. На этапе генерации создается творческая группа из 5—15 человек (специалисты-смежники и люди “со стороны”, не имеющие никакого опыта в области, к которой относится решаемая задача). Группе объясняется суть задачи, требующей решения, и проводится этап генерации идей. На этом этапе не допускается критика предлагаемых идей. Поощряется выдвижение даже сумасбродных идей. Затем группа экспертов анализирует высказанные идеи и отбирает те, которые заслуживают более тщательной проработки.

Методом мозгового штурма работают команды знатоков в популярной телепередаче: “Что? Где? Когда?” Пятьдесят секунд идет генерация идей и только десять секунд тратится на обсуждение выдвинутых идей.

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

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

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

Согласно проведенному опросу, большинство профессиональных программистов именно этим методом генерировали внешний облик своих программных систем и определили способы реализации многих функций программ.

Метод морфологических таблиц является простым и эффективным особенно там, где необходимо найти большое число вариантов достижения цели. В последнее время он используется достаточно широко как средство развития творческого воображения. Метод по сути аналогичен сборке разных вариантов дома из кубиков деревянного конструктора и заключается в том, что для интересующего нас объекта формируется набор отличительных признаков: наиболее характерных подсистем, свойств или функций. Затем для каждого из них определяются альтернативные варианты реализации (детали конструктора). Комбинируя альтернативные варианты, можно получить множество различных решений. Анализируя их, выделяют предпочтительные варианты.

Примером морфологической таблицы является прайс-лист компьютерной фирмы. В прайс-листе содержится информация о нескольких типах корпусов ЭВМ; материнских плат; процессоров и т. д. Каждая часть снабжена техническими характеристиками и ценой. Не все варианты частей могут быть состыкованы между собой. Главное, что характеризует прайс-лист, — это отсутствие критерия качества целого компьютера для конкретного пользователя. Глядя на прайс-лист, надо синтезировать данный критерий и выбрать оптимальный состав частей. Как результат синтеза могут быть выявлены варианты построения компьютеров, ориентированных на различные категории пользователей.

Трудность здесь такая же, как и в ситуации подбора одежды для девушки. Если ознакомиться с товаром в ряде магазинов, то нетрудно по рекомендации “лучшее — дорогое” купить отдельные элементы гардероба. Скорее всего эти “лучшие” элементы не будут в целом смотреться на девушке из-за несовместимости цветов, фасона, да и самого облика и характера девушки, т. е. отсутствует оптимизация по критерию целого.

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

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

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

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

В 1983 г. В.В. Костериным была успешно применена морфологическая таблица для синтеза идей построения алгоритма нелинейного программирования поиска глобального экстремума функций многих переменных на сетке кода Грея. Алгоритмы нелинейного программирования предназначены для поиска экстремумов функций многих переменных. В методах прямого поиска экстремум выявляется путем расчета множества точек функции при аргументах, определяемых самим алгоритмом поиска. В табл. 2.2 приведена данная морфологическая таблица, которая содержит классификационные признаки отдельных механизмов алгоритмов нелинейного программирования на уровне основных принципов. Приведенные классификационные признаки выделялись по основным функциональным признакам отдельных механизмов. Каждому классификационному признаку соответствует множество реализаций механизмов в виде значений классификационных признаков.

Интересно отметить, что число возможных реализаций алгоритмов нелинейного программирования по этой таблице составляет N = 5*6*8*5*7*7*6 = 352800, что значительно превышает число опубликованных методов (около 2000)!

Таблица 2.2

Морфологическая таблица принципов функционирования алгоритмов нелинейного программирования

Классификационные признаки
Значения классификационных признаков

Начальная точка поиска
1.1
1.2
1.3
1.4
1.5

Зондирование гиперповерхности
2.1
2.2
2.3
2.4
2.5
2.6

Стратегия шагов поиска
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8

Направление поиска на шаге
4.1
4.2
4.3
4.4
4.5

Стратегия шага поиска
5.1
5.2
5.3
5.4
5.5
5.6

Механизм самообучения
6.1
6.2
6.3
6.4
6.5
6.6
6.7

Механизм завершения поиска
7.1
7.2
7.3
7.4
7.5
7.6

Значения классификационных признаков классификационного признака “Механизм начальной точки поиска”:

признак 1.1 — из точки, указанной пользователем;

признак 1.2 — из средней точки области определения;

признак 1.3 — из точки на границе области определения;

признак 1.4 — из случайной начальной точки поиска;

признак 1.5 — начальная точка поиска не задается.

Значения классификационных признаков классификационного признака “Первичное зондирование гиперповерхности”:

признак 2.1 — в виде большого числа случайных точек, зондирующих всю гиперповерхность;

признак 2.2 — поочередные спуски из ряда случайных начальных точек;

признак 2.3 — конкурирующие спуски из добавляемых случайных точек;

признак 2.4 — зондирование гиперповерхности случайными точками с выявлением и более тщательным исследованием “подозрительных областей”;

признак 2.5 — сканирование всей гиперповерхности с использованием различных разверток, например Пеано;

признак 2.6 — отдельный механизм начала поиска отсутствует.

Значения классификационных признаков классификационного признака “Стратегия шагов поиска”:

признак 3.1 — один шаг;

признак 3.2 — последовательные шаги до выявления экстремума;

признак 3.3 — осуществлять все шаги по одному и тому же механизму;

признак 3.4 — переключать механизмы шагов от глобального метода до локального;

признак 3.5 — переключать механизмы шагов от глобальных далее до усредненных и до локальных;

признак 3.6 — переключать механизмы шагов по эвристическим правилам;

признак 3.7 — малое количество последовательных шагов из ограниченного ряда лидирующих конкурирующих начальных точек;

признак 3.8 — шаги поиска отсутствуют.

Значения классификационных признаков классификационного признака “Направление поиска на шаге”:

признак 4.1 — новая точка в направлении аппроксимации градиента, построенного на основе данных текущей и предшествующей пробной точек;

признак 4.2 — по результатам обработки небольшого числа перспективных точек, полученных на предшествующих шагах;

признак 4.3 — по результатам анализа функции, аппроксимирующей случайные точки в перспективном направлении;

признак 4.4 — зондирование гиперповерхности большим количеством случайных точек и последующим построением аппроксимирующей функции;

признак 4.5 — вдоль границы области определения целевой функции;

признак 4.6 — механизм отсутствует.

Значения классификационных признаков классификационного признака “Механизм стратегии шага поиска”:

признак 5.1 — пробные точки только на расстоянии предполагаемого экстремума;

признак 5.2 — пробные точки на большем расстоянии, чем предполагаемый экстремум;

признак 5.3 — пробные точки на расстоянии, несколько меньшем, чем у предполагаемого экстремума;

признак 5.4 — объединение признаков 5.1 и 5.2;

признак 5.5 — объединение признаков 5.1, 5.2 и 5.3;

признак 5.6 — совмещение поиска направления и расстояния до экстремума;

признак 5.7 — разделение поиска направления и расстояния до экстремума.

Значения классификационных признаков классификационного признака “Механизм самообучения”:

признак 6.1 — сужение границ поиска по мере продвижения к экстремуму;

признак 6.2 — постепенное повышение точности поиска;

признак 6.3 — выявление формы гиперповерхности по результатам предшествующих шагов и переход на специальный механизм уточнения экстремума;

признак 6.4 — выявление формы гиперповерхности по результатам предшествующих шагов и переход на специальный механизм продвижения вдоль оврагов;

признак 6.5 — выявление формы гиперповерхности по результатам предшествующих шагов и отказ от текущего найденного экстремума;

признак 6.6 — изменение плотности вероятности случайных точек для разных зон поиска;

признак 6.7 — механизм отсутствует.

Значения классификационных признаков классификационного признака “Механизм завершения поиска”:

признак 7.1 — не выявляется направление улучшения функции на следующем шаге;

признак 7.2 — израсходован ресурс времени;

признак 7.3 — достигнуто заранее заданное значение целевой функции;

признак 7.4 — исчерпаны возможности алгоритма поиска экстремума;

признак 7.5 — выполнено заранее заданное количество шагов поиска;

признак 7.6 — нет улучшений в “дальней” и “близкой” окрестностях.

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

Оболочки визуального программирования, например Delphi, реализуют метод морфологического синтеза при построении форм диалога программ на основе визуальных компонент.

О чём речь

В чём идея

Почему рекурсия лучше вложенных циклов

Алгоритм

Что дальше

Перестановки без повторений

Перестановки с повторениями

Читайте также

Сравнение старой и новой реализаций

4.5. Отношения на диаграмме вариантов использования

4.6. Пример построения диаграммы вариантов использования

4.7. Рекомендации по разработке диаграмм вариантов использования

6.16.8 Конец списка вариантов и отсутствие операций

6.16.9 Кодирование вариантов

Предложите пару вариантов на выбор

7. Выбор вариантов

Использование операторов if для выбора вариантов

Изменчивость Реализаций (Implementation Variation)

Интерфейс и повторное использование реализаций

Слово в защиту реализаций

Добавить комментарий Отменить ответ

О чём речь

В чём идея

Почему рекурсия лучше вложенных циклов

Алгоритм

Что дальше

Перестановки без повторений

Перестановки с повторениями

Читайте также

Сравнение старой и новой реализаций

4.5. Отношения на диаграмме вариантов использования

4.6. Пример построения диаграммы вариантов использования

4.7. Рекомендации по разработке диаграмм вариантов использования

6.16.8 Конец списка вариантов и отсутствие операций

6.16.9 Кодирование вариантов

Предложите пару вариантов на выбор

7. Выбор вариантов

Использование операторов if для выбора вариантов

Изменчивость Реализаций (Implementation Variation)

Интерфейс и повторное использование реализаций

Слово в защиту реализаций

Вам также может понравиться

Как найти переписку в архиве ватсап

Как составить акт возврата пример

Как составить претензию на возврат бытовой техники

Добавить комментарий Отменить ответ