алгоритм оптимального поиска без допустимой эвристики

Question

Пожалуйста, простите меня, если я не использую правильные условия или не упустил существующее решение. Я не знаком с поисковыми алгоритмами и теориями. Я просто хотел бы решить проблему.

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

Что я узнал:

• Начала в вашем происхождении узла
• Открыть новое решение для каждого пути вы можете взять
• Рекурсивных создать новое субрешение для каждого пути вы можете взять оттуда
• Когда вы приедете в том же месте, с несколькими решениями, падение тех, кто занял больше времени, чем самый быстрый

Теперь, если я понимаю википедии правильно, это то, что я должен был сделать:

• Начало в вашем происхождении узла
• Открыть новое решение для каждого пути вы можете взять
• Сортировать решения по «стоимости от пути, пройденного»+„оценивается стоимость целевого“
• Возьмите дешевое решение и создать субрешениями для каждого возможного пути
• порядка эти решения в других затем ополоснуть повторить

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

Я не ищу путь на географической карте. Я пытаюсь найти наилучшую последовательность действий. Существует минимальная последовательность - скажем - ABCDEFGH. Вы не можете делать F до E, но повторение предыдущих действий в частичном порядке может сделать более поздние действия более эффективными.

Нужен ли мне другой алгоритм поиска? Я делаю то, что я изначально узнал, и просто живу с тем, что делать больше работы - это цена за отсутствие хорошей эвристической функции?

Я считаю, что мой учитель признал эту проблему. И то, что я узнал, было просто A * с эвристической функцией f (n) = 0.

Answer 1

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

Непонятно, можно ли повторить одно действие, то есть решение является ABCDEFGH, но возможно ли ABBBBCDEFGH?

Если нет, то вы можете быть в состоянии иметь алгоритм *, реализован так:

1. At some stage (say the first, "empty"), you have one of several actions 
    available. 
2. The cost of going from Empty City to A City is the cost of action A. 

3. The cost of going from Empty City to B city is the cost of action B. 

Когда вы достигли B, стоимость выполнения C является постоянной (если это не , то вы не можете использовать A * как есть), и вы вставляете стоимость переезда из города B в город C как стоимость C.

Таким образом, вы можете обрабатывать случай, в котором действие имеет разные расходы, при условии, что эта разница полностью описана предыдущим состоянием. Например, если вы можете делать только C, если вы сделали A или B, а стоимость C равна 5 и 8, вы вводите «расстояние» между A и C как 5, а от B до C - от 8.

Если стоимость, скажем, D зависит от двух предыдущих состояний, вы все равно можете использовать более сложную реализацию A *, где вы определяете виртуальные «города» BC, AB и AC, а расстояние от BC до D - это « стоимость D, сделанная B и C ", и так далее. Стоимость достижения BC от A - это «стоимость B, предоставленная A, и стоимость C, предоставленная A и B». Так что если эти расходы зависят от предыдущих состояний, все становится еще сложнее.

В конце концов, сложность этого пересмотренного A * будет возрастать до тех пор, пока он не станет вашим алгоритмом, где каждое состояние потенциально зависит от последовательности всех предыдущих состояний. Чем больше это верно, тем больше ваш алгоритм удобен; чем больше каждое государство является ценой для себя, тем больше A * является удобным.

И, конечно, возможность замкнутых петель (посещение одного и того же состояния/действия дважды, делая этот циклический график) ударяет A * прямо из воды.