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

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

Все темы | Новая тема  Стр.1 (8) След. > >>    Поиск:
Автор	Тема: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл.
kondrat Сообщений: 4026	Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 07 окт 12 12:50 Для тех, кто следил за рассуждениями в теме Выполнение команд (решение задач), Предлагаю продолжить обсуждение алгоритмов оптимизации поиска в этой теме. Что интересует лично меня: Задача 1. Поиск кратчайшего цикла Гамильтона в полном, неориентированном, нагруженном графе (не псевдо, не мульти). Достигнутые результаты (рабочие гипотезы): Основа алгоритма (по аналогии с жадным): Находим наименьшее ребро. Удаляем его (т.е.объединияем узлы). Из пар инцидентных получившемуся узлу 2*(n-1) рёбер оставляем наименьшие. Повторяем процедуру. Краткие итоги обсуждения: 1. К маршруту нужно добавлять отбрасываемые в первой строке рёбра. Кому интересно, может убедится, что алгоритм сходится ровно на N-1 шаге. Можно поискать ошибку, доказывая, что все вершины пройдены по 1 разу и маршрут без разрывов. Это достаточно элементарно. Мне просто лень. 2. Сложность нужно вычислять с учётом первоначальной сортировки (или статистики) и строить алгоритм так, чтобы максимально использовать память при следующем поиске. Это самый интересный вопрос, ответ на который я пока не получил. Если учесть, что рёбра могут быть одинаковые (или в рамках погрешности), то можно существенно оптимизировать алгоритм с учётом статистики и допусков. При построении оптимального алгоритма всякие рекурсии с фракталами рисуются на раз-два. 3. Т.к. на каждом шаге для суммы выбирается с вероятностью 1 минимальное из оставшихся слагаемое, то алгоритм находит кратчайший цикл. 4. Если придать длинам рёбер физический смысл и устремить N к бесконечности, возможно, получатся построения аналогичные таковым из ТФ и прочих наук. Задача 2. Мне пока не всё понятно, поэтому названия не придумал. Цитата: Автор: Egg вот есть еще одна полезная забавная задачка... она встречается в навигации по всяческим структурам... визуализационная задача... есть граф... неориентированный... некоторые вершины связаны ребрами, но не полносвязно, предположим, есть некоторый "уровень разряжения", где-нибудь 10-25%... не больше... нужно его планаризовать - то есть разместить вершины на плоскости так, чтобы никакие ребра не пересекались... разумеется, для полносвязного графа решение существует только для 3D... Если у кого появится вопрос в виде задачи, прошу обозначать и нумеровать их. У меня ещё есть кролики в шляпе!))) К сожалению, ещё не все они достаточно выросли. ((( [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 07 окт 12 16:59 Замечание: Требование прохождения вершины по одному разу автоматически сводит граф к "не псевдо". А требование минималности маршрута так же автоматически делает его "не мульти". С неориентированностью немного сложнее... [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 12:31 Очень жаль, что никто до сих пор не запарился указать на элементарные ошибки и не оценил сопутствующие сентенции. Игра не удалась... Однажды, на АИ портале я уже задумывался над игровой составляющей совместного творчества и, даже, озвучивал эту идею. На что уважаемый Victor Tsaregorodtsev, который даёт, обычно, исключительно интересные для меня ссылки, заметил, что игры в стиле RPG в этой области на форумах уже были и почти ни к чему не привели. Но, всё-таки, я хочу предложить ещё одну игру... Она не требует особых способностей к сотрудничеству и самоорганизации. Мотивация целиком возложена на играющего. Я оставляю за собой право поржать в обоих исходах. Но и обманывать никого не собираюсь. Закрытый тендер. Не аукцион. На кону методика нижней оценки группы кандидатов в кратчайшие маршруты (не в смысле количества, а в смысле маршрутов), которая, к сожалению, почти раскрывает весь подход. В перспективе - алгоритм, дающий полный перебор при плохой статистике, N шагов (не считая микроподготовки) при хорошей. От применения подхода и решения - ваще ахринедь можна. Методика очень проста, как и все решённые задачи. Принимаются любые ставки - ссылки на интересную, по мнению игрока, инфу, какие-либо предложения, чего вы там ещё можете себе позволить. Тендер проводится в 3 тура. 1 тур - первая неделя. 2 тур - вторая неделя. 3 тур - третья неделя. В каждом туре идёт скрытая торговля. В конце тура объявляются победители (3, 2, 1). Делайте ставки, господа! [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 13:23 Если и эта игра не состоится, - придётся строить боевого дроида самому (((( [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 13:28 И, кстати, если будут конструктивные предложения по решению задач - шлите на скрытый тендер. Мой маил - kondrat23@mail.ru [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13070	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 13:41 kondrat, мне кажется, Вы допускаете одну большую ошибку по процедуре - на этом форуме не занимаются общим творчеством и анализом или решением чужих задач, здесь люди отдыхают по поводу своих задач... своих... у каждого их миллион, и задач, и гениальных теорий и прочего добра, до которого не доходят руки, а Вы тут предлагаете какие-то скучные аукционы и тендеры... И не забывайте, что постоянных участников здесь около десяти и у каждого есть работа или проекты, поэтому большинство из нас здесь именно отдыхают, а не создают искусственный интеллект, мне, например, задач по замысловатой обработке данных хватает и на рабочих проектах... поэтому, если Вы будете делать то, что нравится Вам - этого будет вполне достаточно для того, чтобы тема развивалась... ждать энтузиазма со стороны других участников - не оптимистично, на мой вкус... [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 13:47 Цитата: Автор: Egg kondrat, мне кажется, Вы допускает одну большую ошибку по процедуре - на этом форуме не занимаются общим творчеством и анализом или решением чужих задач, здесь люди отдыхают по поводу своих задач... своих... у каждого их миллион, и задач, и гениальных теорий и прочего добра, до которого не доходят руки, а Вы тут предлагаете какие-то скучные аукционы и тендеры... И не забывайте, что постоянных участников здесь около десяти и у каждого есть работа или проекты, поэтому большинство из нас здесь именно отдыхают, а не создают искусственный интеллект, мне, например, задач по замысловатой обработке данных хватает и на рабочих проектах... Эт - да. Но просмотров, почему-то, гораздо больше десяти. Может, молодёжь заинтересуется и подтянется. В тендере же не заоблачные условия. А задачка достаточно интересная и перспективная. [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 14:02 Просто, трёп кажого 11-ого ни о чём изрядно утомил. А тут есть элемент игры и азарта. [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 14:16 Цитата: Автор: Egg поэтому, если Вы будете делать то, что нравится Вам - этого будет вполне достаточно для того, чтобы тема развивалась... ждать энтузиазма со стороны других участников - не оптимистично, на мой вкус... Я, к сожалению, любитель. У меня есть опыт во многих других областях, но в этой - гляжу широко раскрытыми глазёнками и делаю то, что другие дяди уже за-сь делать. Мне кажется, что в азартные игры на тему ИИ ещё никто не играл. Зато, я постоянно натыкаюсь на посты, типа: а кто вам раскроет своё ноухау? В любом случае, пацан сказал - пацан сделал. Всё остальное - интерес вероятных игроков. [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13070	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 14:44 Цитата: Автор: kondrat Я, к сожалению, любитель. а я, к сожалению, профессионал, поэтому просто не могу делиться кодом (не потому, что жалко, а потому, что он, как правило, принадлежит заказчику), а о некоторых проектах даже ни разу в Сети не рассказывал... вот мне интересно обсуждать моделирование и обработку естественного языка (сейчас мы с парнями над этим трудимся), а графы, коммивояжеры и прочее - это просто ежедневная рутина, например, обработка тех или иных корпусов - это миллиарды записей, каждый алгоритм для каждой задачи - уникальный (с учетом всех особенностей фактуры данных), иначе он будет не три дня работать, а месяц... [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 15:09 Цитата: Автор: Egg а я, к сожалению, профессионал, поэтому просто не могу делиться кодом (не потому, что жалко, а потому, что он, как правило, принадлежит заказчику), а о некоторых проектах даже ни разу в Сети не рассказывал... вот мне интересно обсуждать моделирование и обработку естественного языка (сейчас мы с парнями над этим трудимся), а графы, коммивояжеры и прочее - это просто ежедневная рутина, например, обработка тех или иных корпусов - это миллиарды записей, каждый алгоритм для каждой задачи - уникальный (с учетом всех особенностей фактуры данных), иначе он будет не три дня работать, а месяц... В этом вопросе я вас понимаю больше, чем вы думаете. Скажите, пожалуйста, вас сама идея игры заинтересовала? Или, всё-таки, этот подход совсем бесперспективен? Должен заметить, что на данный момент я действительно думаю, что владею хорошим подходом. Если в ходе всей заварухи выясню, что ошибаюсь, то верну все ставки и принесу публичные извинения. Право поржать в обоих случаях означает, что будет ли выигравший удовлетворён или нет, - ставки не будут возвращены. Т.е. в чём-то придётся мне доверять. [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13070	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 15:44 Цитата: Автор: kondrat Скажите, пожалуйста, вас сама идея игры заинтересовала? Или, всё-таки, этот подход совсем бесперспективен? честно говоря, я не очень понял в чем игра... Мы с Натой (это жена) довольно часто ездим в Вегас, любим этот город и понимаем игру (первые свои евро я оставил в Монте-Карло)... Вашу игру я не понимаю... дело не в ставках... я помню, первый раз, когда я привел Нату на рулетку, я ей говорил на ухо что выпадет, часто не попадало, то когда пару раз выпало, она стало совсем иначе относиться к этому... Вы не рассказали в чем суть Вашей игры... [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 16:00 Игра - соревнование, кто ценнее выступит в тёмную (победитель будет публиковаться по его желанию). Выигрыш - удовлетворение любопытства (на очень интересную тему) + весьма возможный бонус от него. Ставка - любая. От кота в мешке до всемирного господства. А в холдэм вы там не рубитесь? [Ответ][Цитата]
Вольфрамовый клaпaн Сообщений: 13070	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 16:28 нет, мы уже не настолько молодые, мы любим только свободу и деньги... как говаривал мой друг, Уальд, когда я был молодым, я думал, что деньги - важнее всего, теперь, когда я стал взрослым, я понимаю, что я не ошибался... я не понял, что значит "ценнее выступить в темную", Вы надеетесь, что кто-то Вам даст алгоритм? да здесь половина слова такого не знает... [Ответ][Цитата]
kondrat Сообщений: 4026	На: Оптимальный поиск, сжатие и т.п. Минимальный Гамильтоновский цикл. Добавлено: 09 окт 12 16:32 Нее Любая - значит любая Я не ограничиваю фантазию игроков. Кому больше выигрыш понравится. Приму любые описания ставок. Но при обмене придётся предъявить поставленное. Кто проврался - точно будет обубликован. [Ответ][Цитата]
Стр.1 (8): [1]  2  3  4  5  ...  8 След. > >>