GotAI.NET

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

 

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

 Все темы | Новая тема Стр.30 (56)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Выполнение команд (решение задач)
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 11:10
спасибо
[Ответ][Цитата]
Андрей
Сообщений: 3459
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 12:25
Решение задачи коммивояжёра рекурсивным полным перебором

Сформулируем задачу.
Дано N узлов, расположенных на плоскости. Задан входной узел (Вх) и выходной узел (Вых). Необходимо обнаружить кратчайший путь, охватывающий все узлы, начинающийся во входном узле, заканчивающийся в выходном узле и проходящий через каждый узел только один раз.

Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:
1. необходимо обнаружить кратчайший гамильтонов цикл
2. необходимо обнаружить кратчайший путь, начинающийся в заданном узле

Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первой формулировки.
Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным - один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.
Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.
Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.

Совершенно очевидно (кому не очевидно, может проверить и убедиться), что задача коммивояжёра в общем случае гарантированно решается оптимально только полным перебором всех вариантов.
В алгоритмической реализации полного перебора возможно применение двух условий, сокращающих время перебора и отсекающих заведомо неоптимальные пути, а именно:
1. При построении очередного варианта пути, подсчитывать его длину и если эта длина превышает уже найденный локальный минимум длины – пропускать этот вариант и все те, которые он порождает.
2. Если следующее выбранное ребро пересекает одно из ранее построенных рёбер – пропустить этот вариант и все те, которые он порождает.

Последнее условие фактически запрещает циклы, т.к. если мы представим себя на месте реального коммивояжёра, то пересечение рёбер (несмотря на то, что в задаче запрещено в явном виде только повторное использование узлов) фактически будет означать возврат коммивояжёра в то место, где он уже был, что противоречит определению оптимального (кратчайшего) пути.

Кроме этого, следует подумать о таком способе оптимизации как уход от вычисления точной длины пути в процессе его поиска. Ведь нам, в сущности, не интересно знать точную длину гипотенузы. Нам интересно знать, какая гипотенуза длиннее для двух данных пар катетов…

Оптимальное решение задачи коммивояжёра на десктопах возможно. Однако с ростом количества узлов время, затрачиваемое на полный перебор, растёт экспоненциально. Таким образом, на машине с четырёхядерным процессором 2,67 ГГц 10 узлов обсчитывается в среднем за 5 миллисекунд, 20 узлов – за 15 минут, а на расчёт оптимального пути для 60 узлов уйдёт более 6 триллионов лет…

Для обхода этого препятствия люди просто отказываются от получения оптимального решения для больших N и вместо задачи коммивояжёра решают какую-то другую, очень похожую, аналогичную задачу. Такой метод подмены задачи получил название «эвристического решения», хотя эвристика в каждом случае – это не более чем случайно выбранная аналогия. Например, отжиг – это решение задачи путём имитации охлаждения кристаллизующихся веществ, жадный алгоритм – это имитация поведения жадного человека, существуют методы, построенные по аналогии с поведением муравьёв, надувающимся воздушным шариком и т.п.

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

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

Мы не будем искать аналогию наугад, мы попробуем решить задачу коммивояжёра максимально непредвзято, не призывая на помощь посторонние аналогии. Попробуем решить общую задачу в общем виде. А для этого призовём на помощь только одну аналогию - аналогию с интеллектом вообще. Как решает сложные задачи (в том числе и задачу коммивояжёра) человеческий интеллект? Он разбивает исходную задачу на дерево более простых под-задач, решает их в обратном порядке и получает результат. Мы поступим точно так же!

Совершенно очевидно, что упростить задачу коммивояжёра для того, чтобы решать её полным перебором за приемлемое время, можно только одним способом – уменьшить количество перебираемых узлов. А это возможно сделать тоже только одним способом – объединить узлы в группы – над-узлы, над-задачи (суб-задачи).

Чтобы поставить задачу коммивояжёра рекурсивно попробуем взглянуть на неё рекурсивно.
Основной элемент в этой задаче – это узел, в который входит одно ребро и выходит одно ребро:


Не призывая посторонние аналогии, мы тут же замечаем аналогию с самой постановкой общей задачи, в которой задано два «крайних» узла: Вх, в который входит коммивояжёр на старте, и Вых, из которого выходит коммивояжёр на финише. Можно сказать, что вся совокупность узлов N в задаче – это один большой узел, в который коммивояжёр входит и выходит по ребру:


Таким образом, вырисовывается общий вид рекурсивного алгоритма.
1. Задать узлы N.
2. Задать максимально допустимое время решения задачи Tmax.
3. Провести на данной машине бенчмарк и определить зависимость времени решения от количества узлов при полном переборе вариантов Т(N).
4. Исходя из заданного количества узлов N, Tmax и зависимости для Т определить, на сколько групп (над-узлов) следует разбить множество из N узлов. Либо задать это количество узлов вручную (именно так мы и поступим).
5. Разбить множество из N узлов на M групп.
6. Провести полный перебор для M групп и найти кратчайший путь для соединения этих групп.
7. После шага 6 у нас известно для каждой группы вход и выход, поэтому мы ставим рекурсивно задачу коммивояжёра для каждой группы, т.е. переходим к шагу 4, где N равно количеству узлов в каждой группе.
8. После выхода из рекурсии получаем подоптимальный путь для данной машины и данного Tmax (либо заданного количества узлов в группе).

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

На шаге 5, очевидно, лучше предпочитать M как можно больше. При М стремящемся к N мы получаем всё более точное решение. Чем меньше мы уходим от полного перебора, тем точнее наше решение. Выбрать M можно по таблице, составленной из самого простого грубого предположения, что на каждом шаге рекурсии мы будем разбивать суб-задачу на группы с одинаковым количеством узлов в группе.



Как видно из таблицы, уже при 18 узлах в одной группе мы можем обрабатывать более 10 миллиардов узлов при глубине рекурсии до 8.

Если мы хотим улучшить найденный таким образом маршрут, то у нас есть такие варианты:
- выбрать более производительную машину
- увеличить допустимое время Tmax
- увеличить количество групп
- увеличить вложенность рекурсии. То есть на шаге 6 разбивать задачу на существенно (в зависимости от N) большее число групп, но производить их перебор не оптимально, а подоптимально. Например, разбивать задачу из 1000 узлов на 500 групп, но искать не кратчайший путь их соединения полным перебором (это слишком долго), а разбивать группы на суб-группы, например по 250 групп и проводить поиск подоптимального пути среди них. И так далее, пока мы не спустимся на уровень, где машина может сделать полный перебор.

Как объединять узлы в группы?
Чтобы не привлекать «с потолка» отвлечённые аналогии и не пользоваться эвристиками, попробуем найти ответ в самой задаче. Совершенно ясно, что изначально в задаче у нас одна группа, для которой заданы Вх и Вых.

Чтобы разбить данную задачу минимум на две, нам необходимо выделить среди всех узлов промежуточный узел, который станет промежуточным входом/выходом.
Поскольку в качестве признака оптимальности в задаче мы применяем евклидово расстояние, то для обнаружения нового промежуточного входа/выхода нам необходимо ввести некий лимит расстояния от каждого узла до уже существующих входа и выхода. Поскольку мы не знаем, что это за лимит возьмём его настолько большим, чтобы оказалось, что все узлы принадлежат только начальной группе. Теперь будем плавно уменьшать этот лимит. При этом один из узлов ранее принадлежавший первоначальной группе должен выделиться. Независимо от того, что именно мы возьмём в качестве лимита, этим узлом станет тот узел, который расположен на самом дальнем расстоянии от первоначальных входа и выхода. Поэтому вместо выдумывания формулы лимита мы можем сразу брать самый дальний узел. После того как мы нашли этот промежуточный вход/выход, мы должны поделить все оставшиеся узлы между новыми двумя группами так, чтобы гарантировать непересечение ребёр.

Если нам надо поделить задачу на произвольное число групп, то мы производим это разбиение рекурсивно. Сначала находим промежуточный вход/выход взаимо-дальний по отношению к начальным входу и выходу. Потом находим второй промежуточный вход/выход взаимо-дальний к первым трём, и так далее.

Очевидно, что при количестве групп, равному N, промежуточные входы/выходы этих групп совпадут с начальными узлами. Таким образом, мы нашли единственно правильное деление всех узлов на группы.

Поиграться с разбиением на группы можно здесь.
Чтобы создать задачу коммивояжёра нужно ввести количество узлов и нажать Enter. Либо загрузить задачу из файла.
Перемещая ползунок можно наблюдать принцип разбиения на группы. Кнопка «Link groups» соединяет текущие группы по оптимальному маршруту полным перебором. Кнопка «Link nodes» соединяет все узлы по оптимальному маршруту полным перебором. Поэтому не следует давить эти кнопки при большом (>18) количестве узлов или групп.

Здесь можно скачать программу для решения задачи коммивояжёра по алгоритму, описанному выше.
Органы управления:
Кнопка «Load» загружает задачу из файла с расширением *.txt
Формат файла txt такой: в каждой строке через 1 пробел указаны координаты x и y для каждого узла в задаче. В первой строке указаны координаты входного узла. В последней строке – координаты выходного узла. Остальные узлы между ними в произвольном порядке. Координаты находятся в диапазоне 0-1 с точностью 6 знаков после запятой. Отделитель целой и дробной части – запятая.

Кнопка «Generate» генерирует рандомом случайную задачу коммивояжёра, с количеством узлов, указанном в поле «Nodes =».

Кнопка «Save» сохраняет координаты узлов данной задачи.

Кнопка «Solve» решает задачу коммивояжёра, рекурсивно разбивая её на константное количество групп, указанном в поле «Groups =». Если заданное количество групп больше либо равно количеству узлов, то будет, естественно, производится полный перебор узлов. Поэтому не рекомендуется указывать количество групп более 18.

В данной программе разбивка на группы не оптимальная, поэтому пересечения случаются. Но этот недостаток принципиально устраним.
[Ответ][Цитата]
Эгг
Сообщений: 10336
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 12:31
Цитата:
Автор: Андрей

Сформулируем задачу.

а в чем сакральный смысл этого огромного сообщения?
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 12:47
Very Fast k-means (VFKM) algorithm (Domingos & Hulten, ) runs as a sequence of k-means runs, with increasing number of examples
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 12:51
Цитата:
Автор: NO.

Very Fast k-means (VFKM) algorithm (Domingos & Hulten, ) runs as a sequence of k-means runs, with increasing number of examples


Еще один пример красивой, но бесплодной теории
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 13:04
Чего это вдруг? k-mean самый простой метод кластеризации. Когда не нужно строить формулы для моделей, его одного хватит и для моделирования и для машинного обучения. Или вот Андрею нужно выделять группы. Может работать за один проход.

Вы наверно из-за интереса к противоборствам красоту недооцениваете. Это потому, что для врага она даже ещё полезнее чем для своих.
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 13:11
Цитата:
Автор: NO.

Чего это вдруг? k-mean самый простой метод кластеризации. Когда не нужно строить формулы для моделей, его одного хватит и для моделирования и для машинного обучения. Или вот Андрею нужно выделять группы. Может работать за один проход.


Ага, только почему-то народ при этом забывает о метриках
В примитивных задачках для теоретиков и эвклидова годится, а в реале все несколько иначе, и это - та самая капля дегтя. В общем, если вам удается решить проблему сходства, то тогда и кластеризация во всей красе может применяться. Только эти проблемы сильно разного уровня сложности.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 13:22
Это разные задачи. Если найти обоснованную метрику сходства всё равно останутся растояния и будет нужно кластеризовать. Может быть только распределение станет менее равномерным. k-mean работает одинаково хорошо и по евклиду и по уму.
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 13:46
Цитата:
Автор: NO.

Это разные задачи. Если найти обоснованную метрику сходства всё равно останутся растояния и будет нужно кластеризовать. Может быть только распределение станет менее равномерным. k-mean работает одинаково хорошо и по евклиду и по уму.


По уму, вы правы, все хорошо работает. Только вот добиться этого обычно бывает непросто
Я ведь не спорю, а только лишь обращаю внимание на то, что без понимания того, как описываются метрики или сходства в пространстве признаков, кластеризация становится красивой безделушкой. И там лежат по сути нетронутые проблемы. Неймарк-гений об этом, мне кажется, первым заговорил много лет назад, но мало кем был услышан

[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 14:09
Ну вот, а что делать если ума нет?
[Ответ][Цитата]
Андрей
Сообщений: 3459
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 16:20
Цитата:
Автор: Egg
в чем сакральный смысл этого огромного сообщения?
Смыслов много.
1. Я нашёл очень хороший (а может и лучший) гибкий алгоритм решения задачи коммивояжёра. Возможно (при определённых условиях, которые я сейчас исследую...) он может решать эту задачу оптимально за приемлемое время.
2. Показано на примере, как может работать механизм обобщения - механизм выкидывающий детали и оставляющий общее (крайнее!), а это задел для (моих) исследований в области распознавания.
3. Построение плана решения, при интеллектуальном решении любой задачи, можно свести к задаче коммивояжёра. Предложенный алгоритм является одновременно
- илюстрацией процесса разбиения сложной задачи на суб-задачи и
- механизмом решения этих суб-задач - т.е. соединения суб-задач в один целостный последовательный план решения.
Т.е. это такой маленький вырожденный ИИ. Тут всё очень рекурсивно и интересно.

Цитата:
Автор: NO.
Very Fast k-means
Сходство чисто внешнее. Суть принципиально разная.
- Центры групп (классов) выделяются и добавляются рекурсивно, т.е. каждый следующий центр можно обнаружить только если найдены все предыдущие.
- Количество классов можно наращивать произвольно, вплоть до N. Чем больше, тем лучше. Здесь процесс ограничивает только вычислительная мощь. Никакой проблемы с отнесением узлов к классу нет - евклид.
- Изначально в задаче всегда есть два заданных начальных класса, которые предопределяют судьбу всей задачи. Это наводит на очень глубокие размышления о целостности сознания, прошлом и будущем, и вообще о процессе решения задач человеком.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 17:26
Если группы выделяются рекурсивно то зачем указывается количество? Делили бы всё рекурсивно пополам и пополам, без количества групп.
[Ответ][Цитата]
Андрей
Сообщений: 3459
На: Выполнение команд (решение задач)
Добавлено: 08 сен 12 23:07
Количество указывается для того, чтобы задать границу, ниже которой на группы уже разбивать не надо, а делать полный перебор узлов. Задача решается полным перебором. Но когда узлов много, мы вынуждены разбивать их на группы и сначала строить оптимальный маршрут для соединения групп. Отсюда очевидно, что чем больше групп, тем ближе мы к оптимальному решению.
Точнее и более правильно следует указывать два числа:
Nmax - максимальное количество узлов, для которого делается полный перебор без разбиения на группы
Gmax - количество групп для разбиения узлов, количество которых превысило Nmax. И это число можно задавать очень по разному. Можно делить на 2 количество узлов (как Вы предлагаете), можно отнимать единичку, можно брать по золотому сечению, можно брать X%... В данной программе, для простоты и наглядности, я взял грубо Gmax = Nmax
[Ответ][Цитата]
Андрей
Сообщений: 3459
На: Выполнение команд (решение задач)
Добавлено: 09 сен 12 8:06
Существенно улучшил алгоритм в плане пересечений ребёр и программной архитектуры.
Кому интересно, качать здесь.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 09 сен 12 8:58
быстро считает
[Ответ][Цитата]
 Стр.30 (56)1  ...  26  27  28  29  [30]  31  32  33  34  ...  56<< < Пред. | След. > >>