GotAI.NET

Форум: Проблемы искусственного интеллекта

 

Регистрация | Вход

 Все темы | Новая тема Стр.37 (56)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Выполнение команд (решение задач)
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 8:24
"Покупатель навоза, не довольный его качеством, не нашел слов чтобы выразить негодование."
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 8:49
Цитата:
Автор: Slava
а о каких хотя бы примерно задачах идет речь?
Сигал, насколько я понял, трассировал платы. Сейчас в GPS-навигаторах компутер сам маршрут составляет для автомобиля. Но это всё частные задачи. Я же в перспективе вижу этот алгоритм как замену аналоговому решателю, который оптимально (или близко к тому) строит план решения любой задачи.

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

Цитата:
Автор: Egg
всякая задача, связанная с интеллектом (то есть - моделирование) сводится именно к различным типам кластеризации.
Возможно, я до этого ещё не додумался, и мне надо сначала поиграться к коммивояжёром.
А ещё, возможно, я (как всегда) не точно выразился ранее и сложилось впечатление будто я занимаюсь кластеризацией. Но это не так на самом деле. Я просто ищу кратчайший маршрут, соединяющий N точек.

Цитата:
Автор: Egg
Функция объединения в кластеры тоже произвольная, например, в случае коммивояжера - это общий упорядоченный список, где длина (по заданной мере) списка минимальна.
В каждой конкретной задаче коммивояжёра есть самые дальние (взаимо-дальние) узлы. Они на равных основаниях должны быть включены в итоговый маршрут вместе с другими узлами. Но если эти дальние узлы взаимно будут соединены плохо, то именно они внесут максимальную ошибку (лишний прирост длины) в итоговый маршрут. Поэтому сначала надо соединять не ближние точки, а дальние. Такиим образом гарантируем, что алгоритм не напортачит глобально.

Отсюда делаются далекоидущие выводы о том, как нужно составлять план решения любой задачи.
[Ответ][Цитата]
Вольфрамовый клaпaн
Сообщений: 13070
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 8:58
Вот известный пример на отношение глобального и локального...
Клетки А и В одинакового цвета...
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 9:08
Простите, а где тут задача?
[Ответ][Цитата]
Вольфрамовый клaпaн
Сообщений: 13070
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 9:09
Цитата:
Автор: Андрей
Простите, а где тут задача?

Нет, не прощу.
upd: Когда поймешь в чем тут задача - можем продолжить, если захочешь.
Пока дам последнюю самую большую подсказку - алгоритм, похожий на эту иллюзию используется у меня в задачке построения аннотации для текста.
[Ответ][Цитата]
Вольфрамовый клaпaн
Сообщений: 13070
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 12:38
вот интересненько:
http://habrahabr.ru/post/151459/
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 13:46
Физики запутали десять миллиардов пар кубитов
http://www.membrana.ru/particle/15591
[Ответ][Цитата]
kondrat
Сообщений: 4026
На: Выполнение команд (решение задач)
Добавлено: 14 сен 12 14:08
Чем-то жёлтым попахивает.
[Ответ][Цитата]
kcrotor
Сообщений: 402
На: Выполнение команд (решение задач)
Добавлено: 15 сен 12 2:37
Цитата:
Автор: Egg
... алгоритм, похожий на эту иллюзию используется у меня в задачке построения аннотации для текста.


А можно ваш алгоритм увидеть в действии? Очень интересно на что он способен.

ЗЫ: Первая ассоциация: Алгоритм выдает одну и ту же аннотацию независимо от текста, но пользователю аннотации кажутся разными
[Ответ][Цитата]
Вольфрамовый клaпaн
Сообщений: 13070
На: Выполнение команд (решение задач)
Добавлено: 15 сен 12 5:12
Цитата:
Автор: kcrotor

А можно ваш алгоритм увидеть в действии? Очень интересно на что он способен.
ЗЫ: Первая ассоциация: Алгоритм выдает одну и ту же аннотацию независимо от текста, но пользователю аннотации кажутся разными

я бы сам не отказался посмотреть на него в действии, но для этого нужно его заставить работать, а пока он заставляет работать меня...
А ассоциация у Вас близкая по сути...
[Ответ][Цитата]
Victor G. Tsaregorodtsev
Сообщений: 3187
На: Выполнение команд (решение задач)
Добавлено: 15 сен 12 5:20
Цитата:
Автор: Андрей
Сигал, насколько я понял, трассировал платы.

Не в смысле прокладки товокедущих дорожек - а в смысле планирования схемы перемещения платы под сверлильным станком (т.е. есть координаты будущих дырок в плате - и нужно их максимально быстро обойти при сверлении).

Цитата:
Автор: Андрей
Я же в перспективе вижу этот алгоритм как замену аналоговому решателю, который оптимально (или близко к тому) строит план решения любой задачи.

Так аналоговый решатель и так строит близкий к оптимальному план. Возьмём, к примеру, elastic snake для комми - сложность (ЕМНИП) будет поменьше, чем n^3.
[Ответ][Цитата]
Victor G. Tsaregorodtsev
Сообщений: 3187
На: Выполнение команд (решение задач)
Добавлено: 15 сен 12 5:25
Цитата:
Автор: Андрей
чтобы определить, что интеллектом не является, сначала нужно определиться с тем, что интеллектом таки является.

"Чтобы определИть мышление - нужно сначала опредЕлить его" (С) земляк-биофизик лет 20 назад, я эту цитату на форуме несколько раз уже давал.
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 15 сен 12 5:40
Цитата:
Автор: Victor G. Tsaregorodtsev


"Чтобы определИть мышление - нужно сначала опредЕлить его" (С) земляк-биофизик лет 20 назад, я эту цитату на форуме несколько раз уже давал.


Молодец ваш земляк и вы, раз его услышали, - ограничения - важнейший компонент формулировки задачи. К сожалению, этому практически никого не учат
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 16 сен 12 17:52
Цитата:
Автор: Egg
вот интересненько:
http://habrahabr.ru/post/151459/

ещё о Плотникове
http://rg.ru/2012/09/16/zadacha-site.html
"Сейчас речь о задаче P vs NP. Она формулируется так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти."
Иначе говоря сложность P имеют алгоритмы, решающие задачу. А сложность NP это трудоемкость просто получения ответа, как угодно. Это не класс сложности алгоритмов решения. А более абстрактная идея, поближе к машине Тьюринга. В P-задачах есть модель предметной области и всё такое, она получает только уточняющие параметры, подставляет их в модель, прогоняет и получает ответ. В NP модели-программы нет. NP-машиной можно решать P-задачи. Можно разрешить ей генерировать и выполнять программы, превращающие её в P. Кроме случая NPC, там модели и нет и быть не может. Но это только формулировка идеи, гипотеза. Существуюти ли в действительности NPC задачи (не постановки) не известно. Но многие задачи можно ставить как NPC, если у нас есть постановка то рассуждать P она или не P уже поздно. Существование NPC видимо должно означать существование изолированных фрагментов реальности. Про которые нет никакой обобщающей физики и в которых не возникают никакие закономерности от внешнего воздействия. Вопрос метафизики, а не информатики.

Напомню ещё, что кроме перебора есть универсальный метод решения, заключающийся с составлении таблицы Y=T[X], решающий все задачи любой сложности какого-то класса за одно действие. Даже такие, про которые математически доказано, что они неразрешимы, если неизвестно как, без всякой науки и математики, но мы добыли и записали результаты.
Поэтому если говорить не о теории, а о конкретных компьютерах, то там память ограничена. Это накладывает ограничение на класс задач и означает, что на другом компьютере все задачи этого можно решать P-алгоритмом с полиномом степени 0.
Немного обобщая получаем какое бы конкретное N не взяли NP-задача превращается в P, а если у нас толко буква "N" то получим NP.
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 20 сен 12 15:11
Во отсутствие обсуждения, покритикую себя сам.
Совершенно понятен недостаток предложенного выше рекурсивного алгоритма, как аналога алгоритма решения задач человеческим интеллектом. Когда человек решает задачу, он не пытается сразу проработать все детали всего плана до конца, т.е. не пытается составить план решения вплоть до сокращений конкретных мышц для каждого пункта плана (для каждой подзадачи). Человек прорабатывает план максимально детально только от первого пункта до второго пункта. При достижении второго пункта - прорабатывает детали между вторым и третьим пунктом и так далее.
С учётом этого соображения полностью идеологически переделал алгоритм и теперь он решает 1000 узлов за 3 секунды. И результат при этом показывает на несколько процентов лучший.

Решение задачи коммивояжёра рекурсивным жадным алгоритмом

Условия задачи те же, что и ранее.

Для синтеза плана решения задачи возьмём за основу 2 соображения.
1. Кратчайший путь между двумя точками на плоскости в метрике евклида всегда лежит по прямой.
2. Самые дальние узлы вносят наибольшую ошибку в суммарную длину маршрута если эти дальние узлы не самым лучшим образом соединены с остальными узлами.

Исходя из этих двух соображений построим алгоритм таким образом.
1. Соединим входной и выходной узел отрезком прямой. Этот итоговый маршрут из Вх в Вых будет, очевидно, кратчайшим.
2. Однако у нас в задаче есть, к сожалению, и другие узлы, которые тоже должны быть включены в итоговый маршрут. Поэтому мы постараемся минимальным образом ухудшать этот наилучший кратчайший маршрут и будем по одному включать в него остальные узлы.
3. Для этого, из всех оставшихся узлов (в силу второго нашего соображения) мы выберем взаимо-дальний узел к первоначальным двум (Вх и Вых) и включим его в найденный кратчайший маршрут оптимальным образом - разорвём связь между Вх и Вых и соединим Вх и Вых через этот третий взаимо-дальний узел.
4. Далее найдём взаимо-дальний узел к первым трём узлам и включим его в итоговый маршрут таким образом, чтобы это включение дало минимальный прирост длины маршрута. Ясно, что при включении этого четвёртого узла у нас появится выбор из двух рёбер (для третьего узла такого выбора не было). Поэтому здесь и далее нам придётся для каждого нового взаимо-дальнего узла перебирать все рёбра текущего полученного маршрута и выбирать из этих рёбер то, разрыв которого даст минимальный прирост длины.
5. Точно так же поступим с оставшимися узлами.

Программу и исходники можно скачать здесь. (Поменял немного интерфейс, теперь окно можно растягивать.)

Достоинства алгоритма:
1. Простота.
2. Скорость. На машине с четырёх-ядерным процессором 2,67 ГГц
1000 узлов - 3 секунды
2000 узлов - 27 секунд
3000 узлов - 87 секунд
4000 узлов - 207 секунд
Прирост времени экспоненциальный, но для практических задач достаточно медленный.
3. В сравнении с ранее предложенным рекурсивным алгоритмом результат получается лучшим примерно на 8%.
4. Минимальное использование оперативной памяти.
5. Отсутствие каких-либо настроек.
6. Минимальное количество пересечений без какой-либо проверки на пересечения.

UPD: Подправил в программе глюк с сообщениями в WinXP.
[Ответ][Цитата]
 Стр.37 (56)1  ...  33  34  35  36  [37]  38  39  40  41  ...  56<< < Пред. | След. > >>