Последовательность с максимальным счетом?

Question

Скажем, у меня есть n-состояния S={s1,s2,s3, ..... sn }, и у меня есть оценка для каждого перехода, то есть T-матрица fe s1->s5 = 0.3, s4->s3 = 0.7, ....так далее.

Какой алгоритм или процедуру я должен использовать, чтобы выбрать наилучшую оцененную последовательность / путь, начиная с состояния-x (s_x).

Два вопроса:

1. Выберите наилучшее следующее состояние, чтобы на бесконечно длинном пути я выбирал как можно лучшее состояние в среднем?
2. Учитывая длину пути L, выберите последовательность состояний, которая будет генерировать наибольшее количество очков?

В настоящее время я изучаю изучение подкрепления, но это кажется излишним, потому что у меня нет ни действий, ни политик. Может быть, я могу использовать что-то вроде функции Value, не знаю.

Что бы вы использовали?

PS> В некоторых сценариях T-матрица может меняться со временем.

---

http://mnemstudio.org/path-finding-q-learning-tutorial.htm

Кажется, что Q-learning - хорошая ставка. Единственное отличие, которое я вижу, состоит в том, что если я хочу хранить Q-значения во времени, мне нужно найти способ приспособиться к изменению T-матрицы.

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

Мои первые мысли были на каждом временном шаге, чтобы сделать L-шаги наилучшим путем (то есть пересчитывать Q каждый раз с нуля), но если я смогу, я предпочту сохранить изменяющуюся Q-таблицу в соответствии с входящими данными.

Answer 1

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

Если вы не установите ограничение для длины пути, то, очевидно, максимальная оценка бесконечна.

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

Рекурсивная формулировка (которую вы затем можете использовать для определения части динамического программирования) гласит: Чтобы выяснить лучший путь длины L, начиная с состояния x, посмотрите на все другие состояния y. Для каждого из них вычисляем T_xy + "лучший путь длины L-1, начиная с состояния y".

Очевидно, что лучший путь длины 1, начиная с некоторого состояния x, будет "следующим лучшим состоянием", поэтому ваша рекурсия имеет простой базовый случай.