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

Michael_K

На входе у кого, простите?
Вы предполагаете, что у робота есть карта,
а этого в условии нет - просто вам так удобнее считать.

Angel71

я и не предпологаю, всё чётко написано на предыдущей странице.

=DeaD=

Angel71 писал(а):

таки гамильтонов цикл

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

Добавлено спустя 2 минуты 9 секунд:
Да еще и на указанном им в примере количестве вершин...

Angel71

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

и по жизни это помогает лучше.
а про алгоритм и программу... та программа, что он привёл немного под другие цели делалась. допустим размер робота равен размеру клетки, смотрим картинки из той программы. мап2, разрешение 370*516. мап3, разрешение 477*407. путь при таком количестве точек естественно искать будет как минимум долго. :pardon:

значит не нужно делать карту с такими разрешениями.
:crazy:

или ему нужно будет вот так, как в следёющем абзаце обьяснять?
запускаем игру сапёр, которая есть почти на каждом компе с виндой и делаем по аналогии - маленькая карта, но каждая точка/клетка игрового поля на экране отображается квадратиком, размером n*m. для поиска пути используем алгоритм решения задачи коммивояжера, что это такое и код алгоритма смотрим тут: let me google that for you: решение задачи коммивояжера

=DeaD=

Задача коммивояжера - это слегка другая задача вроде? У нас все ребра весят одинаково, но далеко не все есть, и вопрос в том, что вершины надо посетить ровно по 1 разу.

Angel71

один из вариантов задачи коммивояжера, это когда нужно "посетить" только один раз. :oops:

я вроде же ничего не напутал?
Вики:

Цитата:

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

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

Добавлено спустя 7 минут 19 секунд:
берём квадрат, размером 5 на 5, допустим препятствие это 1 клетка в центре, стены толщиной в одну клетку по контуру квадрата.

итого у нас остаётся для алгоритма всего 8 клеток, вот по 8ми вершинам обход и делать.

я это так представляю

=DeaD=

2Angel71: Суть задачи коммивояжера в том, что ребра имеют разный вес и поэтому интересно найти кратчайший гамильтонов цикл, что может быть существенно сложней поиска любого гамильтонова цикла.

Angel71

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

=DeaD=

2Angel71: Хорошо, давай так - ты видел задачу коммивояжера с алгоритмом решения, в которой решение может не существовать?

Angel71

=DeaD=

не совсем пойму, что донести хотите.

Вложение:

Untitled-1.jpg [ 14.41 КиБ | Просмотров: 4848 ]

если нельзя перемещаться наискось, то что-то мне подсказывает, что решения при такой начальной точке нет

=DeaD=

2Angel71: Если можно перемещаться "наискость", то добавление всего 1 клетки сделает этот вариант также неберущимся.

Angel71

assassin6 писал(а):

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

какие условия и рисунок, такой и ответ программы должен быть - или путь или окошко с ругательством

roboforum.ru

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

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