roboforum.ru

Технический форум по робототехнике.

Алгоритм авто-сторожа

Re: Алгоритм авто-сторожа

Сообщение Michael_K » 03 ноя 2009, 03:15

На входе у кого, простите?
Вы предполагаете, что у робота есть карта,
а этого в условии нет - просто вам так удобнее считать.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 03:32

:) я и не предпологаю, всё чётко написано на предыдущей странице.
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 08:33

Angel71 писал(а): :crazy: таки гамильтонов цикл

И что, проще стало? Где алгоритм? Ему эйлеров цикл то построить проблема будет, а тут...

Добавлено спустя 2 минуты 9 секунд:
Да еще и на указанном им в примере количестве вершин...
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 15:58

=DeaD=, смысл курсовой если не ошибаюсь заключчается в том, чтобы студент смог продемонстрировать чему научился во время учёбы и иногда еще в демонстрации как он научился учится. кого как, нас в основном учили второму :) и по жизни это помогает лучше.
а про алгоритм и программу... та программа, что он привёл немного под другие цели делалась. допустим размер робота равен размеру клетки, смотрим картинки из той программы. мап2, разрешение 370*516. мап3, разрешение 477*407. путь при таком количестве точек естественно искать будет как минимум долго. :pardon: значит не нужно делать карту с такими разрешениями.
:crazy: или ему нужно будет вот так, как в следёющем абзаце обьяснять?
запускаем игру сапёр, которая есть почти на каждом компе с виндой и делаем по аналогии - маленькая карта, но каждая точка/клетка игрового поля на экране отображается квадратиком, размером n*m. для поиска пути используем алгоритм решения задачи коммивояжера, что это такое и код алгоритма смотрим тут: let me google that for you: решение задачи коммивояжера
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 16:18

Задача коммивояжера - это слегка другая задача вроде? У нас все ребра весят одинаково, но далеко не все есть, и вопрос в том, что вершины надо посетить ровно по 1 разу.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 16:32

один из вариантов задачи коммивояжера, это когда нужно "посетить" только один раз. :oops: я вроде же ничего не напутал?
Вики:
В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.

:) а зачем при преобразовании картинки в данные для алгоритма запихивать те, которые представляют клетки, по которым нельзя перемещаться воображаемому роботу?

Добавлено спустя 7 минут 19 секунд:
берём квадрат, размером 5 на 5, допустим препятствие это 1 клетка в центре, стены толщиной в одну клетку по контуру квадрата. :) итого у нас остаётся для алгоритма всего 8 клеток, вот по 8ми вершинам обход и делать. :) я это так представляю
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 16:35

2Angel71: Суть задачи коммивояжера в том, что ребра имеют разный вес и поэтому интересно найти кратчайший гамильтонов цикл, что может быть существенно сложней поиска любого гамильтонова цикла.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 16:41

:) не вижу особой загвоздки в том, что рёбра будут иметь одинаковый вес. главное вроде найти путь или определить, что проложить на данной карте при данных условиях невозможно.
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 16:44

2Angel71: Хорошо, давай так - ты видел задачу коммивояжера с алгоритмом решения, в которой решение может не существовать? :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 17:01

=DeaD= :) не совсем пойму, что донести хотите.
Untitled-1.jpg
Untitled-1.jpg (14.41 КиБ) Просмотров: 3744

если нельзя перемещаться наискось, то что-то мне подсказывает, что решения при такой начальной точке нет
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Re: Алгоритм авто-сторожа

Сообщение =DeaD= » 03 ноя 2009, 17:12

2Angel71: Если можно перемещаться "наискость", то добавление всего 1 клетки сделает этот вариант также неберущимся.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Алгоритм авто-сторожа

Сообщение Angel71 » 03 ноя 2009, 17:17

assassin6 писал(а):3) человек рисует помещение вид сверху и расставляет препятствия, примеры даны в архиве с программой
5) 2 условия:
1. Робот не должен попасть на одно и тоже место 2 раза(то есть в одну и ту же клетку)

:pardon: какие условия и рисунок, такой и ответ программы должен быть - или путь или окошко с ругательством
Аватара пользователя
Angel71
 
Сообщения: 10668
Зарегистрирован: 18 апр 2009, 22:18
Предупреждения: -1

Пред.

Вернуться в Юмор

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2