GotAI.NET

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

 

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

 Все темы | Новая тема Стр.29 (56)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Выполнение команд (решение задач)
Андрей
Сообщений: 3414
На: Выполнение команд (решение задач)
Добавлено: 27 авг 12 13:58
Для проверки некоторых идей сделал рекурсивную решалку Задачи коммивояжёра полным перебором. Скачать можно здесь.
По нажатию клавиши Enter в поле ввода программа случайно расставляет, заданное в этом поле, количество узлов. По нажатию на кнопку Start программа ищет наилучший (кратчайший) путь из красного узла в синий узел (выбранные случайно).
Координаты узлов можно сохранить в файл/загрузить из файла.
Задавать количество узлов более 18 не рекомендуется.
Для ускорения использован минимакс по длине и проверка на пересечение.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 27 авг 12 14:32
Задача коммивояжера O(N!)
Полиномы это N^k
А не-полином это уже 2^N
[Ответ][Цитата]
Know How
Сообщений: 10000
На: Выполнение команд (решение задач)
Добавлено: 27 авг 12 17:27
Цитата:
Автор: Андрей

Задавать количество узлов более 18 не рекомендуется.

не видел пока, чтобы коммивояжер был решен лучше, чем мое решение 2004 года... там, конечно, нет полного перебора, только отжиг, но зато можно задавать до 10000 узлов...
[Ответ][Цитата]
Know How
Сообщений: 10000
На: Выполнение команд (решение задач)
Добавлено: 27 авг 12 17:28
Цитата:
Автор: Slava
Если вы так думаете, то вам еще расти и расти

я очень редко ошибаюсь... особенно в таких вещах...
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 27 авг 12 23:17
Цитата:
Автор: Egg

я очень редко ошибаюсь... особенно в таких вещах...


Напоминает какой-то известный парадокс
Мои поздравления
[Ответ][Цитата]
Андрей
Сообщений: 3414
На: Выполнение команд (решение задач)
Добавлено: 27 авг 12 23:49
Цитата:
Автор: Egg
там, конечно, нет полного перебора, только отжиг
Меня сейчас интересует именно оптимальный полный перебор, чтобы попробовать на его основе сделать неоптимальный рекурсивный перебор. Интересно будет сравнить с отжигом.

2 Slava
Когда Вы не отвечаете Egg'у там, где нужно не отвечать, то выглядите мудрее...
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 2:01
В задаче коммивояжера точки обычно располагаются на плоскости. Это мало о чем говорит людям, не занимавшимся топологией. Они этот факт не замечают, не используют и решают более общую задачу чем нужно, поэтому менее эффективно чем следовало бы.
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 2:50
Цитата:
Автор: Андрей
2 Slava
Когда Вы не отвечаете Egg'у там, где нужно не отвечать, то выглядите мудрее...


Знаете, Андрей, мне глубоко безразлично, как я выгляжу
Вы даже и представить себе, наверно, не можете, насколько это так
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 2:54
Цитата:
Автор: Андрей

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


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

Цитата:
Автор: Slava
У Загоруйко есть близкая к этому процедура кластеризации
Благодарю, попробую найти.
[Ответ][Цитата]
Victor G. Tsaregorodtsev
Сообщений: 3100
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 5:53
Цитата:
Автор: Slava
У Загоруйко есть близкая к этому процедура кластеризации - Краб, кажется, - уж если сравнивать, то с ней.

Не, Крабы были на минимальных связных подграфах - из вершины графа (из точки) могли выходить 3 и более ребра. Т.е. заточка была именно под кластеризацию, а не под последовательный обход всех точек из известного начала в известный конец.

Цитата:
Автор: Slava
Вообще, почитайте его - очень незаурядный мужик

+1. Книга 99 года - великолепна. Но под современные практические задачи мало подходит - сейчас у народа преимущественно big data (гигабайты и больше), и поэтому желательна линейная сложность алгоритмов (ну или полиномиальная с достаточно малой степенью).


2 Андрей:
Гуглите Загоруйко "Прикладные методы анализа данных и знаний" - книга есть в инете.
Там, правда, Краб не описан (описан Лямбда-краб), но разница только в том, что в Лямбда-крабе анализируются отношения длин смежных (выходящих из одной вершины) рёбер графа, а в обычном крабе - просто длины рёбер (в Крабе граф будет резаться по самым коротким рёбрам, а в лямбда-версии - по рёбрам на границе между сгущёнными и разреженными массивами точек, т.е. там, где отношение расстояний уходит от близкого к единице).
[Ответ][Цитата]
Fractaler
Сообщений: 2490
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 6:51
Цитата:
Автор: Slava
а где интуиция?

Если по NO-ссылке, то, видимо, где-то здесь - Figure 3: Comparison of logical and analogical reasoning
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 8:14
Цитата:
Автор: Victor G. Tsaregorodtsev
Не, Крабы были на минимальных связных подграфах - из вершины графа (из точки) могли выходить 3 и более ребра. Т.е. заточка была именно под кластеризацию, а не под последовательный обход всех точек из известного начала в известный конец.


Вы правы, Виктор, и я это помнил, но все это по сути где-то рядом лежит, а у Андрея соображаловка хорошо работает, так что - все в порядке.
[Ответ][Цитата]
Slava
Сообщений: 3070
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 8:15
Цитата:
Автор: Fractaler
Если по NO-ссылке, то, видимо, где-то здесь - Figure 3: Comparison of logical and analogical reasoning


Да, но речь ведь шла не о том, что можно домысливать, глядя на эту схемку, а о том, что автор не удосужился сам это явным образом обозначить.
[Ответ][Цитата]
Андрей
Сообщений: 3414
На: Выполнение команд (решение задач)
Добавлено: 28 авг 12 9:53
Цитата:
Автор: Victor G. Tsaregorodtsev
Загоруйко "Прикладные методы анализа данных и знаний"
Благодарю, нашёл книгу. На всякий случай сделал копию.
[Ответ][Цитата]
 Стр.29 (56)1  ...  25  26  27  28  [29]  30  31  32  33  ...  56<< < Пред. | След. > >>