roboforum.ru

[Michael_K]

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

[Angel71]

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

[=DeaD=]

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

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

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

[Angel71]

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

[=DeaD=]

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

[Angel71]

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

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

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

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

[=DeaD=]

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

[Angel71]

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

[=DeaD=]

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

[Angel71]

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

Untitled-1.jpg (14.41 КиБ) Просмотров: 5450

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

[=DeaD=]

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

[Angel71]

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

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