История изменений

Исправление pathfinder, 28.08.13 21:26 (текущая версия) :

Нет, наверное все-таки динамическое программирование можно здесь применить по схеме близкой к нахождению кратчайшего пути.

Но здесь очень важно правильно понять что и как надо перебирать. Тут должно быть что-то вроде последовательного «обволакивания».

Уф. Попробую объяснить.

Пускай у нас двухмерный случай и предположим, что у нас есть частичное решение А вида.

aa
aa

Здесь каждый символ сетки, это узел. Для каждого из этих узлов известно правильное значение (на сфере), так, что суммарная «близость на сфере» всех значений смежных узлов оптимальна. Cам лист с неизвестными оптимальными значениями имеет вид:

......
......
..aa..
..aa..
......
......

Так как фигура А является частью искомого листа, то добавим ещё один «обволакивающий» слой B:

......
.bbbb.
.baab.
.baab.
.bbbb.
......

Можно догадаться, присоединение слоя B возможно N способами, где N зависит количества значений во всех узлах слоя B. Соответственно мы можем для каждого из этих N способов посчитать целевую функцию f(А+B)

Добавим ещё один обволакивающий слой С:

сссссс
сbbbbс
сbaabс
сbaabс
сbbbbс
сссссс

Можно догадаться, что присоединение слоя С возможно M способами, где M зависит от количества значений во всех узлах слоя C. Для каждого из этих М способов нам достаточно выбрать только один (sic!) способ присоединения слоя B из N возможных. Выбираем самый оптимальный, с наилучшей целевой функцией, остальные отбрасываем. Так мы можем поступить потому, что связь слоев a-b внутренняя и никак не может повлиять на дальнее наращивание целевой функции при присоединении слоя С. Поэтому выбираем наилучший вариант N.

По такой схеме можно продолжить дальше.

Исходная версия pathfinder, 28.08.13 21:22:

Уф. Попробую объяснить.

Пускай у нас двухмерный случай и предположим, что у нас есть частичное решение А вида.

aa
aa

......
......
..aa..
..aa..
......
......

Так как фигура А является частью искомого листа, то добавим ещё один «обволакивающий» слой B:

......
.bbbb.
.baab.
.baab.
.bbbb.
......

Можно догадаться, присоединение слоя B возможно N способами, где N - суммарное количество значений во всех узлах слоя B. Соответственно мы можем для каждого из этих N способов посчитать целевую функцию f(А+B)

Добавим ещё один обволакивающий слой С:

сссссс
сbbbbс
сbaabс
сbaabс
сbbbbс
сссссс

Можно догадаться, что присоединение слоя С возможно M способами, где M - суммарное количество значений во всех узлах слоя C. Для каждого из этих М способов нам достаточно выбрать только один (sic!) способ присоединения слоя B из N возможных. Выбираем самый оптимальный, с наилучшей целевой функцией, остальные отбрасываем. Так мы можем поступить потому, что связь слоев a-b внутренняя и никак не может повлиять на дальнее наращивание целевой функции при присоединении слоя С. Поэтому выбираем наилучший вариант N.

По такой схеме можно продолжить дальше.