Интеллектуальные робототехнические системы

       

Алгоритм наискорейшего спуска по дереву решений


Пример построения более узкого дерева рассмотрим на примере задачи о коммивояжере. Торговец должен побывать в каждом из 5 городов, обозначенных на карте (рис. 3.3).

Алгоритм наискорейшего спуска по дереву решений

Рис. 3.3. 

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

Алгоритм наискорейшего спуска по дереву решений

Рис. 3.4. 

Такой алгоритм поиска решения получил название алгоритма наискорейшего спуска (в некоторых случаях - наискорейшего подъема).



Содержание раздела