GotAI.NET

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

 

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

 Все темы | Новая тема Стр.38 (56)<< < Пред. | След. > >>   Поиск:  
 Автор Тема: На: Выполнение команд (решение задач)
kondrat
Сообщений: 4026
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 1:12
Так значит, всё-таки, евклидово пространство и расстояния по прямой...
На мой взгляд, точно задачу минимальной длины цикла гамильтона в от балды нагруженном графе можно решить только полным перебором. Для упрощений, как, в прочем, и в реальной жизни, требуются доп. ограничения и допуски. Хорошо бы, также, среднюю ошибку оценить, хотя бы в рамках одной реализации.
Задача очень похожа на задачу поиска алгоритма сжатия белого шума.
Программу не ковырял из-за отсутствия времени.
Предлагаю попросить Гришу Перельмана найти общее между топологиями, онтологиями, нейроникой и т.п.
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 1:26
1. Никто не спорит (надеюсь), что полный перебор - это единственный метод, который даёт гарантированно лучшее решение. Сейчас я ищу (неполным перебором аналогий) быстрый и идеологически обоснованный подоптимальный метод решения.
2. Коммивояжёр может заканчивать своё путешествие в любом городе, поэтому общий случай не сводится к гамильтоновому циклу.
3. В реальной жизни "доп. ограничения и допуски" - это не более, чем просто дополнительные задачи. В данной программной аналогии точка - это и есть задача. Так что не следует плодить того, чего не следует.
[Ответ][Цитата]
kondrat
Сообщений: 4026
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 1:42
В данном случае, допуском (то же, что и ограничение) является евклидовость пространства и выполнение неравенства треугольника.
Т.е. задача решается для для небольшого класса реализаций, по сравнению с общей задачей.
[Ответ][Цитата]
Tester64
Сообщений: 1910
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 2:13
Шикарный алгоритм... Давно подобный искал... и даже где-то встречал явно более ранние версии алгоритма. Это Ваша разработка?
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 2:22
Не назвал бы это "разработкой". Алгоритм предельно прост и очевиден, умещается в 50 строк кода.
Вот над рекурсивным полным перебором пришлось попотеть. Хоть он и дал худший результат.
[Ответ][Цитата]
Tester64
Сообщений: 1910
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 2:36
Цитата:
Автор: Андрей
Не назвал бы это "разработкой".

Не скажите! Те примеры что я встречал выдерживали 12-14 точек на моей машине в минуту/две.
Сейчас для одной фирмы пишу некое подобие логистики. И пока "для коллекции" (для будущих анализов кода) собрал 5-8 более менее рабочих алгоритмов.
Но я заметил что Ваш алгоритм использует всего один поток процессора! Тяжело ли его распаралелить? И на сколько процесоров максимум?
[Ответ][Цитата]
Fractaler
Сообщений: 2490
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 2:54
Есть визуализаторы (Графы. Циклы и разрезы) на http://rain.ifmo.ru/cat/view.php/vis/graph-circuits-cuts
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 3:01
2 Tester64
1. Вам попались какие-то сильно неоптимизированные алгоритмы. Полный перебор находит наилучший маршрут для 15 узлов за несколько секунд. Если скорость принципиально важна, то лучше, конечно, всё переписать на MASM.
2. Поскольку рассматриваемые тут алгоритмы рекурсивные то их распараллеливание (разделение на суб-задачи) не должно составить особую проблему. Первый алгоритм естественным образом это обеспечивает, даже не требует модификации.
[Ответ][Цитата]
Tester64
Сообщений: 1910
На: Выполнение команд (решение задач)
Добавлено: 21 сен 12 3:28
>> Вам попались какие-то сильно неоптимизированные алгоритмы. Полный перебор находит наилучший маршрут для 15 узлов за несколько секунд.
У меня в примерах (некоторые за исходники даже денежку просят) 14-15 узлов шло при полном переборе не меньше 30 секунд, а это очень много учитывая что для моей задачи нужно 30-50 точек минимум
>> Если скорость принципиально важна, то лучше, конечно, всё переписать на MASM.
Не долюбливаю MASM. По моему он уходит в прошлое как система оптимизации. Полезен в основном для драйверов, ОС и прошивок чипов. Пора использовать потоки и облака. К тому-же не мультиплатформенный. Поглядываю уже из Делфи в сторону Лазаруса для линукса и андроида.
>> Поскольку рассматриваемые тут алгоритмы рекурсивные то их распараллеливание (разделение на суб-задачи) не должно составить особую проблему. Первый алгоритм естественным образом это обеспечивает, даже не требует модификации.
Вот это уже о-о-очень интересно! Хотя с семафорами/мютексами повозится прийдется. К тому-же довольно тяжело сбалансировать количество потоков (что-бы не зашкалило за 200, когда разумно было бы на 4х ядрах не больше 8).
Мне предстоит в моем проекте (через месяц добирусь и до коммивояжера) брать данные для матрицы растояний из базы данных, а возможно даже с внешнего SQL сервера. Вот где ОЧЕНЬ не помешает оптимизация.
[Ответ][Цитата]
Tester64
Сообщений: 1910
На: Выполнение команд (решение задач)
Добавлено: 22 сен 12 20:47
Цитата:
Автор: Андрей
2. Поскольку рассматриваемые тут алгоритмы рекурсивные то их распараллеливание (разделение на суб-задачи) не должно составить особую проблему. Первый алгоритм естественным образом это обеспечивает, даже не требует модификации.


Не могли бы Вы в следующей версии РАЗДЕЛИТЬ логику и графику по разным юнитам? Очень тяжело понять алгоритм "коммивояжера", учитывая что почти половину кода занимает обработка графики и системные функции. Опять-же проще будет подключить распаралеливание. А даже по самым скромным оценкам это должно ускорить алгоритм на 4х ядерном процессоре раза в 3.5-4.
[Ответ][Цитата]
NO.
Сообщений: 10700
На: Выполнение команд (решение задач)
Добавлено: 22 сен 12 21:09
Tester64:
Какой-то коммивояжор успевает за день в 30 точек?
[Ответ][Цитата]
Tester64
Сообщений: 1910
На: Выполнение команд (решение задач)
Добавлено: 22 сен 12 21:35
Речь шла о фирме, которая по нескольким областям развозит мелкий товар фурой. В городе до 10 точек, городов(крупных и почти незаметных на карте) до 50... от 150 до 300 накладных... маршрут длится до 7 дней! Сейчас это делается через главную страницу гугла и слегка подправляется руками. Точки каждый раз ищутся вручную заново. Конечно же гугл быстро решает комивояжера!

Сейчас в процессе учетная программа для накладных. Пытаюсь прицепить справочник городов с координатами. Следующим этапом будет проставлять их на гугл для прокладки маршрута. Машруты сохранятся в базу как матрица растояний между городами. И по мере надобности будут подаваться в алгоритм комивояжера для поиска оптимального. Кстати гугл ограничивает точки английским алфавитом A-Z (26 максимум), а мне нужно до 50 "пунктов" и еще десяток-два "несущих" (хочу проехать через ... не смотря ни на что или только там можно ездить фурам)
[Ответ][Цитата]
Андрей
Сообщений: 3943
На: Выполнение команд (решение задач)
Добавлено: 23 сен 12 3:37
Цитата:
Автор: Tester64
Не могли бы Вы в следующей версии РАЗДЕЛИТЬ логику и графику по разным юнитам? Очень тяжело понять алгоритм "коммивояжера"
1. Следующая версия будет использовать совсем другой принцип определения маршрута. Поймите меня правильно, здесь я всё-таки провожу натурные программные эксперименты, а не помогаю кому-то подзаработать...
2. Логика и графика в программе уже полностью разделены. Тот факт что они внесены в один вычислительный поток не должно вводить в заблуждение. После выполнения строки queryperformancecounter(t2) массив CS совержит отсортированные индексы массива узлов mas. Вы можете использовать эти индексы для рисования маршрута, для напускания на них какого-то следующего алгоритмического каскада оптимизации, для сохранения в файл и т.д. Весь алгоритм помещён в процедуру CalcProc. Вне этой процедуры только интерфейс и очевидные вспомогательные микрофункции.
3. Мне чужда мысль о том, что программы можно продавать. Поэтому если Вы хотите таким, на мой взгляд, не совсем честным, способом получить барыш - Вам придётся для этого приложить усилия. Исходные коды перед Вами. По всем техническим вопросам лучше обращайтесь на почту/скайп/icq.
4. Предложенный мной алгоритм не годится для соединения реальных пунктов на карте, потому что в реальности нельзя из произвольного узла попасть в произвольный узел по прямой. Поэтому Вам в любом случае придётся адаптировать алгоритм к ограничениям реальной задачи.
[Ответ][Цитата]
Tester64
Сообщений: 1910
На: Выполнение команд (решение задач)
Добавлено: 23 сен 12 7:01
Цитата:
Автор: Андрей
1. ...
2. ...

Я Вам предложил в следующей версии сам алгоритм комивояжера и обработку графики (рисуем, кнопки, обработки мышки) разнести по разным ЮНИТАМ. Я сразу увидел где заканчивается графика и начинается алгоритм, но читать и тестировать не очень удобно. Мне например Вашего графического и отладочного фунционала мало. У меня форма-пустышка раз в 5 сложнее и мне проще для понимания Вашу логику вырезать и вложить в мой пустой проект чем пробовать что-то менять в Вашем проекте. Опять-же я понимаю что Ваш алгоритм - это всего-лишь очень удачная реализация одного из десятков подобных алгоритмов, где главное преимущество - это скорость работы. Поэтому сам начал проект (только графика, простановка случайных точек, изменение их мышкой и заготовка для поиска) в котором буду тестировать готовые и создавать свой алгоритм (все это на 2D-OpenGL собственной обработки).
Цитата:

4. ...не годится...

Это я тоже понимаю. Матрицу растояний между городами я не планирую брать из векторного сложения координат. Матрицу мне даст гугл(Яндекс/Yahoo/OpenMap/BING/...) или операторы занесут вручную. Открываем карту и просим проложить маршрут, например, из Киева в Житомир - самый короткий маршрут для машины - 140 км.(https://maps.google.com/maps?q=from:+%D0%9A%D0%B8%D0%B5%D0%B2,+%D0%A3%D0%BA%D1%80%D0%B0%D0%B8%D0%BD%D0%B0+to:+%D0%96%D0%B8%D1%82%D0%BE%D0%BC%D0%B8%D1%80&saddr=%D0%9A%D0%B8%D0%B5%D0%B2,+%D0%A3%D0%BA%D1%80%D0%B0%D0%B8%D0%BD%D0%B0&daddr=%D0%96%D0%B8%D1%82%D0%BE%D0%BC%D0%B8%D1%80&hl=ru&ie=UTF8&sll=50.356715,29.59129&sspn=1.351061,3.56781&geocode=FbTOAQMdCMDRASkFRVrhTs_UQDH-RgEX0jFJdg%3BFTrT_gId60u1ASldNforo2QsRzEp4rnZo9JK8Q&t=m&z=9 -> ссылка) Заносим это в базу. Когда мне понадобиться перебрать города через которые нужно проехать (и среди которых попадется Киев и Житомир) при переборе алгорим будет брать 140км, а не растояние перелета. Когда городов всего 50-80, то матрицу примерных растояний вполне можно даже в память занести для дальнейшего анализа. К тому-же мечтаю при подборе оптимального маршрута использовать не один информационный слой ("растояние") а как минимум 6(в идеале 8-11)
Свою программу пишу в одиночку с начала лета в свободное время. Проект крайне тяжелый. Работа одновременно идет на 4х-5ти языках программирования, половина из которых вебовские (не считая изучения API Google). 80% времени уходит на создание двусторонних протоколов общения учетной программы с сервисом гугла. 15% на интерфейсы понятные и удобные для пользователя. Пока не доведу до ума все ЭТО, за коммивояжера серьезно не возьмусь - только в экспериментальном режиме.
Цитата:

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

Смешно это слышать профессиональному программисту! У меня работа такая - делать то что другие не могут, упрощать жизнь, сводить работу целого дня до одно кнопки. Убирать рутину и давать время подумать о развитии. Я делаю "инструменты". И за это получаю "барыш". Вы же молоток на базаре не бесплатно берете. Просто все привыкли что если это софт то значит проще взломать чем купить. А купив с исходниками могут подарить соседу или выложить в интернет. Ваш алгоритм - это капля в море для моего проекта. Просто один из вариантов подхода к авто-подбору пути. На равне с ручным вариантом и предложеным гуглом. В коллекции алгоритмов "коми" до Вашего было 4-5 на Делфи, провереных но медленных. И около 10 на других языках. И я точно знаю что ни один из них полностью мне не подходит. Как минимум в Вашем алгоритме не учтены повторы точек (почему бы не проехать через ЭТОТ-же город когда едем назад?), возврат в исходную(хотя можно положить начало и конец рядом) и (почему-то) исключены пересечения маршрутов.
[Ответ][Цитата]
Вольфрамовый клaпaн
Сообщений: 13070
На: Выполнение команд (решение задач)
Добавлено: 23 сен 12 7:09


Кстати, парни, в такой постановке это уже не коммивояжер, а Транспортная Задача...

[Ответ][Цитата]
 Стр.38 (56)1  ...  34  35  36  37  [38]  39  40  41  42  ...  56<< < Пред. | След. > >>