Термин

Перевод, толкование

heuristic algorithm

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

heuristic distance

эвристическое расстояние, т.е. расчет расстояния между объектами на основе некого внутреннего знания (например, известно что оно не меньше некоторого значения)

hill climbing

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

beam search

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

the Oracle checking algorithm

алгоритм проверки полученного путем угадывания ответа на задачу

tree-like diagram

диаграмма в виде дерева

path extending

расширение (увеличение) пути, т.е. добавление в путь новой вершины

starting node

вершина, являющаяся началом пути

accumulated path length

длина пройденного пути

heuristic estimates of how far we are from the goal

эвристические оценки показывают насколько мы далеко от цели (насколько далеко еще предстоит идти до конечной вершины)

we're not considering how far we've got to go, we're only thinking about how far we've gone so far.

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

branch and bound

метод ветвей и границ, по сути полный перебор с отбросом заведомо неверных вариантов

N queueing list

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

branch and bound with extended list

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

admissible heuristic

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

if the heuristic estimate is guaranteed to be less than the actual distance, that's called an admissible heuristic

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

A*

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

non-Euclidean arrangements

неевклидова метрика

consistency condition

свойство непротиворечивости, полноты системы

it almost always depends on the problem itself, if you change the problem, you may get a different result

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

you can either keep track of the nodes that have been extended and not extend them again.

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

dead horse principle - as soon as we figure out that a path that goes to a particular place can't possibly be the winning path, we get rid of it, and don't bother extending it

принцип “мертвой лошади” - как только становится заведомо известно, что текущий путь не может привести к цели, либо он заведомо не кратчайший, то стоит отказаться от него и не пытаться его расширить