1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 10(135)'2015
  5. Відшукання гамільтонова шляху на неповнодоступному стохастичному графі

Відшукання гамільтонова шляху на неповнодоступному стохастичному графі

Р.Х. Ахмадов, Н.І. Ящук
Анотації на мовах:

Класична задача відшукання гамільтонова шляху на графі розглянута для випадку, коли довжини ребер графа задані неточно. Запропоновано вирішення задачі для наступних варіантів обліку невизначеності: елементи матриці - випадкові величини з відомою щільністю розподілу; елементи матриці задані значеннями математичного очікування й дисперсії; елементи матриці визначаються в припущенні про найгіршу щільності розподілу випадкових значень корисності, для якої ймовірність попадання випадкової корисності в неприпустимий діапазон максимальна.
Ключові слова: неповнодоступний граф, гамільтонів шлях, довжини ребер задані неточно, генетичний алгоритм