У меня задача решить "пятнашки" и прочие схожие задачи. Предполагаю(даже не предполоагаю, а точно буду, т.к. делал это руками) использовать astar_search, но astar_search предполагает работу с графами которые уже существуют хоть и принимает astar_search не константную ссылку на граф, но вот breadth_first_visit, по средством которого и работает astar_search, принимает константную ссылку. И вот вопрос, как быть в случае если граф будет расти во время работы алгоритма?

Аноним 908 wrote:

> BGL. Граф должен расти во время алгоритма. <message/3412233.aspx>

Открой доку и посмотри, там чётко прописано в таблице, когда инвалидируются
какие итераторы на графе. Потом глянь в алгоритм, какие итераторы используются.
Вот и получишь. Но по-моему тебе не светит.

Перефразирую вопрос, как не руками реализовать информативный поиск в пространстве состояний, если имеется: начальное состояние, целевое состояние и операторы производящие новые состояния?

Здравствуйте, MasterZiv, Вы писали:

MZ>Аноним 908 wrote:

>> BGL. Граф должен расти во время алгоритма. <message/3412233.aspx>

MZ>Открой доку и посмотри, там чётко прописано в таблице, когда инвалидируются
MZ>какие итераторы на графе. Потом глянь в алгоритм, какие итераторы используются.
MZ>Вот и получишь. Но по-моему тебе не светит.

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

BLo пишет:

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

Нет, ты неправильно понял. если алгоритм предполагает неизменчивость
графа, т.е. например на первом этапе делает какую-то оценку всего графа, а потом
её использует, то это -- другое дело, он не сможет работать с неизменным
графом. А вот алгоритм, который потенциально МОЖЕТ работать с изменчивым графом,
например, тот же поиск в ширину или глубину, при некоторых ограничениях на
модификацию графа, он уже не сможет работать чисто по техническим причинам --
инвалидации итераторов.

Здравствуйте, MasterZiv, Вы писали:

MZ>BLo пишет:

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

MZ>Нет, ты неправильно понял. если алгоритм предполагает неизменчивость
MZ>графа, т.е. например на первом этапе делает какую-то оценку всего графа, а потом
MZ>её использует, то это -- другое дело, он не сможет работать с неизменным
MZ>графом. А вот алгоритм, который потенциально МОЖЕТ работать с изменчивым графом,
MZ>например, тот же поиск в ширину или глубину, при некоторых ограничениях на
MZ>модификацию графа, он уже не сможет работать чисто по техническим причинам --
MZ>инвалидации итераторов.

Об валидности итераторов я позаботился бы установкой listS для вершин и для ребер. Похоже придется писать ручками аналогичный astar_search.

PS: Галочка "получать ответы по e-mail" сбилась.

Здравствуйте, Аноним, Вы писали:

А>У меня задача решить "пятнашки" и прочие схожие задачи. Предполагаю(даже не предполоагаю, а точно буду, т.к. делал это руками) использовать astar_search, но astar_search предполагает работу с графами которые уже существуют хоть и принимает astar_search не константную ссылку на граф, но вот breadth_first_visit, по средством которого и работает astar_search, принимает константную ссылку. И вот вопрос, как быть в случае если граф будет расти во время работы алгоритма?
По моему, вначале надо определиться с тем, что такое граф будет расти во время работы алгоритма.
Ведь, в дюбом случае, в какой-то момент надо будет зафиксировать граф и запустить алгоритм поиска. далее, по окнчании работы алгоритма надопосмотреть не изменилось ли состояние графа, если нет то принять работу, иначе сформировать новый граф и запустить снова astar_search.

Здравствуйте, serge.bn, Вы писали:

SB>По моему, вначале надо определиться с тем, что такое граф будет расти во время работы алгоритма.

"Рост графа во время работы алгоритма" — под этим подразумеваться то, что в контрольной точке работы алгоритма (discover vertex, examine vertex, ...) может произойти добавление вершин и ребер.

SB>Ведь, в дюбом случае, в какой-то момент надо будет зафиксировать граф и запустить алгоритм поиска. далее, по окнчании работы алгоритма надопосмотреть не изменилось ли состояние графа, если нет то принять работу, иначе сформировать новый граф и запустить снова astar_search.

вот это, думаю, лишнее.