Равенство двух алгоритмов

Question

Рассмотрим дерево глубины B (т. Е. Все пути имеют длину B), узлы которых представляют состояния системы, а ребра представляют собой действия.

Каждое действие a in ActionSet имеет коэффициент усиления и переводит систему из состояния в другое. Выполнение последовательности действий A-B-C или C-B-A (или любая другая перестановка этих действий) приводит к одинаковому усилению. Более того:

• тем выше число действий, выполняемых перед тем a, тем меньше увеличение общего коэффициента усиления, когда a просят
• прирост от каждого пути не может быть больше, чем количество H, а именно: некоторые пути может получить выигрыш, который ниже, чем H, но всякий раз, когда выполнение действия делает общее усиление, равное H, все остальные действия выполняются с этого момента получит 0
• , что достигается с помощью последовательности действий #b,h,j, ..., a# является g(a) ()
• раз действие было выполнено на пути от корня к листу, оно не может быть выполнено во второй раз на том же пути

Применение Algorithm1. Я применяю следующий алгоритм (A * -like):

1. Начать с корня.
2. Разверните первый уровень дерева, который будет содержать все действия в ActionSet. Каждый расширил действие a имеет получить f(a) = g(a) + h(a), где g(a) определяется как указано выше, и h(a) является оценка того, что будут заработаны путем выполнения других B-1 действий
3. Выберите действие a*, который максимизирует f(a)
4. Расширьте детей a*
5. Итерация 2-3 до тех пор, пока не будет пройден весь путь от B посещений от корня до листа, который гарантирует самое высокое значение f(n). Обратите внимание, что новое выбранное действие можно также выбрать из узлов, которые были оставлены на предыдущих уровнях. Например, если после расширения a* узел максимального f(a) является дети корня, он выбран в качестве нового лучшего узла

Применение Algorithm2. Теперь предположим, что у меня есть жадный алгоритм, который смотрит только на компонент полезности-эвристики f(n), т. Е.Этот алгоритм выбирает действия в соответствии с выигрышем, который уже заработали:

1. на первом этапе я выбираю действие a максимального усиление g(a)
2. на второй шаге я выбрать действие b максимизируя прибыль g(b)

Претензия. Экспериментальные доказательства показали мне, что два алгоритма приводят к одному и тому же результату, который может быть смешанным (например, первый предлагает последовательность A-B-C, а вторая предлагает B-C-A). Однако мне не удалось понять, почему.

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

спасибо.

Answer 1

A * поиск вернет оптимальный путь. Из того, что я понимаю о проблеме, ваш жадный поиск просто выполняет вычисления байков, и wlll продолжает это делать, пока не найдет оптимальный набор узлов. Поскольку порядок узлов не имеет значения, они должны возвращать один и тот же набор узлов, albiet в разных порядках.

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