Алгоритм Харта, Нільсона, Рафаэля

Міркування за індукцією, парадокс Хенпеля

Парадо́кс во́ронов (англ. Raven paradox), известный также как парадокс Гемпеля (нем. Hempels paradox) или во́роны Гемпеля — логический парадокс, сформулированный немецким математиком Карлом Густавом Гемпелем в 1940-х годах, для иллюстрации того, что индуктивная логика иногда входит в противоречие с интуицией.

Гемпель описал этот парадокс следующим образом. Предположим, что существует теория, согласно которой все вороны чёрные. Согласно формальной логике, эта теория эквивалентна теории, что все предметы, не являющиеся чёрными, не являются воронами. Если человек увидит много чёрных воронов, то его уверенность в том, что эта теория верна, увеличится. Если же он увидит много красных яблок, то это увеличит его уверенность в том, что все не чёрные предметы не являются воронами, и, согласно вышесказанному, должно также увеличить и его уверенность в том, что все вороны чёрные.

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

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

Принцип индукции утверждает, что:

Наблюдение явления Х, которое соответствует теории Т, увеличивает вероятность того, что теория Т истинна.

Мережа Хеміного

Мережа Хемінга (Hamming) є розширенням мережі Хопфілда. Ця мережа була розроблена Річардом Ліппманом (Richard Lippman) у середині 80-х рр. Мережа Хемінга реалізує класифікатор, що базується на найменшій похибці для векторів двійкових входів, де похибка визначається відстанню Хемінга. Відстань Хемінга визначається як число бітів, які відрізняються між двома відповідними вхідними векторами фіксованої довжини. Один вхідний вектор є незашумленим прикладом образу, інший є спотвореним образом. Вектор виходів навчальної множини є вектором класів, до яких належать образи. У режимі навчання вхідні вектори розподіляються до категорій для яких відстань між зразковими вхідними векторами та біжучим вхідним вектором є мінімальною.

Алгоритм Харта, Нільсона, Рафаэля

Поиск A* (произносится «А звезда» или «А стар», от англ. A star) — в информатике и математике, алгоритм поиска по первому наилучшему совпадению на графе, который находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной).

Этот алгоритм был впервые описан в 1968 году Питером Хартом, Нильсом Нильсоном и Бертрамом Рафаэлем. Это по сути было расширение алгоритма Эдсгера Дейкстры, созданного в 1959 году. Он достигал более высокой производительности (по времени) с помощью эвристики. В их работе он упоминается как «алгоритм A». Но так как он вычисляет лучший маршрут для заданной эвристики, он был назван A*.

A* пошагово просматривает все пути, ведущие от начальной вершины в конечную, пока не найдёт минимальный. Как и все информированные алгоритмы поиска, он просматривает сначала те маршруты, которые «кажутся» ведущими к цели. От жадного алгоритма (который тоже является алгоритмом поиска по первому лучшему совпадению) его отличает то, что при выборе вершины он учитывает, помимо прочего, весь пройденный до неё путь (составляющая g(x) — это стоимость пути от начальной вершины, а не от предыдущей, как в жадном алгоритме). В начале работы просматриваются узлы, смежные с начальным; выбирается тот из них, который имеет минимальное значение f(x), после чего этот узел раскрывается. На каждом этапе алгоритм оперирует с множеством путей из начальной точки до всех ещё не раскрытых (листовых) вершин графа («множеством частных решений»), которое размещается в очереди с приоритетом. Приоритет пути определяется по значению f(x) = g(x) + h(x). Алгоритм продолжает свою работу до тех пор, пока значение f(x) целевой вершины не окажется меньшим, чем любое значение в очереди (либо пока всё дерево не будет просмотрено). Из множественных решений выбирается решение с наименьшей стоимостью.

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

Код MatLab

function A*(start,goal)

% множество уже пройденных вершин

var closed:= the empty set

% множество частных решений

var q:= make_queue(path(start))

while q is not empty

var p:= remove_first(q)

var x:= the last node of p

if x in closed

continue

if x = goal

return p

add x to closed

% добавляем смежные вершины

foreach y in successors(x)

enqueue(q, p, y)

return failure