GotAI.NET

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

 

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

 Все темы | Новая тема Стр.31 (56)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Выполнение команд (решение задач)
Эгг
Сообщений: 10145
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 7:59
Цитата:
Автор: Андрей

Смыслов много.

На Хабре тебе довольно предметно ответили...
Сейчас, к сожалению, у меня обрез по времени, а вот в декабре, если у тебя не пройдет интерес к этой задачке можно сделать следующее:
1. Разработать формат начальных условий, какой-нибудь двумерный массив;
2. Сгенерировать входной файл с начальными условиями - 1000 точек, я полагаю, будет нормально;
3. Разработать формат решения, какой-нибудь векторный список пар точек;
4. Написать общую для всех считалку пути, чтобы можно было оценить качество решения;
5. Скорость решения придется "прикидывать на глазок", она будет относительной, будем считать ее в процентах и усреднять по разным компам, если у разных людей она разная.

И устроим соревнование. Уверен, что мой вариант отжига будет лучше.

upd: это напоминает мне третий класс моей (математической) школы, когда мы судорожно пытались решить с помощью линейки и циркуля задачу квадратуры круга и трисекции угла. И каждый раз казалось, что вот оно - решение. NPC - это NPC, всякая эвристика на ней - это просто эвристика...
[Ответ][Цитата]
Андрей
Сообщений: 3436
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 10:58
Цитата:
Автор: NO.
быстро считает
И это не предел. Надо увеличить вложенность рекурсии, тогда вообще летать будет.

Цитата:
Автор: Egg
На Хабре тебе довольно предметно ответили
На Хабре по сути высказался только ystein, дав любопытную ссылку на аналогичный метод, который, тем не менее, существенно отличается от моего. Все остальные участники попридирались к словам. Сомневаюсь, что большинство ответивших вообще вникли в суть алгоритма.

Цитата:
Автор: Egg
NPC - это NPC, всякая эвристика на ней - это просто эвристика
Эвристика - это аналогия. И она подбирается субъективно и стохастически. Уйти от этого полностью - нельзя, согласен. Но максимально уйти от этой субъективной предвзятости, наверное, можно.

Цитата:
Автор: Egg
устроим соревнование
Поддерживаю. Конкуренция - двигатель прогресса.
Может ещё кто-то захочет подключиться.
[Ответ][Цитата]
Эгг
Сообщений: 10145
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 11:07
Цитата:
Автор: Андрей

Сомневаюсь, что большинство ответивших вообще вникли в суть алгоритма.

и это правильно... я вот тоже, честно скажу, не слишком вникал, поскольку любые идеи из области оптимизации имеют границы своего применения. Точка. Что это значит? То, что в "средне-статистическом" случае такой алгоритм может работать с качеством 0.95 (и выше), но по "достижении" "больших чисел" будет вариант, при котором он даст серьезную ошибку. И чем более оптимален алгоритм, тем большую ошибку можно вызвать.

А то, что "большие числа" бывают я узнал по своему газпромовскому проекту, где на 100км трубы примерно 10 миллиардов значений с одного прохода одного типа дефектоскопа. Сигналом вполне может быть кластер из 6-15 сигналов. Вот у нас и получалось, что стоило только сформулировать эвристическое правило, как обязательно оказывалось реально найденное исключение. Логика в таких вещах не работает, просто поверь - и подумай на досуге - почему.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 11:17
Один участник тоже отметил, что задача на плоскости.

Рекурсия может нарваться на какой-нибудь тоже рекурсивный фрактал и получить рекурсивно плохой результат. В эвриситике используется предположение о равномерном распределении точек. NPC не оптимизируется ни сверху-вниз ни снизу-вверх, никак.
Задача коммивояжора хуже чем NPC, тут N! что больше чем 2^N. Вот построить первое разбиение, при котором этот алгоритм найдет точное решение, это 2^N.
[Ответ][Цитата]
Андрей
Сообщений: 3436
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 11:43
Цитата:
Автор: Egg
стоило только сформулировать эвристическое правило, как обязательно оказывалось реально найденное исключение
Именно поэтому я против эвристик. Получился какой-то не контраргумент, а самый настоящий аргумент.

Цитата:
Автор: NO.
В эвриситике используется предположение о равномерном распределении точек.
В какой эвристике? У меня такого нет.
Простое соображение. Следите за руками. Если в массиве данных есть какие-то неоднородности (скопления) то именно на них надо ориентироваться в первую очередь, чтобы построить первое, грубое, приблизительное решение. Мой алгоритм их мгновенно обнаруживает при рекурсивном разбиении на группы. Это буквально очевидно на том макете, что я размещал выше. Если же узлы рсположены равномерно, то мы впадаем в другую крайность и тут, внимание, алгоритм вообще всё-равно какой, хоть жадный, хоть отжиг - все дадут примерно одинаковый результат, потому что на любой развилке всё-равно куда поворачивать - нет принципиальной разницы, всё однородно и изотропно.
Вот и получается, что лучший алгоритм это тот, который гибко подстраивается под конкретную задачу, а не пытается некую шаблонную задачу натянуть на данную. Мне кажется, я нашёл лучший способ для такой подстройки. Поживём - увидим...
[Ответ][Цитата]
Эгг
Сообщений: 10145
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 11:52
Цитата:
Автор: Андрей

Если в массиве данных есть какие-то неоднородности (скопления) то именно на них надо ориентироваться в первую очередь, чтобы построить первое, грубое, приблизительное решение.

Все алгоритмы, использующие локальные максимумы, основаны на этом нехитром соображении...

я нашел для тебя следующую задачку - обращение больших матриц... примени свой метод на них, там очень много проблем из-за близости (n/->0)... и методы есть классические, будет с чем сравнить...
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 10 сен 12 12:13
Раз алгоритм считает быстро можно запустить поиск неудачной конфигурации. Сравнивать с полным перебором и сдвигать понемногу точки. Я думаю получится какой-то фрактал, раз уж алгоритм рекурсивный.
Для отжига аналогично наверно получится путь в котором большинство переходов между близкими точками, а один переход очень длинный.

В общем под любой можно выкопать локальную яму. А сравнивать нужно графики зависимости качества от времени работы. Который круче тот круче.
[Ответ][Цитата]
Victor G. Tsaregorodtsev
Сообщений: 3133
На: Выполнение команд (решение задач)
Добавлено: 11 сен 12 6:14
Цитата:
Автор: Egg
Уверен, что мой вариант отжига будет лучше.

Лучше отожжёт


PS. Это было замаскированное пожелание (вместо критериев "быстрее" или "точнее" взять критерий "круче"). В конце концов не счёты делаем - а ИИ. Пусть прога, например, регулярно просит сказать волшебное слово "пожалуйста" И далее можно доводить у проги алгоритмы работы с естественным языком и алгоритмы выпендривания до качества, позволяющего пройти ТТ.
[Ответ][Цитата]
Анатоль
Сообщений: 1964
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 0:27
А зачем в условии комивояжёру чтобы только один раз пройти каждую точку?
Ведь для практических целей это бессмысленно.
Ведь практический смысл именно в наименьшей сумме.
И если она может быть меньше при допущении повторных посещений, то на практике так и надо делать.
[Ответ][Цитата]
Fractaler
Сообщений: 2490
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 2:47
Цитата:
Автор: Анатоль

Так ставится "задача коммивояжёра" (офени-коробейника, торгового агента, распространителя и т.п.). Вершинами графа могут быть не только города, но и другие объекты. Ограничения (запреты) могут быть человеческими (нельзя и всё, бить будут, налог за посещение, фейс-контроль и т.д.), так и просто ну нечеловеческими (занятия в задаче составления расписания - обучаемые не должны попадать на такое же занятие, которое уже посетили).
[Ответ][Цитата]
Андрей
Сообщений: 3436
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 4:00
Цитата:
Автор: Анатоль
А зачем в условии комивояжёру чтобы только один раз пройти каждую точку?
Ведь для практических целей это бессмысленно.
Ведь практический смысл именно в наименьшей сумме.
И если она может быть меньше при допущении повторных посещений, то на практике так и надо делать.
Любопытно, что ответ на Ваш (фундаментальный) вопрос для Вас не очевиден. Попробую прояснить тремя способами.

1. Теоретический.
Допустим, что коммивояжёр уже знает оптимальный путь. Или (что ещё лучше) он знает оптимальную стратегию движения. То есть ему не надо ничего искать, ничего перебирать, ничего решать - ему нужно только в каждом узле делать выбор следующего узла строго в соответствии со своим знанием оптимальной стратегии. В таком случае совершенно очевидно, что попав в какой-то узел он может выбрать только один единственный узел-преемник (потому что его стратегия оптимальна (однозначна) по определению!). Если же стратегия коммивояжёра допускает неопределённость в выборе узла (т.е. из одного и того же узла можно попадать то в один то в другой узел), тогда она не оптимальна. По определению. А поскольку нас интересует оптимальная (или близкая к ней) стратегия, то мы используем в качестве признака этой стратегии именно данное условие - попадать в каждый узел один раз.

2. Практический.
Все оптимальные пути, полученные полным перебором на практике, не содержат повторов и пересечений. Я проверял.

3. Умный.
Задача коммивояжёра детально рассматривается в данном топике не потому, что заняться больше нечем, а потому, что через такую отвлечённую почтовую аналогию можно представить процесс решения любой задачи! Каждый узел - это под-задача большой над-задачи. Коммивояжёр решает конкретную над-задачу - доставка почты. После того, как коммивояжёр пришёл в конкретный город, он оставил в нём всю почту для данного города (решил под-задачу), и ему просто больше незачем в этот город возвращаться! Если мы посмотрим на задачу коммивояжёра более абстрактно, то заметим, что составляя план решения произвольной над-задачи мы разбиваем её на под-задачи с таким умыслом, что после решения каждой из этих подзадач по одному разу(!) вся задача в целом будет решена гарантированно.
[Ответ][Цитата]
Анатоль
Сообщений: 1964
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 4:30
Цитата:
Автор: Андрей
В таком случае совершенно очевидно, что попав в какой-то узел он может выбрать только один единственный узел-преемник (потому что его стратегия оптимальна (однозначна) по определению!).

Не обязательно. Может быть несколько оптимальных путей.

Цитата:

Все оптимальные пути, полученные полным перебором на практике, не содержат повторов и пересечений. Я проверял.

Тогда это теорема и незачем её ставить в условие задачи.

Цитата:
3.

Кроме того без этого ограничения задача станет более общей.
Комивояжер сможет посетить и тупиковые селения, в которые ведет только одна дорога.
[Ответ][Цитата]
shuklin
Сообщений: 2053
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 4:34
Цитата:
Автор: Анатоль

А зачем в условии комивояжёру чтобы только один раз пройти каждую точку?
Ведь для практических целей это бессмысленно.
Ведь практический смысл именно в наименьшей сумме.

Да, в этой задаче можно было бы говорить о "хотя бы один раз" с наименьшей суммой.
Интрига в том, чтобы обойти все точки. Полный перебор всех точек заложен в условии.
[Ответ][Цитата]
shuklin
Сообщений: 2053
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 4:38
Цитата:
Автор: Анатоль

Комивояжер сможет посетить и тупиковые селения, в которые ведет только одна дорога.

Точно. Если несколько деревьев связать через один узел, то не пройти по этому узлу несколько раз будет проблематично
[Ответ][Цитата]
Андрей
Сообщений: 3436
На: Выполнение команд (решение задач)
Добавлено: 12 сен 12 5:13
Цитата:
Автор: Анатоль
Может быть несколько оптимальных путей.
Может. Но в каждом из них каждый узел будет посещаться один раз.

Цитата:
Автор: Анатоль
Комивояжер сможет посетить и тупиковые селения, в которые ведет только одна дорога.
Мы не решаем задачу доставки почты, надеюсь Вы понимаете. Мы решаем задачу создания ИИ. Задача коммивояжёра - только удобная привычная наглядная отвлечённая аналогия.
[Ответ][Цитата]
 Стр.31 (56)1  ...  27  28  29  30  [31]  32  33  34  35  ...  56<< < Пред. | След. > >>