История изменений
Исправление
stevejobs,
(текущая версия)
:
сейчас такая идея.
Тупо A*, который «поиск кратчашего пути на карте», ищем самый дешевый маршрут из соображения что стоимость пути до точки - это стоимость пути до предыдущей точки+стоимость текущего шага, определяющегося эвристикой.
Фиксируем какой-то набор «особо важных» переменных, 1-3 штуки, и считаем что чем быстрее операция приближает к ним, тем «короче путь» до нее. Т,е если цель - x>100, то путь x+500 намного дешевле, чем x+10. «Пространство поиска» уменьшится. Потом снова фиксируем 1-3 переменных, и так далее.
Идти можно и A->B, и B->A одновременно. В надежде что встретятся. Учитывать в эвристике, что чем ближе между собой противоположные пути, тем «дешевле» считать этот путь.
Плюс крутое анти-ограничение «автоподстраивающиеся значения». В конце дерева поиска (либо в «конце пути», либо при встрече двух сходящихся одновременно из А и Б путей) скорее всего получится так, что решений не существует. Тогда движок будет волен поменять (в некоторых пределах допуска) саму задачу, н-р если исходно требуется чтобы x>20, а у нас x=19, и это правило помечено как «неважное» (или не помечено как «важное») - то движок корректирует условие: x>20 => x>19.
Всё вместо это может оказаться намного дешевле тупого перебора в ширину
Но тут надо хорошую эвристику на «расстояние», которой я еще не знаю, если есть идеи - вэлкам
Например, вот x*2 будет «дешевле» x+500 только при достаточно больших X. Но как мы решим, что Х действительно достаточно большое - проведем реальные вычисления? Тогда на сам подсчет стоимости шага будут тратиться капец какие ресурсы
Исправление
stevejobs,
:
сейчас такая идея.
Тупо A*, который «поиск кратчашего пути на карте», ищем самый дешевый маршрут из соображения что стоимость пути до точки - это стоимость пути до предыдущей точки+стоимость текущего шага, определяющегося эвристикой.
Фиксируем какой-то набор «особо важных» переменных, 1-3 штуки, и считаем что чем быстрее операция приближает к ним, тем «короче путь» до нее. «Пространство поиска» уменьшится. Потом снова фиксируем 1-3 переменных, и так далее.
Идти можно и A->B, и B->A одновременно. В надежде что встретятся. Учитывать в эвристике, что чем ближе между собой противоположные пути, тем «дешевле» считать этот путь.
Плюс крутое анти-ограничение «автоподстраивающиеся значения». В конце дерева поиска (либо в «конце пути», либо при встрече двух сходящихся одновременно из А и Б путей) скорее всего получится так, что решений не существует. Тогда движок будет волен поменять (в некоторых пределах допуска) саму задачу, н-р если исходно требуется чтобы x>20, а у нас x=19, и это правило помечено как «неважное» (или не помечено как «важное») - то движок корректирует условие: x>20 => x>19.
Всё вместо это может оказаться намного дешевле тупого перебора в ширину
Но тут надо хорошую эвристику на «расстояние», которой я еще не знаю, если есть идеи - вэлкам
Исходная версия
stevejobs,
:
сейчас такая идея.
Тупо A*, который «поиск кратчашего пути на карте», ищем самый дешевый маршрут из соображения что стоимость пути до точки - это стоимость пути до предыдущей точки+стоимость текущего шага, определяющегося эвристикой.
Фиксируем какой-то набор «особо важных» переменных, 1-3 штуки, и считаем что чем быстрее операция приближает к ним, тем «короче путь» до нее. «Пространство поиска» уменьшится. Потом снова фиксируем 1-3 переменных, и так далее.
Идти можно и A->B, и B->A одновременно. В надежде что встретятся. Учитывать в эвристике, что чем ближе между собой противоположные пути, тем «дешевле» считать этот путь.
Плюс крутое анти-ограничение «автоподстраивающиеся значения». В конце дерева поиска (либо в «конце пути», либо при встрече двух сходящихся одновременно из А и Б путей) скорее всего получится так, что решений не существует. Тогда движок будет волен поменять (в некоторых пределах допуска) саму задачу, н-р если исходно требуется чтобы x>20, а у нас x=19, и это правило помечено как «неважное» (или не помечено как «важное») - то движок корректирует условие: x>20 => x>19.