Аннотация:

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

Ключевые слова:

структура компактных троек, структура компактных пар, несогласованные структуры, унификация структур, совместный выполняющий набор.

Стр. 13-24.

V. F. Romanov

"Discordant compact data structures in combinatorial optimization problems"

Abstract. In sphere of research of discrete optimization algorithms efficiency the important place occupies a method of polynomial reducibility of some problems to others with use of special purpose components. In this paper a novel method of compact representation for sets of binary sequences in  the  form  of  «compact  triplets  structures»  and «compact couples structures» is stated, supposing both  logic  and  arithmetic  interpretation  of  data. A key-point of the investigation is adaptation of the polynomial algorithm of constraints distribution (well-known in the optimization theory) to the efficient resolving Boolean formula coded by means of discordant compact structures.

Keywords: structure of compact triplets, structure of compact couples, discordant structures, structures unification, joint satisfying set.

Полная версия статьи в формате pdf.

REFERENCES

1. Romanov V. F.  Neortodoksalnye  modeli  dlya  zadach diskretnogo analiza i optimizatsii. LAP LAMBERT Academic Publishing: Saarbrucken, Germany, 2012. 130 s.
2. Romanov V. F. Non-orthodox combinatorial models based on discordant structures. Electronic journal «Investigated in Russia» — http://zhurnal.ape.relarn.ru/articles/2007/143e.pdf
3. Romanov  V. F. Non-orthodox combinatorial models based on   discordant   structures.  ArXiv.org.,  2011 —   http:// arxiv.org/abs/1011.3944
4. Lorer Zh.-L.  Sistemy  iskusstvennogo  intellekta. M.: Mir, 1991. 568 s.