16

Речь идет о прикладной задаче: словаре неисправностей (в качестве осей там значатся частота и номер неисправности).

Таблица выглядит так (см вложения). введите описание изображения здесь

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

При этом в отдельные группы выделяются неисправности(строки), которые совпадают друг с другом (они считаются неразличимыми и не учитываются в общем алгоритме). Быть может кто-то подскажет, какой алгоритм можно для этого использовать или у кого-то есть на примете что-то готовое?

PS - один из примеров решений - для данного словаря - это три частоты (столбцы затенены). Ссылка на статью, в которой я разбираю данную проблематику - https://bib.irb.hr/datoteka/11551.ICECS96.pdf Статья на английском, раздел 3.3 занимается вопросом оптимизации.

8
  • Внутреннее ощущение, что это NP-какая-то-там задача и целесообразно искать или точное решение для маленькой размерности задачи (всего немного частот и сбоев), или приблизительное, эвристическое решение большой задачи.
    – _Vi
    8 апр 2015 в 11:38
  • @_Vi, дело в том, что эта задача точно решается. Я разбираю иностранную статью, где это делается как процедура "по умолчанию" (само собой разумеющееся) - и к ее результатам применяется еще одна группа методов. Там подразумевается, что это подойдет для любой аналогичной задачи (таблицы неисправности с другой размерностью) 8 апр 2015 в 11:40
  • Я бы, наверное, использовал что-то типа перебора или генетического алгоритма или ещё какую-нибудь эвристику, не нацеливаясь на самое оптимальное решение в 100% случаев.
    – _Vi
    8 апр 2015 в 11:41
  • Можете разместить также ссылку на ту статью. Может там будут какие-то дополнительные наводки.
    – _Vi
    8 апр 2015 в 11:43
  • @_Vi, добавила в текст вопроса ссылку на статью и раздел, в котором обсуждается данная проблема 8 апр 2015 в 11:49

4 ответа 4

12
+50

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

Посмотрите алгоритмы для поиска «minumal unique column combination». Похоже, они делают именно то, что вам нужно.

Heise A. et al. Scalable Discovery of Unique Column Combinations — Описание Ducc, одного из таких алгоритмов.

Abedjan Z., Naumann F. Advancing the Discovery of Unique Column Combinations — Описание алгоритма HCA

10

Будем накапливать варианты таким образом:

Идем по списку ошибок, считая что у нас есть не более i ошибок. Смотрим какие столбцы определяют однозначно ошибку.

Например, если у нас есть одна (#0) ошибка, ее определить можно по любому столбцу. Заносим в список вариантов решения массивы из одного элемента по каждому столбцу: [[47],[50],[52],...[71]].

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

На третей итерации, нас не удовлетворяет 58 столбец, т.к. там идет повтор пятерки. Для 58-го столбца нам понадобится еще один столбец, в данном случае любой. Заменяем [58] на пары, в итоге получаем: [[47],[50],[52],[47,58],...[58,71],...[71]].

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

Также возможна ситуация, когда добавление одного столбца может быть недостаточно и придется пытаться добавлять два и более. В частности такая ситуация возникнет для ошибок, которые нельзя идентифицировать по имеющимся значениям (#10,#11 и т.д.) - логично исключить эти ошибки заранее.

Оптимальными наборами столбцов окажутся естественно те, длина которых меньше. Вот если бы было только первых пять ошибок, достаточно было бы одного из столбцов 52,53,54,67 или 71. Для шести первых ошибок уже одного столбца было бы недостаточно, были бы пары...

Иллюстрация предложенного алгоритма:

function go(maxColumnsCount) {
  var results = [];
  for (var er = 0; er < errors.length; er++) {
    if (!results.length) {
      // первоначальное заполнение
      for (var c = 0; c < colcount; c++) {
        results.push([c]);
      }
    } else {
      var newResults = [];
      for (var r = 0; r < results.length; r++) {
        // проверяем существующие кандидаты на валидность для следующей ошибки
        if (isUnique(results[r], newResults) && checkCollisions(results[r], er)) {
          newResults.push(results[r]);
        } else {
          for (var i = 0; i < colcount; i++) {
            var candidateresult = results[r].slice();
            if (candidateresult.length < maxColumnsCount && candidateresult.indexOf(i) < 0) {
              candidateresult.push(i);
              if (isUnique(candidateresult, newResults) && checkCollisions(candidateresult, er)) {
                newResults.push(candidateresult);

              }

            }
          }
        }
      }
      if (newResults.length) {
        results = newResults;
      } else {
        logIt("error cannot be indentified [" + er + "]:" + errors[er]["name"]);
      }
    }
    //logIt(JSON.stringify(results));
  }
  logIt(JSON.stringify(results));
}

function checkCollisions(res, row) {
  var values = [];
  for (var r = 0; r < res.length; r++) {
    values.push(errors[row]["f"][res[r]]);
  }
  for (var cr = 0; cr < row; cr++) {
    var same = true;
    for (var v = 0; v < values.length; v++) {
      if (values[v] != errors[cr]["f"][res[v]]) {
        same = false;
        break;
      }
    }
    if (same) return false;
  }
  return true;
}

function isUnique(candidate, results) {
  candidate.sort(function(a, b) {
    return a - b
  });
  for (var r = 0; r < results.length; r++) {
    if (candidate.length == results[r].length) {
      var same = true;
      for (var c = 0; c < candidate.length; c++) {
        if (candidate[c] != results[r][c]) {
          same = false;
          break;
        }
      }
      if (same) {
        return false;
      }
    }
  }
  return true;
}
var errors = [{
  "name": "R1A+",
  "f": [1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
}, {
  "name": "R1A-",
  "f": [5, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7]
}, {
  "name": "R2A+",
  "f": [6, 6, 6, 6, 6, 6, 5, 5, 5, 0, 0, 0]
}, {
  "name": "R2A-",
  "f": [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1]
}, {
  "name": "R3A+",
  "f": [1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3]
}, {
  "name": "R3A-",
  "f": [1, 0, 0, 0, 0, 5, 6, 7, 8, 8, 8, 8]
}, {
  "name": "R4A+",
  "f": [2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2]
}, {
  "name": "R4A-",
  "f": [7, 7, 7, 7, 7, 8, 8, 8, 7, 7, 7, 7]
}, {
  "name": "R5A+",
  "f": [6, 7, 7, 8, 8, 8, 8, 8, 8, 7, 7, 6]
}, {
  "name": "R5A-",
  "f": [3, 3, 3, 4, 4, 4, 4, 4, 4, 3, 3, 3]
}, {
  "name": "R1B+",
  "f": [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]
}, {
  "name": "R1B-",
  "f": [5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7]
}, {
  "name": "R2B+",
  "f": [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
}, {
  "name": "R2B-",
  "f": [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
}, {
  "name": "R3B+",
  "f": [1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2]
}, {
  "name": "R3B-",
  "f": [5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7]
}, {
  "name": "R4B+",
  "f": [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
}, {
  "name": "R4B-",
  "f": [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
}, {
  "name": "R5B+",
  "f": [5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
}, {
  "name": "R5B-",
  "f": [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
}, {
  "name": "C1A+",
  "f": [7, 8, 8, 8, 8, 7, 6, 0, 1, 2, 2, 2]
}, {
  "name": "C1A-",
  "f": [2, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 0]
}, {
  "name": "C2A+",
  "f": [2, 3, 3, 3, 3, 4, 4, 4, 4, 3, 3, 3]
}, {
  "name": "C2A-",
  "f": [0, 0, 0, 0, 0, 5, 6, 7, 8, 8, 8, 8]
}, {
  "name": "C1B+",
  "f": [5, 5, 5, 5, 5, 0, 0, 0, 1, 1, 1, 1]
}, {
  "name": "C1B-",
  "f": [1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 5]
}, {
  "name": "C2B+",
  "f": [2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
}, {
  "name": "C2B-",
  "f": [6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8]
}];
var colcount = errors[0]["f"].length;

document.getElementById("go").addEventListener("click", function() {
  go(parseInt(document.getElementById("maxCol").value) || 3);
});
document.getElementById("clear").addEventListener("click", function() {
  document.getElementById("log").value = "";
});

function logIt(msg) {
  var memo = document.getElementById("log");
  memo.value = memo.value + "\n" + msg;
}
html,
body {
  height: 100%;
  margin: 0;
  padding: 0
}
#log {
  height: 100%;
  width: 100%;
  border: 0;
  padding: 0
}
#maxCol {
  position: absolute;
  top: 10px;
  right: 100px;
}
#go {
  position: absolute;
  top: 10px;
  right: 50px
}
#clear {
  position: absolute;
  top: 30px;
  right: 50px
}
<textarea id="log"></textarea>
<input type="text" id="maxCol" value="3" placeholder="Максимальное количество колонок">
<button id="go">go</button>
<button id="clear">clear log</button>

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

9
  • обновил ответ, добавил реализацию на javascript'е. есть простор для оптимизации. еще куда-то закралась ошибка - не все неидетифицируемые ошибки отображает. ну главное - идея. 15 апр 2015 в 20:05
  • jsfiddle.net/ufgq4xeh 15 апр 2015 в 20:10
  • Спасибо. Мне ваш вариант алгоритма понравился больше всего(тк легок для понимания). Я на c# это описала, но у меня уже на 6 строке выходит количество комбинаций более 6 миллионов - и дальше крашится с outOfMemory, к сожалению( Попробовала добавить верхнюю границу (количество столбцов максимальное) - но у меня не получается даже с "5", хотя решение вроде - 3 столбца) *на вход методу я передаю сразу набор строк, которые только уникально различимы. **PS - Хотя, ваша реализация выдает верный результат даже на 3х столбцах) Жаль, что я плохо разбираюсь в javascript 16 апр 2015 в 8:20
  • @alena_fox_spb попробуйте выложить ваш вариант на ideone.com например. я с C# не работаю, с нуля написать не смогу, но посмотреть в чем может быть ошибка проще. Может быть другие участники также смогут помочь. 16 апр 2015 в 11:10
  • вот я попыталась переделать ваш код в аналог на C# - ideone.com/bsYI3p . Для примера взяла не 28, а 20 (уникальные строки) - и в качестве ответа на выходе только (0,1,11). Я глазами просмотрела - вроде эта тройка идентифицирует строки, но куда потерялись варианты [[0,5,11],[0,6,11]] - которые я могла получать с помощью вашего кода - не могу понять =( 16 апр 2015 в 12:31
6

Первое, что пришло в голову -- попробуйте такую идею.

Сначала выбросим все строки, которые однозначно не идентифицируются всем набором столбцов.

Для оствшихся.

Для каждого столбца i найдем A[i] -- количество разных значений. Рассортируем столбцы по убыванию A[i].

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

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

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

4
  • Сходу, опровергающий пример: 5 столбцов, 5 строк. В первом столбце различны 4 первые строки, во-втором столбце различны 3 первые строки и т.д. В последнем столбце различны строки 4 и 5. Т.е. по-хорошему надо выбрать столбцы 1 и 5, но по вашему алгоритмы будут задействованы все столбцы. Поэтому надо после каждого шага выбрасывать (точнее - склеивать) те строки, которые уже идентифицированы и снова находить различия в столбцах. Хотя и этот алгоритм вроде не оптимален - несколько столбцов будут иметь одинаковые различия, но оптимальными из них будут только несколько из них.
    – BOPOH
    11 апр 2015 в 5:50
  • Например, на наборе (1, 1, 2), (1, 1, 4), (2, 3, 4), (2, 3, 2) У каждого столбца по два различия. Выбираем первый столбец - ни один столбец однозначно не идентифицировали, ничего не выбрасываем. Берем дальше второй столбец (у него тоже по два различия) - ничего не изменилось. Берем третий столбец - каждая строка идентифицирована. А если бы на втором шаге сразу взяли бы третий столбец - тогда сразу бы идентифицировали все записи. Проблема в том, что хотя второй столбец и содержит разные значения, но строки, разбитые на группы по первому столбцу, во втором столбце имеют одни и те же значения.
    – BOPOH
    11 апр 2015 в 6:02
  • @BOPOH, любые усовершенствования приветствуются. Только в `(2, 3, 4) различий уже вообще нет, т.е. он на очередном шаге и будет выбран. (возможно на днях (если неожиданной работки не подкинут) попробую просто программку на эту тему нарисовать)
    – avp
    11 апр 2015 в 17:54
  • (2, 3, 4) (и остальное) - это строка)) поэтому она точно выбрана не будет ) Выше уже ссылки на алгоритмы вроде привели, поэтому, боюсь, любые усовершенствования будут сводиться либо к одному, либо к другому алгоритму. Хотя может быть коллективными усилиями еще один придумаем ) С O(N) = 1 ))))
    – BOPOH
    11 апр 2015 в 18:06
4

Можно разбить сигнатуры на группы по повторам в выбранном первом разряде и перебрать возможные варианты разрядов делающие сигнатуры уникальными.

  • Убираем общие и уникальные сигнатуры. Остались только сигнатуры с повторами.
  • Выбираем разряд(столбец) сигнатуры, который охватывает максимум комбинаций(назову его S1) и добавляем в список используемых разрядов. Для этого считаем повторы значений сигнатуры для каждой частоты.
  • Группируем сигнатуры с одинаковыми значениями в разряде S1. Для их идентификации требуется больше разрядов.
  • Для каждой группы сигнатур определяем разряды(1 или более) делающие их уникальными:

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.